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 [14], 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, minor-free and bounded degree graphs.
This paper ignored the game theoretic problem of coalitional stability. While the structures we find do maximize the welfare, they do so in a potentially unstable manner. When agents are selfish, and only care about their own utility, the coalition structure may be broken when some agents decide to form a different coalition, improving their own utility at the expense of others. It would be interesting to examine questions relating to solution concepts such as the core, the nucleolus or the cost of stability @cite_32 @cite_6 @cite_17 @cite_0 .
@cite_0 @cite_32 @cite_6 @cite_17
2115537584 2125363721 1540727845
A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the core --the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the cost of stability (CoS) as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures. Abstract : In RM 23, a proof was given that the nucleolus is continuous as a function of the characteristic function. This proof is not correct; the author, at least, does not know how to complete it. In the paper a correct proof for this fact is given. The proof is based on an alternative definition of the nucleolus, which is of some interest in its own right. (Author) One key question in cooperative game theory is that of coalitional stability. A coalition in such games is stable when no subset of the agents in it has a rational incentive to leave the coalition. Finding a division of the gains of the coalition (an imputation) lies at the heart of many cooperative game theory solution concepts, the most prominent of which is the core. However, some coalitional games have empty cores, and any imputation in such a game is unstable. We investigate the possibility of stabilizing the coalitional structure using external payments. In this case, a supplemental payment is offered to the grand coalition by an external party which is interested in having the members of the coalition work together. The sum of this payment plus the gains of the coalition, called the coalition's "adjusted gains", may be divided among the members of the coalition in a stable manner. We call a division of the adjusted gains a super-imputation, and define the cost of stability (CoS) as the minimal sum of payments that stabilizes the coalition. We examine the cost of stability in weighted voting games, where each agent has a weight, and a coalition is successful if the sum of its weights exceeds a given threshold. Such games offer a simple model of decision making in political bodies, and of cooperation in multiagent settings. We show that it is coNP-complete to test whether a super-imputation is stable, but show that if either the weights or payments of agents are bounded then there exists a polynomial algorithm for this problem. We provide a polynomial approximation algorithm for computing the cost of stability.