In AAAI Conference on Artificial Intelligence (AAAI), July 2013.

Abstract

Representation languages for coalitional games are a key research
area in algorithmic game theory. There is an inherent
tradeoff between how general a language is, allowing it
to capture more elaborate games, and how hard it is computationally
to optimize and solve such games. One prominent
such language is the simple yet expressive Weighted
Graph Games (WGGs) representation (Deng and Papadimitriou
1994), which maintains knowledge about synergies between
agents in the form of an edge weighted graph.

We consider the problem of finding the optimal coalition
structure in WGGs. The agents in such games are vertices in
a graph, and the value of a coalition is the sum of the weights
of the edges present between coalition members. The 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, minorfree
and bounded degree graphs.