Fair stable sets of simple games
Introduction
Simple games—in which every coalition of players either wins or loses—represent political structures in which “power” is the fundamental driving force. For example, a legislature in which any two of three parties have enough parliamentary seats to form a new government can be represented by the three-player simple majority game.2
A fair stable set of a simple game is a set of distributions of power among the players that (i) satisfies certain internal and external stability properties, and (ii) does not discriminate among players based on their names. For example, the unique fair stable set of the three-player simple majority game consists of the three possible outcomes in which power is divided equally among two of the three players; intuitively, this stable set reflects that—when all coalitions obtain the same surplus from forming government—the governing coalition is vulnerable when one of its parties receives less than the other.3
In 1978, Lloyd Shapley asked which simple games admit a fair stable set. Rabie (1985) showed that the answer is not “all,” but—to the best of my knowledge—the set of simple games that admit a fair stable set has not been characterized.4
In this article I describe a method to construct fair stable sets of compound simple games from fair stable sets of their quotient and components, and I discuss how this method contributes to the characterization of the set of simple games that admit a fair stable set.
Compound simple games are built out of component games, which are, in turn, “players” of a quotient game. An example of a compound simple game is the multimillion-person game “US Presidential Election”—whose quotient is a weighted majority game (the Electoral College), and whose components are symmetric majority games of assorted sizes (the electorates of the 50 states and the District of Columbia). Sums of games—whose winning coalitions are exactly those that win in at least one of these games—and products of games—whose winning coalitions are exactly those that win in all of these games—are particular classes of compound games. For example, the game “US Congress” can be represented as the product of two simple majority games (the Senate and the House of Representatives). A game is prime if it does not have any non-trivial compound representation.5
The main result of this article is closely related the composition theorem of Shapley (1963c). To emphasize this connection, I quote his verbal description of his result (Shapley, 1963c, page 269) adding words in italics that transform it into a description of my result6:
If one first divides the proceeds of a regular7 [compound simple] game among the components, in accordance with a fair [stable set] of the quotient, and then subdivides them among the players of each component according to a scaled-down fair [stable set] of that component, using isomorphic fair stable sets for isomorphic components, then the resulting set of imputations is a fair [stable set] of the compound.
This new composition result combined with Shapley's (1967) “unique factorization” theorem8 reveals that the set of simple games that admit a fair stable set includes all simple games whose factors—or prime quotients in their unique factorization—are in . In other words, a game that does not admit a fair stable set has at least one factor that does not admit a fair stable set. It is an open question whether the converse holds; if it does, the composition result presented in this article implies that characterizing the set of prime games in is equivalent to characterizing the set .
The rest of this article is organized as follows. In section 2 I provide background material: The definitions of simple game, compound simple game, committee and stable set, and Shapley's unique factorization and composition theorems. In section 3 I define what it means for a stable set to be fair, and I state and prove the main result of this article: A composition theorem that shows how to construct fair stable sets of compound simple games from fair stable sets of their quotient and components. I conclude in section 4 by discussing the implications of this result for the characterization of the set of simple games that admit a fair stable set, and for the problem of aggregation in the theory of fair stable sets.
Section snippets
Preliminaries
In this section I review the two fundamental results of Lloyd Shapley that this article builds on. In subsection 2.1 I review the definitions of simple game, compound simple game, dual of a game and committee of a game, and I present the unique factorization theorem of Shapley (1967). In subsection 2.2 I review the definition of stable set of a game and the composition theorem presented in Shapley (1963c).
Fair stable sets of compound simple games
Fair stable sets are those that do not discriminate among players based on their names. Not all stable sets are fair; for example, the stable set of the three-player majority game depicted in Fig. 2 is not fair, since it discriminates among its three non-dummy players (who play exactly the same role in this game). In subsection 3.1 I formally describe what it means for a stable set to be fair, and in subsection 3.2 I provide the main result of this article: A composition theorem that shows how
Conclusion
Lloyd Shapley made fundamental contributions to the theory of simple games. In particular, he was the first to define and study compound simple games. One of the reasons he thought compound simple games are interesting is that they allow us to study the problem of aggregation of players in game theory. In his own words (Shapley, 1963c, pages 4–5):
An important question in the application of n-person game theory is the extent to which it is permissible to treat firms, committees, political
References (26)
- et al.
Farsighted coalitional stability in TU-games
Math. Soc. Sci.
(2008) - et al.
The stability of hedonic coalition structures
Games Econ. Behav.
(2002) von Neumann–Morgenstern stable sets
- et al.
Rational expectations and farsighted stability
Theoretical Econ.
(2017) The Theory of Social Situations: An Alternative Game-Theoretic Approach
(1990)An equilibrium-point interpretation of stable sets and a proposed alternative definition
Manage. Sci.
(1974)- et al.
Stable sets in majority pillage games
Int. J. Game Theory
(2015) - Lucas, W., 1978. International Workshop on Game Theory (4th): Multiperson Game Theory and Its Applications held at...
A game with no solution
Bull. Amer. Math. Soc.
(1968)- et al.
Games and Decisions: Introduction and Critical Survey
(1957)
von Neumann–Morgenstern farsightedly stable sets in two-sided matching
Theoretical Econ.
Semi-symmetric solutions for (n, k) games
Int. J. Game Theory
A simple game with no symmetric solution
SIAM J. Algebraic Discrete Methods
Cited by (2)
Stable cores in information graph games
2022, Games and Economic BehaviorCitation Excerpt :There is a recent characterization of those coalitional games with a stable core in Grabisch and Sudölter (2021) and, before that, a stronger notion of the stable core is characterized by Jain and Vohra (2010). Stable sets have been found on several classes of games, such as assignment games (Núñez and Rafels, 2013), linear production games (Rosenmüller and Shitovitz, 2000, 2010), pillage games (MacKenzie et al., 2015), patent licensing games (Hirai and Watanabe, 2018), matching problems (Herings et al., 2017), tournaments (Brandt, 2011), voting games (Talamàs, 2018), and exchange economies (Graziano et al., 2015, 2017). Non-cooperative foundations of stable sets have been shown by Anesi (2010); Diermeier and Fong (2012).
Stable Cores in Information Graph Games
2021, SSRN
- 1
I thank Benjamin Golub for encouraging me to write this article; his detailed feedback has greatly improved it. I also thank Aubrey Clark, Jerry Green, Rajiv Vohra and the participants of Harvard's Games and Markets and Contracts and Organizations seminars for useful comments. Finally, I thank the editor and an anonymous referee for useful suggestions. All errors are my own.