<figure><img src="image_1.png" /></figure>

HAL
open science

Power in plurality games

René van den Brink, Dinko Dimitrov, Agnieszka Rusinowska

► To cite this version:

René van den Brink, Dinko Dimitrov, Agnieszka Rusinowska. Power in plurality games. 2024. halshs-04917809

HAL Id: halshs-04917809

https://shs.hal.science/halshs-04917809v1

Submitted on 28 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CES

Centre d'Économie de la Sorbonne
UMR 8174

Power in plurality games

René Van Den BRINK, Dinko DIMITROV, Agnieszka RUSINOWSKA

2024.14
# Power in plurality games

René van den Brink

Department of Economics and Tinbergen Institute, VU University
De Boelelaan 1105, 1081 HV Amsterdam, The Netherlands

Email: j.r.vanden.brink@vu.nl

Dinko Dimitrov*

Chair of Economic Theory, Saarland University
Campus C3 1, 66123 Saarbrücken, Germany

Email: dinko.dimitrov@mx.uni-saarland.de

Agnieszka Rusinowska

Centre d'Economie de la Sorbonne, CNRS – Paris School of Economics
Université Paris 1 Panthéon Sorbonne

106-112 Bd de l'Hôpital, 75647 Paris Cedex 13, France
Email: agnieszka.rusinowska@univ-paris1.fr

December 13, 2024

## Abstract

Simple games in partition function form are used to model voting situations where a coalition being winning or losing might depend on the way players outside that coalition organize themselves. Such a game is called a plurality voting game if in every partition there is at least one winning coalition. In the present paper, we introduce a power index for this class of voting games and provide an axiomatic characterization. This power index is based on equal weight for every partition, equal weight for every winning coalition in a partition, and

<footnote>*Corresponding author.</footnote>
equal weight for each player in a winning coalition. Since some of
the axioms we develop are conditioned on the power impact of losing
coalitions becoming winning in a partition, our characterization heav-
ily depends on a new result showing the existence of such elementary
transitions between plurality voting games in terms of single embed-
ded winning coalitions. The axioms restrict then the impact of such
elementary transitions on the power of different types of players.

JEL Classification: C71, D62, D72

Keywords: axiomatization, power index, plurality game, winning coalition

# 1 Introduction

In a simple game in partition function form, 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 that partition. So, in this case, winning does
not necessarily mean that the coalition has a majority and can pass a bill,
but simply that it is the strongest in a given coalitional configuration as
represented by the partition.

Plurality games were introduced in van den Brink et al. (2021) and can
be used to analyze parliamentary situations where (i) several (coalitions of)
parties can consider themselves as the winner after a parliamentary election,
and (ii) whether a coalition of parties considers itself as winning or losing
might depend on the way that other parties organize themselves in coalitions.
To illustrate (i), usually the biggest party after an election declares itself the
winner. However, if this party does not belong to the ideological (e.g. left or
right wing) majority then also a majority consisting of ideological opponents
might consider themselves as winner. To illustrate (ii), whether the biggest
party is a winner or not might depend on whether the ideological opposing
parties form a coalition or not.

We assume plurality games to be *monotonic*, both with respect to a coali-
tion 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 such coalitions becoming bigger cannot turn a losing coalition into a winning one. This reflects that in a finer partition, there is ‘less resistance’ against the winning coalition.

Whereas in van den Brink et al. (2021) the focus is mainly on the representability of these games by party weights, the current paper studies power distributions in plurality voting games. Specifically, we introduce and axiomatize a power index for this class of games. In the formulation of our axioms, we utilize the power impact of losing embedded coalitions becoming winning in a partition; that is, our axiomatization heavily depends on a new result describing elementary transitions between plurality voting games in terms of single embedded winning coalitions. Specifically, we show that in every plurality voting game with at least one losing embedded coalition, there is always a losing embedded coalition that can be turned into a winning one without affecting the monotonicity of the game.

The rest of the paper is organized as follows. In the next section we introduce the basic ingredients of plurality games as a special class of simple games in partition function form. Section 3 starts with the formal definition of a power index and presents the mentioned useful result (Proposition 1) concerning transitions between plurality games in terms of single winning embedded coalitions. These transitions are correspondingly used as to formulate our five axioms uniquely characterizing the proposed power index (Theorem 1). We conclude with some final remarks in Section 4. The Appendix contains all proofs.

## 2 Setup

We consider a finite set $N$ of players. Each non-empty subset is called a *coalition*. A collection $\pi$ of coalitions is 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) = \{i\}$ for each $i \in N$, is called the *atomistic partition*. The notation $(T_1, T_2, \dots, T_k, \pi^a)$ stands for the partition of $N$ consisting of the coalitions $T_1$ to $T_k$ and all players in $N \setminus (T_1 \cup T_2 \cup \dots \cup T_k)$ being singletons. When, for instance, $k=1$ and $T_1 = \{i,j,l\}$, we slightly abuse
notation and write $(ij\ell, \pi_{-}^{a})$ instead of $({i, j, \ell}, \pi_{-}^{a})$. A pair $(S; \pi)$ 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 = \{(S; \pi) \in (2^N \setminus \{\emptyset\}) \times \mathcal{P} \mid S \in \pi\}$. For partition $\pi \in \mathcal{P}$ and set of players $S \subset N$, we denote by $\pi_S = \{T \cap S \mid T \in \pi : T \cap S \neq \emptyset\}$ the partition of $S$ induced by $\pi$. Further, we will often write $\{T_1, \dots, T_k, \pi_S\}$ for $\{T_1, \dots, T_k, S_1, \dots, S_p\}$ if $\pi_S = \{S_1, \dots, S_p\}$.

A simple game in partition function form is a pair $(N, v)$, where the partition function $v: E \to \{0,1\}$ is such that $v(N; \{N\}) = 1$. An embedded coalition $(S; \pi) \in E$ is called *winning* in the game $(N, v)$ if and only if $v(S; \pi) = 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)$, while $E_W^\pi(v) = \{S \in \pi : (S; \pi) \in E_W(v)\}$ stands for the set of all coalitions which are winning in $\pi$.

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'$ is winning in $\pi$ but losing in $\pi'$. Since the player set $N$ is fixed, we often write a simple game in partition function form $(N, v)$ by its partition function $v$. We use the following notion of inclusion, borrowed from Alonso-Meijide et al. (2017): For $(S'; \pi')$, $(S; \pi) \in E$, we say that $(S'; \pi')$ is weakly included in $(S; \pi)$, denoted by $(S'; \pi') \subseteq (S; \pi)$, if (i) $S' \subseteq S$, and (ii) for each $T \in \pi \setminus \{S\}$, there exists $T' \in \pi'$ with $T \subseteq T'$. A game $v$ is then defined as *monotonic* if $(S'; \pi')$, $(S; \pi) \in E$ with $(S'; \pi') \subseteq (S; \pi)$ implies $v(S'; \pi') \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'.

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$. We assume that the player set $N$ is fixed and of size<fnref n="1" /> $n \ge 3$, and

<footnote n="1">¹Notice that, when $n = 2$, whether an embedded coalition is winning or losing in a</footnote>
identify a plurality game by its partition function. The set of all plurality
games on the player set $N$ is denoted by $G^N$.

3 Axioms on power indices and characteriza-
tion result

A power index for plurality games is a mapping $f : G^N \to \mathbb{R}_+^n$ satisfying $\sum_{i \in N} f_i(v) = 1$ for each $v \in G^N$. We interpret the real number $f_i(v) \in [0, 1]$ as the power of player $i$ in the game $v$.

The axioms we introduce in this section concern implications when the
only difference between two plurality games is a single winning embedded
coalition. Hence, the first question we have to answer is if for every plurality
game that has at least one losing embedded coalition, there is a losing embed-
ded coalition such that turning it into a winning one, we still have a plurality
game; specifically, monotonicity requires that the new winning coalition is
also winning against ‘less resistance’. Our first result whose proof is relegated
to the Appendix, answers this question in the positive.

**Proposition 1** Let $v \in G^N$ be such that $|E_W(v)| < |E|$. Then there exist $(S; \pi) \in E \setminus E_W(v)$ and $v' \in G^N$ such that $E_W(v') = E_W(v) \cup \{(S; \pi)\}$.

In other words, starting from any plurality game in which not all em-
bedded coalitions are winning, there is always a path of games leading to
the unique game in which all embedded coalitions are winning; along such a
path, each next game differs from its direct predecessor only by one winning
embedded coalition.

Let us now introduce the requirements we impose on a power index by
using the following additional notation. For $(S; \pi) \in E$, any two games
$v, v' \in G^N$ with $E_W(v') = E_W(v) \cup \{(S; \pi)\}$, and any $T \subseteq N$, we set
$\Delta_i^f(v, v') = f_i(v') - f_i(v)$ and $\Delta_T^f(v, v') = \sum_{i \in T} \Delta_i^f(v, v')$. That is, $\Delta_i^f(v, v')$
displays the change in the power of player $i \in N$ (as measured by $f$) when a
single embedded coalition which is losing in $v$ becomes winning in $v'$. Corre-
spondingly, $\Delta_T^f(v, v')$ stands for the change in the power of coalition $T$. For
$S, T \in \pi$, we finally set $\Delta_{ST}^f(v, v') = \Delta_S^f(v, v') - \Delta_T^f(v, v')$ saying how far
apart are the power change in $S$ and the power change in $T$ when $S$ becomes
the new winning coalition in the partition $\pi$.

<footnote>partition is in a trivial way independent of how the rest of the players are organized. This
is the reason for considering only plurality games with at least three players.</footnote>
We are ready now to present our axioms.

*Unanimity (U):* For all $v \in \mathcal{G}^N : E_W(v) = E$ implies $f_i(v) = f_j(v)$ for all $i, j \in N$.

*Internal Impact (II):* For all $v, v' \in \mathcal{G}^N : E_W(v') = E_W(v) \cup \{(S; \pi)\}$ implies $\Delta_i^f(v, v') = \Delta_j^f(v, v')$ for all $i, j \in T \in E_W^\pi(v')$.

*External Impact (EI):* For all $v, v' \in \mathcal{G}^N : E_W(v') = E_W(v) \cup \{(S; \pi)\}$ implies $\Delta_Q^f(v, v') = \Delta_R^f(v, v')$ for all $Q, R \in E_W^\pi(v)$.

*Null Impact (NI):* For all $v, v' \in \mathcal{G}^N : E_W(v') = E_W(v) \cup \{(S; \pi)\}$ implies $\Delta_i^f(v, v') = 0$ for all $i \in H \in \pi \setminus E_W^\pi(v')$.

*Power Difference (PD):* For all $v, v' \in \mathcal{G}^N : E_W(v') = E_W(v) \cup \{(S; \pi)\}$ implies $\sum_{T \in E_W^\pi(v)} \Delta_{ST}^f(v, v') = \frac{1}{|P|}$.

Unanimity requires equal power in case all embedded coalitions are winning in the corresponding game and thus, it can be seen as a weak symmetry axiom.

Internal Impact requires that a losing embedded coalition becoming winning (i) has the same impact on the powers of the players in that winning coalition and (ii) for each other winning coalition in the corresponding partition (i.e., the partition that contains this new winning coalition) it also has the same impact on the power of the players inside each such winning coalition. Part (i) can be seen as some kind of Myerson (1977a) fairness applied to this game model<fnref n="2" />. Part (ii) of this axiom extends this idea also to players in other winning coalitions in the corresponding partition since also from the perspective of each of them the situation changed in a 'symmetric' way.

External Impact requires that the impact of a losing embedded coalition becoming winning is the same for each other winning coalition in the corresponding coalition in the sense that the sum of the powers of all players in each such winning coalition changes by the same amount. This can also be seen as a kind of fairness as above, but then applied on the coalition level.

Null Impact is a rather strong axiom that requires that a losing embedded coalition becoming winning has no effect on the powers of the players in losing

<footnote n="2">²Myerson (1977a)'s fairness is introduced for communication graph games and requires that breaking a link between two players in a communication graph has the same impact on the payoff of these two players. Notice that we apply fairness to a coalition that might contain more than two players, and in this respect our axiom looks more similar to the fairness in Algaba et al. (2001) applied with respect to union stable systems where a link (called support) might contain more than two players.</footnote>
coalitions in the corresponding partition. Although using a similar argument as the fairness criteria mentioned above it seems reasonable that within each such losing coalition the changes in power are the same, requiring the effect to be zero is an extreme case. However, if we consider the partition as a coalition structure (cf. Aumann and Drèze 1974 and Owen 1977) isolated from the rest, then a 'null' agent is powerless whatever is the configuration of winning coalitions in the coalition structure.

Finally, Power Difference is a balance axiom in the style of the collusion neutrality axioms for TU-games in Haller (1994) and Malawski (2002). They speak about a pairwise power difference axiom, where a certain change in the game (collusion of players) does not change the sum of the payoffs of the two players involved. We consider changes in the 'game' in the sense of losing embedded coalitions becoming winning in their partitions. A similar requirement as that of collusion neutrality would require that the sum of the powers of the new winning coalition and each other winning coalition in that partition would be zero. In our context this is, however, a very strong requirement. Therefore, we modify this requirement in two ways: first, we weaken this idea by requiring the sum of these power differences to be constant and second, this constant is not zero, but $\frac{1}{|P|}$, reflecting an equal importance of the partitions.

For $i \in N$ and $v \in G^N$, let $P_i^v = \{\pi \in P : \pi(i) \in E_W^\pi(v)\}$ be the set of all partitions $\pi$, where player $i$ belongs to a winning coalition in $\pi$. We define the power index $f^*$ such that, for each $v \in G^N$ and $i \in N$,

$$f_i^*(v) = \frac{1}{|P|} \sum_{\pi \in P_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} \quad (1)$$

This index assumes equal weight/importance for every partition, and thus $\frac{1}{|P|}$ is allocated over the players in every partition. In any partition, this number is (i) equally allocated over the winning coalitions in the partition (recall that in a plurality game there is at least one winning coalition in every partition), and (ii) the power allocated to a winning coalition in a partition is equally allocated over the players in that winning coalition.

In order to show that $f^*$ is a power index, fix $v \in G^N$ and observe that, due to $E_W^{\{N\}}(v) = \{N\}$, the lowest value $f_i^*(v)$ can take for $i \in N$ is when player $i$ belongs to a winning coalition only in the partition $\{N\}$; hence, in such a case, we have $f_i^*(v) = \frac{1}{n \cdot |P|} > 0$.
On the other hand,

$$
\begin{align*}
\sum_{i \in N} f_i^*(v) &= \sum_{i \in N} \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} \\
&= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}} \sum_{i \in N, \pi \in \mathcal{P}_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} \\
&= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}} \sum_{S \in E_W^\pi(v)} \frac{1}{|E_W^\pi(v)|} \\
&= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}} 1 = \frac{1}{|\mathcal{P}|} \cdot |\mathcal{P}| = 1
\end{align*}
$$

and thus, $f^*$ is indeed a power index.

We have the following characterization result.

**Theorem 1** A power index $f$ satisfies U, II, EI, NI, and PD if and only if $f = f^*$.

The proof of Theorem 1 is relegated to the Appendix.

# 4 Conclusion

The study of plurality voting games combines ideas from the analysis of simple games (cf. Shapley 1962) and insights from the general literature on partition function form games initiated by Thrall (1962) and Thrall and Lucas (1963)<fnref n="3" />. Specifically, the present paper contributes to the strand of literature devoted to power indices in simple games and to values for games in partition function form. Within this strand of literature, the focus is predominantly on extending the Shapley value to games with externalities (e.g., Myerson 1977b; Albizuri et al. 2005; Macho-Stadler et al. 2007; McQuillin 2009; Dutta et al. 2010; Grabisch and Funaki 2012) and different power indices to the class of simple games with externalities (e.g., Bolger 1986; Alonso-Meijide et al. 2017). In contrast to the mentioned works, the axioms we utilize in the present paper are not based on players’ movements from one coalition to another within a partition but rather consider the direct impact on power of losing embedded coalitions becoming winning in a partition. The

<footnote n="3">³We refer the reader to Lucas and Marcelli (1978) for a study of general properties of partition function form games and to Koczy (2018) for a detailed literature survey.</footnote>
formulation of such axioms is based on a new result showing that in every plurality voting game with at least one losing embedded coalition, there is always a losing embedded coalition that can be turned into a winning one without affecting the monotonicity of the game.

An interesting question for future research is to provide axiomatizations of power indices for so-called decisive plurality games, being games such that every partition contains exactly one winning coalition. This is challenging since we cannot just turn one losing coalition into a winning one without destroying the decisiveness of the game. So, we can look for axioms where the replacement of the winning coalition in one partition by another coalition in the same partition will have enough bite.

# 5 Appendix: Proofs

## 5.1 Proof of Proposition 1

We start by introducing the notion of a useful embedded coalition and show in Lemma 1 the existence of at least one such coalition in a game $v \in \mathcal{G}^N$ for the case when $|E_W^{\pi_a}(v)| \le n - 1$ (i.e., when there is at least one losing singleton coalition in the atomistic partition $\pi^a$). In Lemma 4 we show this for the case when $|E_W^{\pi_a}(v)| = n$ (i.e., when all singleton coalitions are winning in $\pi^a$). Such coalitions for the mentioned cases are then used in Lemma 2 and in Lemma 5 as to determine the corresponding elementary transitions between two plurality games and complete the proof.

For $v \in \mathcal{G}^N$ with $|E_W^{\pi_a}(v)| \le n - 1$, we call an embedded coalition $(T; (T, \pi_a))$ s-useful if the following two conditions hold:

$$ (1) \quad v(T; (T, \pi_a)) = 0, \text{ and} $$

$$ (2) \quad v(T \cup \{j\}; (T \cup \{j\}, \pi_a)) = 1 \text{ for each } j \in N \setminus T. $$

That is, $T$ is a losing coalition when all other players are singletons and it becomes winning in the corresponding new partition when a player from $N \setminus T$ joins $T$. For $v \in \mathcal{G}^N$, $L_s^k(v)$ is the set of all s-useful embedded coalitions $(T; (T, \pi_a))$ with $|T| = k$. Notice that $k \in \{1, 2, \dots, n-1\}$, the reason being that $N$ is winning in the unique partition containing it (due to $v \in \mathcal{G}^N$) and thus, the embedded coalition $(N; (N))$ with $|N| = n$ cannot be s-useful.

**Lemma 1** Let $v \in \mathcal{G}^N$ with $|E_W^{\pi_a}(v)| \le n - 1$. Then there exists $k \in \{1, 2, \dots, n-1\}$ such that $L_s^k(v) \ne \emptyset$.

**Proof.** Observe first that $|E_W^{\pi_a}(v)| = n - 1$ implies $L_s^1(v) \ne \emptyset$. As to see it,
let {$i$} be the unique losing coalition in $\pi^a$. By $v \in \mathcal{G}^N$ and $v(j; (j, \pi^-)) = 1$ for each $j \in N \setminus \{i\}$, $v(ij; (ij, \pi^-)) = 1$ holds for each $j \in N \setminus \{i\}$ and thus, $L_s^1(v) = \{(i; \pi^a)\}$ follows.

Suppose now that $|E_W^{\pi^a}(v)| < n-1$ and $L_s^k(v) = \emptyset$ holds for each $k \in \{1, 2, \dots, n-2\}$. We show that $L_s^{n-1}(v) \neq \emptyset$. For this, fix $i \in N$ such that $v(i; (i, \pi^-)) = 0$ and notice that $L_s^1(v) = \emptyset$ implies the existence of $k_i \in N \setminus \{i\}$ such that $v(ik_i; (ik_i, \pi^-)) = 0$.<fnref n="4" /> By $L_s^2(v) = \emptyset$, there exists $\ell_i \in N \setminus \{i, k_i\}$ such that $v(ik_i\ell_i; (ik_i\ell_i, \pi^-)) = 0$. Repeating the argument for each $k \in \{3, \dots, n-2\}$ leads to the existence of some $j \in N$ such that $v(N \setminus \{j\}; (N \setminus \{j\}, \{j\})) = 0$. By $v \in \mathcal{G}^N$, $v(N; (N)) = 1$ follows. We have then $(N \setminus \{j\}; (N \setminus \{j\}, \{j\})) \in L_s^{n-1}(v). \blacksquare$

**Lemma 2** Let $v \in \mathcal{G}^N$ be such that $|E_W^{\pi^a}(v)| \le n-1$. Then there exist $(S; \pi) \in E \setminus E_W(v)$ and $v' \in \mathcal{G}^N$ such that $E_W(v') = E_W(v) \cup \{(S; \pi)\}$.

**Proof.** Let $v \in \mathcal{G}^N$ be as above. By Lemma 1, there exists $k \in \{1, 2, \dots, n-1\}$ such that $L_s^k(v) \neq \emptyset$. Let $k^*$ be the smallest integer such that $L_s^{k^*}(v) \neq \emptyset$. Fix an embedded coalition $(T; (T, \pi^-)) \in L_s^{k^*}(v)$ and set $(S; \pi) := (T; \pi^-)$. Let us show that $E_W(v') = E_W(v) \cup \{(T; (T, \pi^-))\}$ implies $v' \in \mathcal{G}^N$.

Suppose that this is not the case. Then there exist two embedded coalitions $(R'; \pi')$ and $(R; \pi)$ with $(R'; \pi') \subseteq (R; \pi)$ such that $v'(R'; \pi') > v'(R; \pi)$ holds. The latter inequality implies that, in the game $v'$, $R'$ is winning in $\pi'$ and $R$ is losing in $\pi$. It follows from the way in which $v'$ was constructed that $E_W(v) \subset E_W(v')$, and thus $v'(R; \pi) = 0$ implies $v(R; \pi) = 0$. By $v \in \mathcal{G}^N$ and $(R'; \pi') \subseteq (R; \pi)$, $v(R'; \pi') = 0$ follows. Since the only losing embedded coalition in $v$ which is winning in $v'$ is $(T; \pi^-)$, it must be that $(R'; \pi') = (T; (T, \pi^-))$.

Observe that $(T; (T, \pi^-)) = (R'; \pi') \subseteq (R; \pi) = (R; (R, \pi_{N \setminus R}))$ implies $T \subseteq R$ and $\pi_{N \setminus R} = \pi_{N \setminus R}^a$. We now show that in each of the two cases $T = R$ and $T \subset R$ we reach a contradiction.

(1) $T = R$ implies $(R'; \pi') = (R; \pi)$ which is in contradiction to $v'(R'; \pi') > v'(R; \pi)$.

(2) $T \subset R$ leads to $v'(T \cup \{i\}; (T \cup \{i\}, \pi^-)) = v(T \cup \{i\}; (T \cup \{i\}, \pi^-)) = 1$ for each $i \in R \setminus T$ by construction and $(T; (T, \pi^-)) \in L_s^{k^*}(v)$. Repeatedly applying the fact that $v \in \mathcal{G}^N$, we get $v'(R; (R, \pi^-)) = 1$. By $(R; \pi) = (R; (R, \pi^-))$, we have a contradiction to $v'(R'; \pi') = 1$ and $v'(R'; \pi') > v'(R; \pi)$. ■

<footnote n="4">⁴Notice that $n=3$ would imply $v(N; \{(N)\}) = 1$ and thus, $(ik_i; (ik_i, \ell)) \in L_s^2(v)$ with $\ell$ being the third player in the game $v$ would directly follow.</footnote>
We have the following helpful result.

**Lemma 3** If $v \in \mathcal{G}^N$ is such that, for each $D \subseteq N$, all coalitions in $(D, \pi_{-}^a)$ are winning in $v$, then $E_W(v) = E$.

**Proof.** Suppose not, i.e., there is an embedded coalition $(S; \pi)$ such that $S \neq N$ and $v(S; \pi) = 0$. By the definition of a plurality game, $v(T; \pi) = 1$ for some $T \in \pi$. Take $i \in S$ and notice that, by the monotonicity of $v$, $v(\{i\}; (N \setminus \{i\}, \{i\})) = 0$ follows. Thus, we have a contradiction to $\{i\}$ being a winning coalition in $(N \setminus \{i\}, \{i\})$. ■

Consider $v \in \mathcal{G}^N$ with $|E_W^{\pi_a}(v)| = n$ and fix $D \subset N$. An embedded coalition $(T; (D, T, \pi_-^a))$ is *D-useful* if the following two conditions hold:

(1) $v(T; (D, T, \pi_-^a)) = 0$, and

(2) $v(T \cup \{j\}; (D, T \cup \{j\}, \pi_-^a)) = 1$ for each $j \in N \setminus (D \cup T)$.

In other words, $T$ is a losing coalition when all players from $N \setminus (D \cup T)$ are singletons and it becomes winning in the corresponding new partition when a player from $N \setminus (D \cup T)$ joins $T$. For $v \in \mathcal{G}^N$, we collect in the set $L_D^m(v)$ all *D-useful* embedded coalitions $(T; (D, T, \pi_-^a))$ with $|T| = m$. Notice that $m \in \{1, 2, \dots, n - |D|\}$, the reason being that the largest coalition that can be losing in a partition containing the coalition $D$ is $N \setminus D$ (of size $n - |D|$).

**Lemma 4** Let $v \in \mathcal{G}^N$ be such that $|E_W^{\pi_a}(v)| = n$ and $E_W(v) \neq E$. Then there exist $D \subset N$ and $m \in \{1, 2, \dots, n - |D|\}$ such that $L_D^m(v) \neq \emptyset$.

**Proof.** Observe that, by $v \in \mathcal{G}^N$ and $|E_W^{\pi_a}(v)| = n$, $v(T; (T, \pi_-^a)) = 1$ holds for each $T \subset N$. By $E_W(v) \neq E$ and Lemma 3, there exist $D \subset N$ and $i \in N$ such that $(i; (D, i, \pi_-^a))$ is a losing embedded coalition in $v$ (and, of course, $(D; (D, \pi_-^a))$ is a winning embedded coalition in $v$).

If $\{i\}$ is the only losing singleton coalition in $(D, \pi_-^a)$, then $L_D^1(v) \neq \emptyset$. As to see it, notice that by $v \in \mathcal{G}^N$, $v(ij; (D, ij, \pi_-^a)) = 1$ holds for each $j \in N \setminus (D \cup \{i\})$ and thus, $L_D^1(v) = \{(i; (D, i, \pi_-^a))\}$ follows.

Suppose now that there are at least two losing singleton coalitions in $(D, \pi_-^a)$ and $L_D^m(v) = \emptyset$ holds for each $m \in \{1, 2, \dots, n - |D| - 2\}$. We show that either $L_D^{n-|D|-1}(v) \neq \emptyset$ or $L_D^{n-|D|}(v) \neq \emptyset$. For this, fix $i \in N$ such that $v(i; (D, i, \pi_-^a)) = 0$ and notice that $L_D^1(v) = \emptyset$ implies the existence of $k_i \in N \setminus (D \cup \{i\})$ such that $v(ik_i; (D, ik_i, \pi_-^a)) = 0$. By $L_D^2(v) = \emptyset$, there exists $\ell_i \in N \setminus (D \cup \{i, k_i\})$ such that $v(ik_i\ell_i; (D, ik_i\ell_i, \pi_-^a)) = 0$. Repeating the argument for each $m \in \{3, \dots, n - |D| - 2\}$ leads to the existence of some $j \in N$ such that $v(N \setminus (D \cup \{j\}); (D, N \setminus (D \cup \{j\})), \{j\})) = 0$. If $v(N \setminus D; (D, N \setminus D)) = 1$, then $(N \setminus (D \cup \{j\}); (D, N \setminus (D \cup \{j\})), \{j\})) \in$
$L_D^{n-|D|-1}(v)$ follows. Otherwise, if $v(N \setminus D; (D, N \setminus D)) = 0$, then $(N \setminus D; (D, N \setminus D)) \in L_D^{n-|D|}(v)$ trivially holds due to $N \setminus (D \cup (N \setminus D)) = \emptyset$ and the definition of a $D$-useful embedded coalition. ■

**Lemma 5** Let $v \in \mathcal{G}^N$ be such that $|E_W^{\pi_a}(v)| = n$ and $E_W(v) \neq E$. Then there exist $(S; \pi) \in E \setminus E_W(v)$ and $v' \in \mathcal{G}^N$ such that $E_W(v') = E_W(v) \cup \{(S; \pi)\}$.

**Proof.** Let $v \in \mathcal{G}^N$ be as above. By Lemma 4, there exist $D \subset N$ and $m \in \{1, 2, \dots, n - |D|\}$ such that $L_D^m(v) \neq \emptyset$. Let $m^*$ be the smallest integer such that $L_D^{m^*}(v) \neq \emptyset$. Fix an embedded coalition $(T; (D, T, \pi_-^a)) \in L_D^{m^*}(v)$ and set $(S; \pi) := (T; (D, T, \pi_-^a))$. Let us show that $E_W(v') = E_W(v) \cup \{(T; (D, T, \pi_-^a))\}$ implies $v' \in \mathcal{G}^N$.

Suppose this is not the case. Then there exist two embedded coalitions $(R'; \pi')$ and $(R; \pi)$ with $(R'; \pi') \subseteq (R; \pi)$ such that $v'(R'; \pi') > v'(R; \pi)$ holds. The latter inequality implies that, in the game $v'$, $R'$ is winning in $\pi'$ and $R$ is losing in $\pi$. It follows from the way in which $v'$ was constructed that $v'(R; \pi) = 0$ implies $v(R; \pi) = 0$ since $E_W(v) \subset E_W(v')$. By $v \in \mathcal{G}^N$ and $(R'; \pi') \subseteq (R; \pi)$, $v(R'; \pi') = 0$ follows. Since the only losing embedded coalition in $v$ which is winning in $v'$ is by construction $(T; (D, T, \pi_-^a))$, we conclude that $(R'; \pi') = (T; (D, T, \pi_-^a))$ should be the case. Observe that $(T; (D, T, \pi_-^a)) = (R'; \pi') \subseteq (R; \pi) = (R; (R, \pi_{N \setminus R}))$ implies $T \subseteq R$ and $\pi_{N \setminus R} \in \{\pi_{N \setminus R}^a, (D, \pi_{N \setminus (R \cup D)}^a)\}$. There are three possible cases to be considered.

(1) $\pi_{N \setminus R} = \pi_{N \setminus R}^a$. As explained above, $v'(R; \pi) = 0$ implies $v(R; \pi) = 0$; that is, we have $v(R; (R, \pi_-^a)) = 0$. However, by $v \in \mathcal{G}^N$ and $|E_W^{\pi_a}(v)| = n$, $v(R; (R, \pi_-^a)) = 1$ should hold, a contradiction.

(2) $T = R$ and $\pi_{N \setminus R} = (D, \pi_{N \setminus (R \cup D)}^a)$. In this case $(R'; \pi') = (R; \pi)$ follows, a direct contradiction to $v'(R'; \pi') > v'(R; \pi)$.

(3) $T \subset R$ and $\pi_{N \setminus R} = (D, \pi_{N \setminus (R \cup D)}^a)$. By construction, $v'(T \cup \{i\}; (T \cup \{i\}, D, \pi_-^a)) = v(T \cup \{i\}; (T \cup \{i\}, D, \pi_-^a)) = 1$ holds for each $i \in R \setminus T$. Repeatedly applying the fact that $v \in \mathcal{G}^N$, we get $v'(R; (R, D, \pi_-^a)) = 1$. By $(R; \pi) = (R; (R, D, \pi_-^a))$, we have a contradiction to $v'(R'; \pi') = 1$ and $v'(R'; \pi') > v'(R; \pi)$. ■
## 5.2 Proof of Theorem 1

We show first that the power index $f^*$ as defined in Section 3 (see (1)) satisfies our five axioms.

*Unanimity* Let $v \in \mathcal{G}^N$ be such that $E_W(v) = E$. Notice that in such a case and for each $i \in N$, we have $\mathcal{P}_i^v = \mathcal{P}$. Clearly then, the number of times each player belongs to a coalition of a given size in a partition is the same. In other words, U is satisfied with $f_i^*(v) = \frac{1}{n}$ for each $i \in N$ (due to $\Sigma_{i \in N} f_i^*(v) = 1$).

In order to show that $f^*$ also satisfies the other four axioms, suppose the games $v, v' \in \mathcal{G}^N$ are such that $E_W(v') = E_W(v) \cup (S; \pi^*)$.

*Internal Impact* For each $i \in T \in E_W^{\pi^*}(v)$ we have

$$f_i^*(v) = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} + \frac{1}{|\mathcal{P}|} \frac{1}{|E_W^{\pi^*}(v)| \cdot |T|}$$

and

$$f_i^*(v') = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^{v'}} \frac{1}{|E_W^\pi(v')| \cdot |\pi(i)|} = \frac{1}{|\mathcal{P}|} \left( \sum_{\pi \in \mathcal{P}_i^{v'} \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} + \frac{1}{|E_W^{\pi^*}(v')| \cdot |T|} \right) \\ = \frac{1}{|\mathcal{P}|} \left( \sum_{\pi \in \mathcal{P}_i^{v'} \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} + \frac{1}{(|E_W^{\pi^*}(v)| + 1) \cdot |T|} \right).$$

Hence,

$$\begin{aligned} \Delta_i^{f^*}(v, v') &= f_i^*(v') - f_i^*(v) && (2) \\ &= \frac{1}{|\mathcal{P}|} \left( \frac{1}{(|E_W^{\pi^*}(v)| + 1) \cdot |T|} - \frac{1}{|E_W^{\pi^*}(v)| \cdot |T|} \right). \end{aligned}$$

We have further for each $i \in S$ that

$$f_i^*(v) = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|}$$
and

$$
\begin{align*}
f_i^*(v') &= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^{v'}} \frac{1}{|E_W^\pi(v')| \cdot |\pi(i)|} \\
&= \frac{1}{|\mathcal{P}|} \left( \sum_{\pi \in \mathcal{P}_i^{v' \setminus \{\pi^*\}}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} + \frac{1}{|E_W^{\pi^*}(v')| \cdot |S|} \right) \\
&= \frac{1}{|\mathcal{P}|} \left( \sum_{\pi \in \mathcal{P}_i^{v' \setminus \{\pi^*\}}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} + \frac{1}{(|E_W^{\pi^*}(v)| + 1) \cdot |S|} \right).
\end{align*}
$$

Hence,

$$
\begin{align}
\Delta_i^{f^*}(v, v') &= f_i^*(v') - f_i^*(v) \tag{3} \\
&= \frac{1}{|\mathcal{P}| \cdot |S| \cdot (|E_W^{\pi^*}(v)| + 1)}. \nonumber
\end{align}
$$

We conclude from (2) and (3) that $\Delta_i^{f^*}(v, v')$ is independent of $i$ for each player $i$ belonging to a winning coalition in the partition $\pi^*$ and thus, II is satisfied.

*External Impact* Take $T \in E_W^{\pi^*}(v)$ and notice that in view of (2) we have

$$
\begin{align*}
\Delta_T^{f^*}(v, v') &= \sum_{i \in T} \Delta_i^{f^*}(v, v') \\
&= \frac{|T|}{|\mathcal{P}|} \left( \frac{1}{(|E_W^{\pi^*}(v)| + 1) \cdot |T|} - \frac{1}{|E_W^{\pi^*}(v)| \cdot |T|} \right) \\
&= \frac{|T|}{|\mathcal{P}|} \cdot \frac{|E_W^{\pi^*}(v)| - |E_W^{\pi^*}(v)| - 1}{(|E_W^{\pi^*}(v)| + 1) \cdot |E_W^{\pi^*}(v)| \cdot |T|} \\
&= \frac{-1}{|\mathcal{P}| \cdot (|E_W^{\pi^*}(v)| + 1) \cdot |E_W^{\pi^*}(v)|},
\end{align*}
$$

i.e., $\Delta_T^{f^*}(v, v')$ is independent of $T$. We conclude that EI is satisfied.

*Null Impact* Take $i \in T \in \pi^* \setminus E_W(v')$. We have

$$
f_i^*(v) = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|} = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^v \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|}
$$
and

$$
\begin{align*}
f_i^*(v') &= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^{v'}} \frac{1}{|E_W^\pi(v')| \cdot |\pi(i)|} = \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^{v'} \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v')| \cdot |\pi(i)|} \\
&= \frac{1}{|\mathcal{P}|} \sum_{\pi \in \mathcal{P}_i^{v'} \setminus \{\pi^*\}} \frac{1}{|E_W^\pi(v)| \cdot |\pi(i)|}.
\end{align*}
$$

Hence,

$$
\Delta_{i}^{f^{*}}(v, v') = f_{i}^{*}(v') - f_{i}^{*}(v) = 0
$$

holds and thus, NI is satisfied.

Power Difference In view of (2) and (3), we have

$$
\begin{align*}
\sum_{T \in E_W^\pi(v)} \Delta_{ST}^{f^*}(v, v') &= |E_W^\pi(v)| \cdot \Delta_S^{f^*}(v, v') - \sum_{T \in E_W^\pi(v)} \Delta_T^{f^*}(v, v') \\
&= \frac{|S| \cdot |E_W^\pi(v)|}{|\mathcal{P}| \cdot |S| \cdot (|E_W^\pi(v)| + 1)} + \frac{|E_W^\pi(v)|}{|\mathcal{P}| \cdot (|E_W^\pi(v)| + 1) \cdot |E_W^\pi(v)|} \\
&= \frac{1}{|\mathcal{P}| \cdot (|E_W^\pi(v)| + 1)} \cdot (|E_W^\pi(v)| + 1) = \frac{1}{|\mathcal{P}|}
\end{align*}
$$

as required for the fulfillment of PD.

Suppose now that *f* satisfies the above axioms. To show that the power index is uniquely determined, consider *v* ∈ *G*^N and let us proceed by induction on the cardinality of the set *E*<sub>*W*</sub>(*v*) of winning embedded coalitions in *v*.

Initialization: Suppose |E<sub>W</sub>(v)| = |E|. By U and the definition of a power index, f<sub>i</sub>(v) = 1/n for each i ∈ N follows.

Induction Hypothesis: Suppose that the power index is uniquely determined for each v* ∈ G^N with |E_W(v*)| > |E_W(v)|.

By Proposition 1, there exists $v' \in \mathcal{G}^N$ such that $E_W(v') = E_W(v) \cup \{(S; \pi)\}$ for some $(S; \pi) \in E \setminus E_W(v)$. Observe that, by $|E_W(v')| > |E_W(v)|$ and the Induction Hypothesis, the power vector $f(v')$ is uniquely determined. In what follows, we show that $f(v)$ is uniquely determined as well.

For this, and w.l.o.g., let $\pi = \{S_1, \dots, S_{k-1}, S_k, S_{k+1}, \dots, S_K\}$ with $v(S_\ell; \pi) = 1$ for each $\ell \in \{1, \dots, k-1\}$, $S_k = S$, and $v(S_\ell; \pi) = 0$ for each $\ell \in$
$\{k+1, \dots, K\}$. Notice then that $f_i(v') - f_i(v) = 0$ holds for each $i \in \cup_{\ell=k+1}^K S_\ell$ due to NI. That is, the exact determination of any such $f_i(v)$ directly follows from the fact that $f_i(v')$ has already been fixed.

For each $T \subseteq N$, set $f_T(v) := \sum_{i \in T} f_i(v)$ and $f_T(v') := \sum_{i \in T} f_i(v')$. Notice further that, by PD we have

$$ 
\begin{align*}
&= \frac{1}{|\mathcal{P}|} \sum_{\ell=1}^{k-1} ((f_S(v') - f_S(v)) - (f_{S_\ell}(v') - f_{S_\ell}(v))) \\
&= (k-1) \cdot (f_S(v') - f_S(v)) - \sum_{\ell=1}^{k-1} (f_{S_\ell}(v') - f_{S_\ell}(v)) \\
&= (k-1) \cdot (f_S(v') - f_S(v)) - \sum_{\ell=1}^{k-1} f_{S_\ell}(v') + \sum_{\ell=1}^{k-1} f_{S_\ell}(v) \\
&= (k-1) \cdot (f_S(v') - f_S(v)) - \sum_{\ell=1}^{k-1} f_{S_\ell}(v') + \left(1 - f_S(v) - \sum_{\ell=k+1}^K f_{S_\ell}(v)\right),
\end{align*}
$$

where the last equality follows from the definition of a power index. Thus, we can exactly determine $f_S(v)$ due to (1) $f(v')$ being already fixed by the Induction Hypothesis, and (2) $f_{S_\ell}(v)$ being also fixed for each $\ell \in \{k+1, \dots, K\}$ by NI as shown above.

Observe further that axiom EI requires the difference $f_Q(v') - f_Q(v)$ to be the same for each $Q \in \{S_1, \dots, S_{k-1}\}$ and thus, $f_Q(v)$ is uniquely determined as well. Finally, II requires for each $Q \in \{S_1, \dots, S_{k-1}\}$ the total power differences $f_i(v') - f_i(v)$ to be the same for each $i \in Q$. Since $f(v')$ is known by the Induction Hypothesis, we conclude that $f(v)$ is uniquely determined.

<figure><img src="image_3.png" /></figure>

## References

[1] Albizuri, M., J. Arin, and J. Rubio (2005): An axiom system for a value partition function form. *International Game Theory Review* 7, 63-73.

[2] Algaba, E., M. Bilbao, P. Borm, and J. López (2001): The Myerson value for union stable structures. *Mathematical Methods of Operations Research* 54, 359-371.
[3] Alonso-Meijide, J., M. Alvarez Mozos, and M. Fiestras-Janeiro (2017): Power indices and minimal winning coalitions for simple games in partition function form. *Group Decision and Negotiation* 26, 1231-1245.

[4] Aumann, R. and J. Drèze (1974): Cooperative games with coalition structures. *International Journal of Game Theory* 3, 217-237.

[5] Bolger, E. (1986): Power indices for multicandidate voting games. *International Journal of Game Theory* 15(3), 175-186.

[6] Brink, R. van den, D. Dimitrov, and A. Rusinowska (2021): Winning coalitions in plurality voting democracies. *Social Choice and Welfare* 56(3), 509-530.

[7] Dutta, B., L. Ehlers, and A. Kar (2010): Externalities, potential, value and consistency. *Journal of Economic Theory* 145, 2380-2411.

[8] Grabisch, M. and Y. Funaki (2012): A coalition formation value for games in partition function form. *European Journal of Operational Research* 221(1), 175-185.

[9] Haller, H. (1994): Collusion properties of values. *International Journal of Game Theory* 23, 261-281.

[10] Koczy, L. (2018): *Partition Function Form Games. Coalitional Games with Externalities*. Theory and Decision Library C, Volume 48, Springer International Publishing.

[11] Lucas, W. and J. Marcelli (1978): Discrete partition function games. In P.C. Ordeshook, editor, *Game Theory and Political Science*, pp. 191-213. New York University Press.

[12] Macho-Stadler, I., D. Perez-Castrillo, and D. Wettstein (2007): Sharing the surplus: An extension of the Shapley value for environments with externalities. *Journal of Economic Theory* 135, 339-356.

[13] Malawski, M. (2002): Equal treatment, symmetry and Banzhaf value axiomatizations. *International Journal of Game Theory* 31, 47-67.

[14] McQuillin, B. (2009): The extended and generalized Shapley value. *Multaneous consideration of coalitional externalities and coalition structure*. *Journal of Economic Theory* 144, 696-721.
[15] Myerson, R. (1977a) Graphs and cooperation in games. *Mathematics of Operations Research* 2, 225-229.

[16] Myerson, R. (1977b): Values of games in partition function form. *International Journal of Game Theory* 6, 23-31.

[17] Owen, G. (1977): Values of games with a priori unions. In: *Mathematical Economics and Game Theory* (R. Henn and O. Moeschlin, Eds.), pp. 76-88, Springer-Verlag.

[18] Shapley, L. (1962): Simple games: An outline of the descriptive theory. *Behavioral Science* 7, 59-66.

[19] Thrall, R. (1962): Generalised characteristic functions for n-person games. In *Proceedings of the Princeton University Conference*, pp. 157-160.

[20] Thrall, R. and W. Lucas (1963): N-person games in partition function form. *Naval Research Logistics Quarterly* 10(1), 281-298.