Koalitionsbildning är ett nyckelämne i multiagentsystem. Man kan föredra en koalitionsstruktur som maximerar summan av koalitionernas värden, men ofta är antalet koalitionsstrukturer för stort för att möjliggöra ett uttömmande sökande efter den optimala. Dessutom är det NP-komplett att hitta den optimala koalitionsstrukturen. Men då, kan den koalitionsstruktur som finns via en partiell sökning garanteras att vara inom en gräns från optimal? Vi visar att ingen av de tidigare koalitionsstrukturalgoritmer kan etablera några bundna eftersom de söker färre noder än en tröskel som vi visar nödvändigt för att upprätta en gräns. Vi presenterar en algoritm som etablerar en snäv gräns inom denna minimal mängd sökning, och visar att någon annan algoritm skulle behöva söka strikt mer. Den fraktion av noder som behövs för att sökas närmar sig noll när antalet agenter växer. Om ytterligare tid återstår, vår när som helst algoritm söker vidare, och etablerar en gradvis lägre snäv gräns. Förvånansvärt nog, bara söka en till nod släpper gränsen på mitten. Som önskat sänker vår algoritm bundet snabbt tidigt, och uppvisar minskande avkastning till beräkning. Det överträffar också betydligt sina uppenbara utmanare. Slutligen visar vi hur man distribuerar den önskade sökningen över egenintresserade manipulativa medel. © 1999 Elsevier Science B.V. Alla rättigheter förbehållna. 0004-3702/99/$ -se huvudfrågan © 1999 Elsevier Science B.V. Alla rättigheter förbehållna. PII: S 0 0 0 4 -3 7 0 2 ( 9 9 ) 0 0 0 3 6 - 3 T. Sandholm et al. / Artificiell intelligens 111 (1999) 209-238
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. I REF ) studera problemet med att skapa en koalitionsstruktur.
Coalition Structure Generation with Worst Case Guarantees
{'venue': 'Artif. Intell.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}