Abstrakt. Vi anser att problemet med att hitta den optimala koalitionsstrukturen i viktade Graph Games (WGGs), en enkel begränsad representation av koalitionsspel [12]. Agenterna i sådana spel är hörn av grafen, och värdet av en koalition är summan av vikterna av kanterna närvarande mellan koalitionsmedlemmar. Den optimala koalitionsstrukturen är en delning av agenterna till koalitioner, som maximerar summan av verktyg som erhållits av koalitionerna. Vi visar att hitta den optimala koalitionsstruktur är inte bara svårt för allmänna grafer, men är också intractable för begränsade familjer såsom planar grafer som är tillgängliga för många andra kombinatoriska problem. Vi ger sedan algoritmer med konstant faktor approximationer för planar, mindre fria och avgränsade grad grafer.
Oberoende, REF visade att problemet koalitionsstrukturgenerering är intractable för planar grafer med kantsumma värdering funktion, och även gav algoritmer med konstant faktor approximationer för planar, mindre fria och avgränsade grad grafer.
Optimal Coalition Structures in Graph Games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}