Optimal Coalition Structures in Graph Games

Details Optimal Coalition Structures in Graph Games Optimal Coalition Structures in Graph Games

2011-08-26

arxiv.org/abs/1108.5248v1

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Coalition Structures in Graph Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Coalition Structures in Graph Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Coalition Structures in Graph Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-501806