Winning coalitions in plurality voting democracies

In parliamentary voting, a plurality voting system is a system where each voter can vote for one party, and the seats in parliament are allocated to the parties dependent on (usually proportional to) the cast votes. If one party received the majority of the votes, then it can be considered the winner of the election. However, very often there is no majority party, and two or more parties need to cooperate and make an agreement to form a (majority) government. Although in such situations there is no party that can guarantee for itself to be in the government, and thus it is not immediately clear who is the winner of the election, usually immediately after the elections there is at least one party that claims to be the winner of the election. For instance, the party with the most votes/seats often declares itself as the winner of the election. But if other, smaller, parties form a majority coalition, then the party with the most votes might eventually be the ‘loser’. For example, if after election a right wing party received the most votes, but the left wing parties can form a majority coalition, then it might be that the largest, or most moderate, left wing party can be considered to be the winner of the election.

Typically, in such situations, whether a coalition is winning or losing might depend on the way how players outside the coalition are organized into coalitions. Therefore, in this paper, we frame debates about winners of an election in the setup of simple cooperative games in partition function form. We address the question if it is possible to assign weights to political parties that somehow measure who is the winner of an election. If that is possible, we say that the corresponding simple game supports a plurality voting democracy.

We introduce plurality games as a special type of simple games in partition function form. A classical simple game assigns to every coalition (i.e., subset of the player set) either a worth of one (if the coalition is winning) or zero (if the coalition is losing). In such a game, whether a coalition is winning or losing does not depend on the way how the players/parties outside the coalition are organized. This assumption is reasonable when we define a coalition to be winning if it has a majority, since in that case any coalition of the opposing parties is a minority coalition. However, in this paper we want to address the issue of determining the winner or strongest party in a coalitional configuration of parties, even when there is no majority coalition formed (yet). During the process of government formation, different potential compositions of government parties might be considered, and the parties trying to form a government use coalition formation with parties outside the current government negotiations in strengthening their arguments or bargaining positions.

Usually, in these cases, the strength of parties also depends on the way other parties form alliances, i.e., there are externalities of coalition formation in the sense that parties forming a coalition has impact on the strength of parties outside the coalition. Such situations can be modeled by simple games in partition function form, where a worth is assigned to every so-called embedded coalition being a pair consisting of a coalition and a partition that contains this coalition. The worth is one (respectively zero) if the corresponding coalition is winning (respectively losing) in the partition. We call such a game a plurality game, if in every partition there is at least one coalition that wins in the partition. So, winning does not necessarily mean that the coalition has a majority and can pass a bill, but simply that it is considered as the strongest in a given coalitional configuration as represented by the partition. For example, it is common practice that the party that got the most votes in an election is considered as a winner and takes the initiative to form a government. Although this does not imply that eventually this party will be in the government, it obviously gives the party an advantage as long as no coalitions are formed yet. On the other hand, it might be that a party that is not the largest, but has ideologically close parties that are big enough to form a majority coalition with, will eventually form a government, and thus can also be considered a winner after the elections. In that case there can be two (or even more) parties that are declared to be winner of the election.

In this paper, we assume plurality games to be monotonic, both with respect to a coalition as well as to a certain type of externalities regarding other coalitions. Specifically, we assume that (i) a winning coalition cannot become losing when it grows, and (ii) there are negative externalities of other coalitions growing in the sense that bigger outside coalitions give ‘more resistance’ and thus outside coalitions becoming bigger cannot turn a losing coalition into a winning one.¹

Within this model of (monotonic) plurality games, we study the possibility of assigning weights to players (parties) such that a winning coalition in a partition is always one that has the maximal sum of its players’ weights over all coalitions in the partition. If this is possible for a given game, then we call the game weighted and refer to the corresponding weights as supporting weights. In that case, we can say that the game supports a plurality voting democracy. In the following, we sometimes shortly speak about the weight of a coalition as being the sum of the weights of the players in the coalition. Notice that a game being weighted does not imply that, when two coalitions in a partition have maximal weight, then both are winning. It only requires that the winner should be one of the coalitions with maximal weight.

In this paper, an important role is played by decisive plurality games being plurality games, where each partition contains exactly one winning coalition. In Sect. 2, we illustrate the problem of assigning supporting weights to plurality games by providing an example of a five-player decisive plurality game which is not weighted. We start our investigation of finding plurality games that are weighted in Sect. 3, by showing that all games with at most four players are weighted. In Sect. 4, we show that a majority game (i.e., a plurality game such that the winner in every partition is a coalition of maximal size in the partition) with more than four players is weighted. We also define a notion of symmetry, and show that such symmetric majority games can only be supported by assigning equal weights to all players. Notice that, intuitively, not all players can be symmetric in a decisive plurality game, because for such a game exactly one singleton is winning in the partition that consists of all singletons. We refer to this special partition into singletons as the atomistic partition. It describes, for example, the situation directly after elections when no coalitions or alliances are formed yet.

The closest we can get to symmetry in a decisive plurality game is to require that all players but one (the winner in the atomistic partition) are symmetric. We call such games \((n-1)\)-symmetric and show in Sect. 5 that \((n-1)\)-symmetric decisive plurality games with an arbitrary number of players are weighted. For this, we define the power of the winner in the atomistic partition in a specific way, show how it shapes the structure of the possible candidates for a winning coalition in a partition, and explicitly use it in the construction of supporting weights.

Section 6 concludes the main part of the paper and provides an overview of the related literature. All proofs are collected in Appendix A (proofs from Sect. 3), Appendix B (proofs from Sect. 4), and Appendix C (proofs from Sect. 5).

All games we consider will be defined on a fixed and finite player set \( N=\left\{ 1,\ldots ,n\right\} \) with \(n\ge 2\), whose non-empty subsets are called coalitions. A collection \(\pi \) of coalitions is called a coalition structure if \(\pi \) is a partition of N, i.e., if all coalitions in \(\pi \) are non-empty, pair-wise disjoint, and their union is N. We denote by \(\mathcal {P}\) the set of all partitions (coalition structures) of N. For \(\pi \in \mathcal {P}\) and \(i\in N\), the notation \( \pi (i)\) stands for the coalition in \(\pi \) containing player i. The partition \(\pi ^{a}\in \mathcal {P}\) with \(\pi ^{a}(i)=\left\{ i\right\} \) for each \(i\in N\), is called the atomistic partition. A pair \(\left( S;\pi \right) \) consisting of a non-empty coalition \(S\subseteq N\) and a partition \(\pi \in \mathcal {P}\) with \(S\in \pi \) is called an embedded coalition. The set of all embedded coalitions is \(E=\left\{ \left( S;\pi \right) \in \left( 2^{N}{\setminus } \left\{ \emptyset \right\} \right) \times \mathcal {P}\mid S\in \pi \right\} \).

For partition \(\pi \in \mathcal {P}\) and set of players \(S\subset N\), we denote by \(\pi _{S}=\left\{ T\cap S\mid T\in \pi :T\cap S\ne \emptyset \right\} \) the partition of S induced by \(\pi \). Further, we will often write \(\{T_{1},\ldots ,T_{k},\pi _{S}\}\) for \(\{T_{1},\ldots ,T_{k},S_{1},\ldots ,S_{p}\}\) if \(\pi _{S}=\{S_{1},\ldots ,S_{p}\}\).

Simple games in partition function form   A simple game in partition function form is a pair \(\left( N,v\right) \), where the partition function \(v:E\rightarrow \left\{ 0,1\right\} \) is such that \(v\left( N;\left\{ N\right\} \right) =1\). An embedded coalition \(\left( S;\pi \right) \in E\) is winning in the game \( \left( N,v\right) \) if and only if \(v\left( S;\pi \right) =1\). Otherwise, it is called losing. We sometimes say that coalition S is winning in partition \(\pi \) when \((S;\pi )\) is a winning embedded coalition. The set of all winning embedded coalitions in the game v is denoted by \(E_{W}(v)\). Notice that this game form allows to model externalities of coalition formation. For instance, it can be that a coalition contained in two partitions \(\pi \) and \(\pi ^{\prime }\) is winning in \(\pi \) but losing in \( \pi ^{\prime }\). Since the player set N is fixed, we often write a simple game in partition function form \(\left( N,v\right) \) by its partition function v. We use the following notion of inclusion, borrowed from Alonso-Meijide et al. (2017): For \(\left( S^{\prime };\pi ^{\prime }\right) ,(S;\pi )\in E\), we say that \(\left( S^{\prime };\pi ^{\prime }\right) \) is weakly included in \(\left( S;\pi \right) \), denoted by \(\left( S^{\prime };\pi ^{\prime }\right) \subseteq (S;\pi )\), if (i) \(S^{\prime }\subseteq S\), and (ii) for each \( T\in \pi {\setminus } \left\{ S\right\} \), there exists \(T^{\prime }\in \pi ^{\prime }\) with \(T\subseteq T^{\prime }\). A game v is then defined as monotonic if \(\left( S^{\prime };\pi ^{\prime }\right) ,(S;\pi )\in E\) with \(\left( S^{\prime };\pi ^{\prime }\right) \subseteq (S;\pi )\) implies \(v\left( S^{\prime };\pi ^{\prime }\right) \le v(S;\pi )\). This monotonicity notion reflects (i) a nonnegative effect when a coalition grows, and (ii) an idea of negative externalities when players outside a coalition form larger coalitions. In particular, it implies that when a coalition is winning in a partition, then it is winning in every finer partition that contains this coalition. In other words, the idea expressed here is that in a finer partition there is ‘less resistance’ against the winning coalition. Clearly, a winning coalition can become losing in a coarser partition since other players forming coalitions might give a ‘stronger resistance’ against the winning coalition, or make the winning coalition more likely to ‘break down’.

Plurality games and supporting weights We call a simple game in partition function form v a plurality game if (i) it is monotonic, and (ii) for each \(\pi \in \mathcal {P}\) we have \(v(S;\pi )=1\) for at least one \(S\in \pi \). A plurality game v is decisive, if for each \(\pi \in \mathcal {P}\) we have that \(v(S;\pi )=1\) for exactly one \(S\in \pi \). A plurality game v is weighted, if there exists a weight vector \(w\in X_{+}^{N}:=\left\{ w\in \mathbb {R} _{+}^{N}\mid \Sigma _{i\in N}w_{i}=1\right\} \) such that for each \((S;\pi )\in E\), \((S;\pi )\in E_{W}(v)\) implies \(w(S):=\Sigma _{i\in S}w_{i}\ge \Sigma _{i\in T}w_{i}:=w(T)\) for each \(T\in \pi \). We call w a supporting weight vector for the plurality game. In words, a plurality game is weighted if there exist nonnegative weights for the players, such that if an embedded coalition is winning, then the sum of the weights of the players in the winning coalition is maximal among the coalitions in the corresponding partition.

The example given below illustrates that a decisive plurality game need not be weighted.

In view of the above example, in what follows we first concentrate on decisive plurality games with at most four players (Sect. 3), and then consider additional restrictions on games with an arbitrary number of players guaranteeing that these games are weighted (Sects. 4 and 5).

We start our analysis by considering decisive plurality games with at most four players. A first reason to start by considering four player games, is that these are very illustrative, and hint to conditions for games with more than four players to be weighted.

A second reason to start with four player games is that, also for standard simple games (simple games without externalities), four player games received considerable attention. For instance, von Neumann and Morgenstern (1944) show that all simple games with less than four players, all proper or strong simple games with less than five players, and all constant sum games with less than six players have voting representations, i.e., they can be represented by weights assigned to the players. However, there are constant-sum games with six players for which representative weights do not exist. In their study of rough weightedness of small games, Gvozdeva and Slinko (2011) show that all games with at most four players, all strong or proper games with at most five players, and all constant-sum games with at most six players are roughly weighted. Finally, it is worth mentioning that Shapley (1962) also explicitly analyses games with four or less players when discussing several properties of weighted majority games. In particular, he studies homogeneous games where the weights can be assigned in such a way that all minimal winning coalitions have the same weight.

For decisive games with at most four players, it turns out that the winning coalition in a partition is either one of maximal size, or the one containing the winner in the atomistic partition. In our results, for convenience and without loss of generality, we will often assume that player 1 is the winner in the atomistic partition of a decisive plurality game.

The above conclusion is very helpful for the proof of our main result in this section.

The proofs of Proposition 1 and Theorem 1 can be found in Appendix A.

Proposition 1 suggests that, if the winning coalition does not contain the winner in the atomistic partition, then it is only the size of a coalition that matters. For an arbitrary number of players, this fact invites us to consider the following type of majority games.

A plurality game v is a majority game if for all \(\left( S;\pi \right) \in E\), every winning coalition is one of maximal size in the partition, i.e., \(\left( S;\pi \right) \in E_{W}(v)\) implies \(\left| S\right| \ge \left| T\right| \) for each \(T\in \pi \). It is easy to verify that \(w=\left( \frac{1}{n},\frac{1}{n},\ldots ,\frac{1}{n} \right) \) is a supporting weight vector for every majority game.

Of special interest are majority games where the players exhibit some kind of symmetry. For simple games in partition function form, several symmetry notions can be defined. Two possibilities are the following. Given a plurality game v, we say that two players \(i,j\in N\) are²Notice that in the definitions above, we can switch the roles of players i and j. A plurality game v is switch-symmetric (respectively grow-symmetric) if all players³ are switch-symmetric (respectively grow-symmetric) in v.

Each of these symmetry notions expresses an independence idea. Two players being switch-symmetric in a game requires that a winning coalition that contains one of them but not the other player, remains winning in the partition obtained by exchanging the places of these two players. On the other hand, grow-symmetry requires that for a winning and a losing coalition not containing both players, the winning coalition should remain winning if we add either one of these players to the winning, and the other to the losing coalition.

Our next result provides a characterization of switch-symmetric majority games and shows that, on the class of majority games, switch-symmetry implies grow-symmetry.⁴

The proofs of this section can be found in Appendix B.

It is worth mentioning that not every grow-symmetric majority game is also switch-symmetric, as illustrated by the following example.

If we require a majority game to be switch-symmetric, then the equal weight vector used to prove Theorem 2, is the only one making the game weighted.

As one can see, this result is clearly driven by the fact that, in a switch-symmetric majority game, all largest coalitions in a partition are winning in it.

We have defined decisive plurality games as games where there is exactly one winning coalition in each partition. Since this implies that there is a unique winner in the atomistic partition, no decisive plurality game is switch-symmetric. The ‘most symmetric’ a game can be is if all other players are symmetric. Therefore, we call a decisive plurality game \((n-1)\)- switch-symmetric if all players but one (the winner in the atomistic partition) are switch-symmetric in the game. We study the impact of this restriction on the game’s support. Due to the decisiveness of v, the following result is immediate.

Recall from Proposition 2, that for the case of majority games, grow-symmetry is implied by switch-symmetry. We define a decisive plurality game v to be \((n-1)\)-grow-symmetric if all players but one (the winner in the atomistic partition) are grow-symmetric in v, and show that \( (n-1)\)-switch-symmetry and \((n-1)\)-grow-symmetry are independent properties.

For this, let us first show that \((n-1)\)-switch-symmetry does not imply \( (n-1)\)-grow-symmetry.

Our next example shows that \((n-1)\)-grow-symmetry does not imply \((n-1)\)-switch-symmetry.

In what follows, we call a decisive plurality game v\((n-1)\)-symmetric decisive plurality games turn out to be weighted (Theorem 3). We show this by proving important implications (stated in Propositions 4-6) on the winning embedded coalitions in such games. In these results, we also explicitly state the type of \((n-1)\)-symmetry (i.e., \((n-1)\)-symmetry, \( (n-1)\)-switch-symmetry, or \((n-1)\)-grow-symmetry) which is used in the corresponding proofs. All proofs of this section are provided in Appendix C.

We start by showing that in \((n-1)\)-switch-symmetric games, a winning coalition in a partition either contains the winner in the atomistic partition, or has strictly more players than any other coalition in the partition.

This proposition gives as a corollary that in a partition having two or more coalitions of maximal size, the winning coalition should contain the winner in the atomistic partition.

Define \(\mathcal {P}_{1}=\{\pi \in \mathcal {P}\mid \{1\}\in \pi \}\) as the collection of those partitions that contain singleton \(\{1\}\). In what follows, we make use of the power \(p_{1}(v)\) of player 1 in a decisive plurality game v with \(v\left( \left\{ 1\right\} ;\pi ^{a}\right) =1\), and define it asthat is, it is the size of a largest coalition that loses against \( \left\{ 1\right\} \) in some partition from \(\mathcal {P}_{1}\). We denote by \( \mathcal {P}^{*}\) the set of all partitions in which there is only one largest coalition that does not contain player 1. For \(\pi \in \mathcal {P} ^{*}\), \(S_{\pi }\) stands for the largest coalition in \(\pi {\setminus } \left\{ \pi (1)\right\} \).

Our next result explains the crucial role of \(p_{1}(v)\) in determining the winning coalitions in the partitions contained in \(\mathcal {P}^{*}\).

Corollary 1 and Proposition 6 allow for a complete characterization of the winning embedded coalitions in \((n-1)\)-symmetric games. For \(\pi \in \mathcal {P}\), the coalition \(\pi (1)\) is winning in \(\pi \) when either \(\pi {\setminus } \left\{ \pi (1)\right\} \) contains at least two largest coalitions, or the unique largest coalition in \(\pi {\setminus } \left\{ \pi (1)\right\} \) is smaller than the threshold level \(p_{1}(v)+\left| \pi (1)\right| \). Otherwise, it is the unique largest coalition which wins in the partition \(\pi \). Notice that, in the two cases where \(\pi (1)\) is winning in \(\pi \), a coalition \(S\in \pi \) with \(\left| S\right| >\left| \pi (1)\right| \) may exist; so, it is not necessarily that a largest coalition wins in a partition.

The value \(p_{1}(v)\) also plays an important role in the following main result on \((n-1)\)-symmetric plurality games, which gives explicit supporting weights for a decisive \((n-1)\)-symmetric plurality game.

The following example sheds light on how the results in this section lead to a plurality game being weighted.

Let us finally remark that decisive plurality games are always weighted in case there are no externalities. We say that a plurality game v is externality-free if \(v(S;\pi )=v(S;\pi ^{\prime })\) holds for all \( S\subseteq N\) and for all partitions \(\pi ,\pi ^{\prime }\in \mathcal {P}\) such that \(S\in \pi \cap \pi ^{\prime }\).

This proposition makes clear that problems with decisive plurality games being not weighted arise from the existence of (negative) externalities.

In our study about the possibility of assigning weights to players in simple partition function form games, we have presented classes of games which do allow for a weighted representation. Moreover, the support of the corresponding games was shown to crucially shape the set of possible winning coalitions in a partition and thus, to shed light on which coalitions are most powerful in the presence of (negative) externalities. This naturally places our work within the strands of literature devoted to the numerical representation of standard simple games as well as to the study of general partition function form games.

The first strand of literature is mainly concerned with the question whether it is (always) possible to represent a standard simple game as a weighted majority game, that is, to find non-negative weights and a positive real number (quota) such that a coalition is winning in the simple game if and only if the combined weights of its members weakly exceeds the quota. As shown by von Neumann and Morgenstern (1944), not all simple games do allow for such weighted majority representation. The question of finding properties that characterize weighted games within the class of simple games was then naturally posted by Isbell (1956, (1958), and answered by Elgot (1961) and Taylor and Zwicker (1992). More precisely, Taylor and Zwicker (1992) characterize weighted voting in terms of the ways in which coalitions can gain or lose by trading among themselves, while Hammet et al. (1981) and Einy and Lehrer (1989) answer the above question by using results about separating convex sets. Peleg (1968) and Sudhölter (1996) show for the case of (constant-sum) weighted majority games that, correspondingly, the nucleolus and the modified nucleolus induce a representation of the game.

If a standard simple game does not allow for a weighted representation, then one might consider rough weights (cf. Taylor and Zwicker 1999). A simple game is roughly weighted if there exist weights and a threshold such that every coalition with the sum of its players’ weights being above (respectively below) the threshold is winning (respectively losing). Again, not all standard simple games turn out to be roughly weighted. Gvozdeva and Slinko (2011) give necessary and sufficient conditions for a simple game to have rough weights. Related to the issue of non-weightedness of games, Carreras and Freixas (1996) and Freixas and Molinero (2009) investigate complete simple games being simple games behaving in some respects as weighted simple games.

All the papers cited above deal with standard simple games, while the focus of our work is on the weighted representation of plurality games which we defined as special type of simple games in partition function form. To the best of our knowledge, we are the first to study and provide conditions assuring weighted representations of such games.

The second strand of related literature deals with general partition function form games as initiated by the seminal works of Thrall (1962) and Thrall and Lucas (1963), and recently surveyed by Koczy (2018). Besides the investigation of general properties of such games (e.g., Lucas and Marcelli 1978; Maskin 2003; Hafalir 2007), there are two main issues of simultaneous interest in the corresponding works: which coalitions will form (cf. Ray 2007), and how the coalitional worths will be allocated to their members. For instance, de Clippel and Serrano (2008) separate the intrinsic payoffs from those due to the externalities of coalition formation. However, the main focus in that literature has been on extending the Shapley value for games with externalities (e.g., Myerson 1977; Gilboa and Lehrer 1991; Albizuri et al. 2005; Macho-Stadler et al. 2007, de Clippel and Serrano (2008); McQuillin (2009); Dutta et al. (2010); Grabisch and Funaki (2012)) and on extending different power indices to the class of simple games with externalities (e.g., Bolger 1986; Alonso-Meijide et al. 2017; Alvarez Mozos et al. 2017).

Although the study of power indices for simple partition function form games was out of the scope of this paper, we nevertheless used a notion of power (for the winner in the atomistic partition) in order to derive our results with respect to \((n-1)\)-symmetric plurality games. In follow-up research, we intend to generalize this notion as to apply to each player, to investigate in detail its properties, and to axiomatically characterize it.