Optimal coalition structures in graph games

Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, Optimal Coalition Structures in Graph Games, ArXiv, 2011.

Report | Published
Author
; ; ;
Department
Abstract
We consider the problem of finding the optimal coalition structure in \emph{Weighted Graph Games (WGGs)}, a simple restricted representation of coalitional games [Deng, Papadimitriou, Math. OR 1994]. The agents in such games are vertices of the graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The \emph{optimal coalition structure} is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minor-free and bounded degree graphs.
Publishing Year
Date Published
2011-08-26
forms.report.field.publication.label
CoRR: Computing Research Repository
Issue
Arxiv:1108.5248
IST-REx-ID

Cite this

Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures in Graph Games. ArXiv; 2011.
Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2011). Optimal coalition structures in graph games. CoRR: Computing Research Repository. ArXiv.
Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam. Optimal Coalition Structures in Graph Games. CoRR: Computing Research Repository. ArXiv, 2011.
Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, Optimal coalition structures in graph games, no. Arxiv:1108.5248. ArXiv, 2011.
Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2011. Optimal coalition structures in graph games, ArXiv,p.
Bachrach, Yoram, et al. “Optimal Coalition Structures in Graph Games.” CoRR: Computing Research Repository, no. Arxiv:1108.5248, ArXiv, 2011.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar