Abstrakt. Detta dokument presenterar ett nytt sätt att formalisera Coalition Structure Generation problem (CSG), så att vi kan tillämpa begränsning optimering tekniker för det. Att bilda effektiva koalitioner är en stor forskningsutmaning inom AI och multiagentsystem. CSG innebär att dela upp en uppsättning agenter i koalitioner så att det sociala överskottet maximeras. Traditionellt är input av CSG-problemet en svart-box funktion som kallas en karakteristisk funktion, som tar en koalition som en input och returnerar värdet av koalitionen. Som ett resultat, tillämpa begränsning optimering tekniker på detta problem har varit ogenomförbar. De karakteristiska funktioner som ofta förekommer i praktiken kan dock kortfattat representeras av en uppsättning regler, snarare än en enda svart-box-funktion. Då kan vi lösa CSG-problemet mer effektivt genom att tillämpa begränsningsoptimeringsteknik på den kompakta representationen direkt. Vi presenterar nya formaliseringar av CSG-problemet genom att använda nyutvecklade kompakta representationssystem för karakteristiska funktioner. Vi karakteriserar först CSG:s komplexitet inom ramen för dessa representationssystem. I detta sammanhang drivs komplexiteten mer av antalet regler än av antalet ombud. Dessutom, som ett första steg mot att utveckla effektiva begränsning optimering algoritmer för att lösa CSG-problemet, utvecklar vi blandade heltal programmering formuleringar och visar att en off-the-shelf optimering paket kan prestera någorlunda bra, dvs, det kan lösa fall med några hundra agenter, medan state-of-the-art algoritm (som inte använder kompakta representationer) kan lösa fall med upp till 27 agenter.
Ett alternativ till CSG-problemet är att använda kompakta representationssystem för värderingsfunktioner som föreslås i REF.
Coalition Structure Generation Utilizing Compact Characteristic Function Representations
{'venue': 'CP', 'journal': None, 'mag_field_of_study': ['Computer Science']}