A Probabilistic Unified Approach for Power Indices in Simple Games

Abstract

Many power indices on simple games have been defined trying to measure, under different points of view, the “a priori” importance of a voter in a collective binary voting scenario. A unified probabilistic way to define some of these power indices is considered in this paper. We show that six well-known power indices are obtained under such a probabilistic approach. Moreover, some new power indices can naturally be obtained in this way.

1 Introduction

Different ways to assign a measure of power to voters in collective decision–making processes have been proposed and analyzed for many authors. The most well–known are the Banzhaf [3, 5, 13] (also known as the Penrose index) and the Shapley–Shubik [14] indices, but other indices as those defined by Johnston [12], Deegan and Packel [6], Alonso and Freixas [1] (also known as shift index), Holler [10] (also known as the Public Good index) or Alonso–Freixas–Molinero index [2] have also interesting properties. Several power indices for simple games are addressed to the problem of dividing among players a unit of a fixed divisible prize worth, say, 1 unit of transferable utility (TU) (e.g., money, a cake). These power indices, by their nature, are efficient: nothing of the divisible good is wasted. They also share the common fact that are based on some subsets of winning coalitions for which players in them are critical, i.e., after the deletion of a player in a winning coalition the coalition becomes losing.

In this context, the importance of a voter, seen as his/her estimated gain, can be measured as his/her expected value under a probabilistic model. Such a probabilistic model is determined by providing an answer for each one of the three following questions:

• What kind of winning coalitions can be formed.

• What is the probability of each coalition to be formed.

• How the benefits are to be distributed among players in the formed coalition.

This point of view was explicitly used in [6] to define the Deegan–Packel index, by assuming that only minimal winning coalitions can be formed, that all minimal winning coalitions have the same probability to be formed and that the shares are divided equally among the members of the victorious coalition. Our contribution in this note is to show that many other power indices in simple games can be defined under the same probabilistic scheme by assuming different answers to the questions above. In fact, the crucial question is the second one because: (a) the more natural answer to the third question is to divide the benefits equally, and (b) certain coalitions are assumed to be impossible, i.e., the probability of their formation is zero, so that the answer to the second question can include the answer to the first one.

The rest of the paper is organized as follows. Section 2 is devoted to recall the fundamentals on simple games. In Sect. 3, two groups of three well-known power indices are seen under similar probabilistic approaches, following what we call Model 1 and Model 2. In Sect. 4 three new indices are introduced under the same approach under what we call Model 3. In Sect. 5 it is proved that the three indices based on winning coalitions containing crucial players are ordinally equivalent in complete simple games, result that complements the well-known equivalence ordinal between the Johnston and the Banzhaf indices on complete simple games. The Conclusion ends the paper in Sect. 6.

2 Basics on Simple Games

In the sequel, $N=\{1,2,\dots ,n\}$ will denote a fixed but otherwise arbitrary finite set of players. Any subset $S\subseteq N$ is a coalition. A cooperative game is a map $v : 2^N \rightarrow \mathbb {R}$ such that $v(\emptyset )=0$. A cooperative game v (in N, omitted hereafter) is a simple game if (a) $v(S)=0\;\text{ or }\;1$ for all S, (b) is monotonic, i.e. $v(S)\le v(T)$ whenever $S\subset T$, and (c) $v(N)=1$. Either the family of winning coalitions $\mathcal W=\mathcal W(v)=\{S\subseteq N:v(S)=1\}$ or the subfamily of minimal winning coalitions $\mathcal W^m = \mathcal W^m(v)= \{S\in \mathcal W: T\subset S\Rightarrow T\notin \mathcal W\}$ determines the game. The players $a \in N$ that can convert a winning coalition into a losing one by leaving the coalition are called critical players:

$$ a\; \text {is critical in a coalition} \;S \quad \text { if and only if}\quad a\in S, \;S\in \mathcal W \text { and } \;S \setminus \{a\}\notin \mathcal W.$$

The set of critical coalitions is $\mathcal W^c = \mathcal W^c(v) = \{ S \in \mathcal W \, :\, S \setminus \{i\} \notin \mathcal W, \; \text {for some} \; i \in N \}$.

Observe that $\mathcal W^m \subseteq \mathcal W^c$.

A player $a \in N$ is null if $a \notin S$ for all $S \in \mathcal W^m$. A player $a \in N$ has veto if $a \in S$ for all $S \in \mathcal W$.

To define the last subset of winning coalitions we are interested in, we need to introduce the desirability relation, given first in [11]. Let v be a simple game on N and $a,b\in N$:

$$ a \succsim b\quad \text{ if } \text{ and } \text{ only } \text{ if }\quad S\cup \{b\}\in \mathcal W\Rightarrow S\cup \{a\}\in \mathcal W\quad \text{ for } \text{ all }\quad S\subseteq N\backslash \{a,b\}. $$

It is not difficult to check that $\succsim$ is a preordering on N. $\succsim$ (resp., $\succ$) is called the desirability (resp., strict desirability) relation and $\approx$ the equi–desirability relation. The relationship between the desirability relation and power indices have been intensively studied, among them we refer to [4, 7, 8, 15, 16].

A simple game is complete if the the desirability relation is a complete preordering, i.e., either $a \succsim b$ or $b \succsim a$ for all pair of players a, b.

A coalition S is shift-minimal winning if $S \in \mathcal W$ and $(S \setminus \{a\}) \cup \{b\}) \notin \mathcal W$ for all $a \in S$ and $b \notin S$ with $a \succ b$. The set ${\mathcal W}^s = {\mathcal W}^s(v)$ denote the set of shift-minimal winning coalitions and satisfies: ${\mathcal W}^s \subseteq \mathcal W^m \subseteq \mathcal W^c$. Only for $n\ge 4$ there are simple games in which the inclusion ${\mathcal W}^s \subseteq {\mathcal W}^m$ is strict.

Example 1

Let $(N,\mathcal W^m)$ be the simple game, with $N = \{1,2,3,4,5\}$ and

$$ \mathcal W^m = \{ S\subseteq N :\; \mid S\mid =3\quad and \quad S\ne \{3,4,5\} \}. $$

It holds $1 \approx 2 \succ 3 \approx 4 \approx 5$. Thus, the coalitions $\{1,2,3\}$, $\{1,2,4\}$ and $\{1,2,5\}$ are minimal winning but not shift-minimal winning because, for instance, $\{1,3,5\}$ is still winning and $2 \succ 3$.

Finally, let’s establish some notation. The three collections of winning coalitions that are used to define power indices in the next section are either $\mathcal W^c$, $\mathcal W^m$ or $\mathcal W^s$. $\mathcal Y$ refers to anyone of these collections when generic properties or notations are to be established.

• For each $a \in N$, $\mathcal Y_a$ denote the set of coalitions in $\mathcal Y$ containing a.

• $\mathcal C_a(\mathcal Y)=\{S\in \mathcal Y_a:S\backslash \{a\}\notin \mathcal W\}$ i.e., $\mathcal C_a (\mathcal Y)$ denote the set of coalitions in $\mathcal Y_a$ for which a is critical. Throughout the paper we denote its cardinality with $\eta _a(\mathcal Y) = | \mathcal C_a(\mathcal Y) |$.

  Note that:

  • $\mathcal C_a(\mathcal W^m) = \mathcal W_a^m$, thus $\eta _a(\mathcal W^m) =|\mathcal C_a(\mathcal W^m)|= |\mathcal W_a^m|$.

  • $\mathcal C_a(\mathcal W^s) = \mathcal W_a^s$, thus $\eta _a(\mathcal W^s) =|\mathcal C_a(\mathcal W^s)|= |\mathcal W_a^s|$.

  • $\mathcal C_a(\mathcal W^c) \subseteq \mathcal W_a^c$, thus $\eta _a(\mathcal W^c)= |\mathcal C_a(\mathcal W^c)| \le |\mathcal W_a^c|$.

  But the inclusion $\mathcal C_a(\mathcal W^c) \subseteq \mathcal W_a^c$ can be strict. For instance, in Example 1 note that

  $$\mathcal W_3^c = \{ \{1,2,3\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{2,3,5\} ,\{1,2,3,4\},\{1,2,3,5\}\}$$
  $$\mathcal C_3(\mathcal W^c) = \{ \{1,2,3\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{2,3,5\} \}.$$

• For $S \in \mathcal W^c$:

  $\mathcal C(S)=\{i\in S:S\backslash \{i\}\notin \mathcal W\}$, i.e., $\mathcal C(S)$ is the set of critical players in S ($\mathcal C(S)\ne \emptyset$).

  ${\chi }(S) = \dfrac{1}{|C(S)|}$, i.e., ${\chi }(S)$ is the converse of the number of critical players in S.

  Note that $\dfrac{1}{|S|} \le {\chi }(S) \le 1$, but if $S \in \mathcal W^m$ or $S \in \mathcal W^s$ then ${\chi }(S) = \dfrac{1}{|S|}$.

3 Known Power Indices for Simple Games

In the next subsections we consider two probabilistic models which lead to the definition of six already known indices. The only difference between the two models is the assumption on the probability of a coalition to be formed. In all cases $\mathcal Y$ indicates a collection of winning coalitions. Although the collections used in this note are either $\mathcal Y=\mathcal W^c$, $\mathcal Y=\mathcal W^m$ or $\mathcal Y=\mathcal W^s$, other possibilities could be also considered.

Let us remark that our approach is not necessarily the way in which every particular index was defined by their authors but it turns out to be true that all of them can be expressed under this unified scheme. The model 1 was already introduced in [6] for $\mathcal Y=\mathcal W^m$ but, as far as we know, model 2, which leads to three well–known power indices was never explicitly stated.

3.1 Model 1

This model is defined by the following assumptions:

• Only winning coalitions in $\mathcal Y$ will be formed.

• All coalitions in $\mathcal Y$ have equal probability of being formed.

• All critical members of the victorious coalition in $\mathcal Y$ receive equal shares of the ‘spoils’, while the rest of players in this coalition receive nothing.

Under these assumptions, the probability of a coalition $S\in \mathcal Y$ to be formed is $P(S)=\dfrac{1}{|\mathcal Y|}$ and the payoff of a player $a\in S$ if $a\in \mathcal C(S)$ is $\dfrac{1}{|\mathcal C(S)|}=\chi (S)$, while her payoff is 0 if $a\notin \mathcal C(S)$. Thus, the Expected value of a ’s gain if a is not null is:

$$\begin{aligned} E_a(\mathcal Y)=\sum _{S\in \mathcal C_a(\mathcal Y)}\dfrac{1}{|\mathcal Y|} \chi (S)=\dfrac{1}{|\mathcal Y|} \sum _{S\in \mathcal C_a(\mathcal Y)}\chi (S)\end{aligned}$$

(1)

and $E_a(\mathcal Y)=0$ if a is a null player.

For each collection $\mathcal Y$ of winning coalitions the formula (1) gives the value of a power index, obtaining in this way the three indices shown below. In the next definitions we assume that $a\in N$ is not a null player because in this case all indices are declared to be zero.

Johnston index ($\mathcal Y=\mathcal W^c$)

$$J_a=\dfrac{1}{|\mathcal W^c|} \sum _{S\in \mathcal C_a(\mathcal W^c)}\chi (S)$$

Deegan–Packel index ($\mathcal Y=\mathcal W^m$)

Alonso–Freixas–Molinero index ($\mathcal Y=\mathcal W^s$)

3.2 Model 2

This model is defined by the following assumptions:

• Only winning coalitions in $\mathcal Y$ will be formed.

• The probability that a coalition in $\mathcal Y$ is formed is proportional to the number of critical players it contains.

• All critical members of the victorious coalition in $\mathcal Y$ receive equal shares of the ’spoils’, while the rest of players in this coalition receive nothing.

Under these hypothesis, for each possible election of the set $\mathcal Y$, the probability of a coalition $S\in \mathcal Y$ to be formed is $P(S)=\dfrac{|\mathcal C(S)|}{\sum _{T\in \mathcal Y}|\mathcal C(T)|}$ and the payoff of a player $a\in S$ is the same as in the model 1. Thus, the Expected value of a ’s gain is:

$$\begin{aligned} E_a(\mathcal Y)=\sum _{S\in \mathcal C_a(\mathcal Y)}\dfrac{|\mathcal C(S)|}{\sum _{T\in \mathcal Y}|\mathcal C(T)|} \chi (S)=\dfrac{ |\mathcal C_a(\mathcal Y)|}{\sum _{T\in \mathcal Y}|\mathcal C(T)|}= \dfrac{ \eta _a(\mathcal Y)}{\sum _{T\in \mathcal Y}|\mathcal C(T)|}\end{aligned}$$

(2)

For each collection $\mathcal Y$ of winning coalitions the formula (2) gives the value of a power index, obtaining in this way the three indices shown below. In the next definitions we assume that $a\in N$ is not a null player because in this case all indices are declared to be zero.

Banzhaf index ($\mathcal Y=\mathcal W^c$)

$$B_a =\dfrac{ \eta _a(\mathcal W^c)}{\sum _{S\in \mathcal W^c}|\mathcal C(S)|}$$

Holler index ($\mathcal Y=\mathcal W^m$)

$$H_a =\dfrac{ \eta _a(\mathcal W^m)}{\sum _{S\in \mathcal W^m}|\mathcal C(S)|}=\dfrac{ \eta _a(\mathcal W^m)}{\sum _{S\in \mathcal W^m}|S|}$$

Alonso–Freixas index ($\mathcal Y=\mathcal W^s$)

$${AF}_a =\dfrac{ \eta _a(\mathcal W^s)}{\sum _{S\in \mathcal W^s}|\mathcal C(S)|}=\dfrac{ \eta _a(\mathcal W^s)}{\sum _{S\in \mathcal W^s}|S|}$$

4 New Power Indices for Simple Games

In this section we introduce a new model which allows us, following the unified probabilistic scheme shown in the former section, to define three new power indices.

4.1 Model 3

This model is defined by the following assumptions:

• Only winning coalitions in $\mathcal Y$ will be formed.

• Coalitions in $\mathcal Y$ have a probability of being formed inversely proportional to their size (or cardinality).

• All critical members of the victorious coalition in $\mathcal Y$ receive equal shares of the ’spoils’, while the rest of players in this coalition receive nothing.

The idea behind this model is the consideration that forming small coalitions is easier and more stable than forming big coalitions.

Items 1 and 3 above are identical as in the previous two models. Thus, the only difference between model 3 and its two predecessors lies on the second item.

Under these assumptions, for each possible election of the set $\mathcal Y$, the probability of a coalition $S\in \mathcal Y$ to be formed is $P(S)=\dfrac{1/|S|}{\sum _{T\in \mathcal Y}1/|T|}$ and the payoff of a player $a\in S$ is $\dfrac{1}{|\mathcal C(S)|}=\chi (S)$ if $a\in \mathcal C(S)$, while her payoff is 0 if $a\notin \mathcal C(S)$. Thus, the Expected value of a ’s gain is:

$$\begin{aligned} E_a(\mathcal Y)=\sum _{S\in \mathcal C_a(\mathcal Y)}\dfrac{1/|S|}{\sum _{T\in \mathcal Y}1/|T|} \chi (S)=\dfrac{1}{\sum _{T\in \mathcal Y}1/|T|} \sum _{S\in \mathcal C_a(\mathcal Y)}\dfrac{1}{|S||\mathcal C(S)|} \end{aligned}$$

(3)

For each collection $\mathcal Y$ of winning coalitions the formula (3) gives the value of a power index, obtaining in this way the three indices shown below. In the next definitions we assume that $a\in N$ is not a null player because in this case all indices are declared to be zero.

Index $\varvec{\alpha }$ ($\mathcal Y=\mathcal W^c$)

$$\varvec{\alpha }_a =\dfrac{1}{\sum _{T\in \mathcal W^c}1/|T|} \sum _{S\in \mathcal C_a(\mathcal W^c)}\dfrac{1}{|S||\mathcal C(S)|}$$

Index $\varvec{\beta }$ ($\mathcal Y=\mathcal W^m$)

$$\varvec{\beta }_a =\dfrac{1}{\sum _{T\in \mathcal W^m}1/|T|} \sum _{S\in \mathcal C_a(\mathcal W^m)}\dfrac{1}{|S||\mathcal C(S)|}=\dfrac{1}{\sum _{T\in \mathcal W^m}1/|T|} \sum _{S\in \mathcal W^m_a}\dfrac{1}{|S|^2}$$

Index $\varvec{\gamma }$ ($\mathcal Y=\mathcal W^s$)

$$\varvec{\gamma }_a =\dfrac{1}{\sum _{T\in \mathcal W^s}1/|T|} \sum _{S\in \mathcal C_a(\mathcal W^s)}\dfrac{1}{|S||\mathcal C(S)|}=\dfrac{1}{\sum _{T\in \mathcal W^s}1/|T|} \sum _{S\in \mathcal W^s_a}\dfrac{1}{|S|^2}$$

We conclude the section by showing the values of the different power indices considered in this paper in two simple games. The first game is the one defined in Example 1 (Table 1):

Example 1 revisited: Let $(N,\mathcal W^m)$ be the simple game, with $N = \{1,2,3,4,5\}$ and

$$ \mathcal W^m = \{ S\subseteq N :\; \mid S\mid =3\quad and \quad S\ne \{3,4,5\} \}.$$

Table 1. Power indices for the game in Example 1.

Example 2

Let $(N,\mathcal W^m)$ be the simple game with $N = \{1,2,3,4,5\}$ and

$$ \mathcal W^m = \{ \{1,2\} ,\{1,3,4\} ,\{1,3,5\}, \{2,3,4\} \}. $$

It holds that $5 \succ 4 \succ 3 \succ 2 \succ 1$, $\mathcal W^s = \{ \{1,2\} ,\{1,3,5\}, \{2,3,4\} \}$ and

$$\mathcal W^c = \{ \{12\},\{123\},\{124\},\{125\},\{134\} ,\{135\}, \{234\}, \{1235\}, \{1245\}, \{1345\},\{2345\} \}.$$

(the voters in each coalition are not separated by commas in this last set) (Table 2).

Table 2. Power indices for game in Example 2.

5 Ordinal Equivalence of the Three Power Indices Based on Critical Winning Coalitions

It is known [9] that in complete simple games, i.e., games for which any two players are comparable by the desirability relation, the hierarchy in the set of players induced by the Johnston and by the Banzhaf indices coincides with the hierarchy induced by the desirability relation. As it was shown in Sect. 2, both indices are obtained, from model 1 and from model 2 respectively, when $\mathcal Y=\mathcal W^c$. In this section we prove that the new $\varvec{\alpha }$ index, obtained from model 3 when $\mathcal Y=\mathcal W^c$, has the same property.

Proposition 5.1

Let v be a simple game on N and $a,b\in N$. Then,

• (i) $a \succsim b \quad \Rightarrow \quad \varvec{\alpha }_a\ge \varvec{\alpha }_b$.

• (ii) $a \succ b \quad \Rightarrow \quad \varvec{\alpha }_a> \varvec{\alpha }_b$.

Proof

 

• (i) Assume that $a \succsim b$ and let S be a coalition such that b is critical in it $(S\in \mathcal C_b(\mathcal W^c)$ or $b\in \mathcal C(S))$. There are two possibilities:

  • If $a\in S$, then $a\in \mathcal C(S)$, because $S\setminus \{b\}=(S\setminus \{a,b\})\cup \{a\} \notin \mathcal W$ implies $S\setminus \{a\}=(S\backslash \{a,b\})\cup \{b\} \notin \mathcal W$.

  • If $a \notin S$ then a is critical in $T=(S\setminus \{b\})\cup \{a\}$, because $S=(S\setminus \{b\})\cup \{b\}\in \mathcal W$ implies $T\in \mathcal W$, and $T\setminus \{a\}=S\setminus \{b\}\notin \mathcal W$. Now, it is $|T|=|S|$ and $|\mathcal C(T)|\le |\mathcal C(S)|$. This last inequality is due, on the one hand, to the fact that $a\in \mathcal C(T)$, $a\notin \mathcal C(S)$, $b\in \mathcal C(S)$ and $b\notin \mathcal C(T)$, and, on the other hand, because if $x\in \mathcal C(T)$ and $x\ne a$ then $x\in \mathcal C(S)$. Therefore, $\displaystyle {\dfrac{1}{|T||\mathcal C(T)|}\ge \dfrac{1}{|S||\mathcal C(S)|}}$.

  Thus, it holds

  $$\begin{aligned} \displaystyle {\sum _{T\in \mathcal C_a(\mathcal W^c)}\dfrac{1}{|T||\mathcal C(T)|}\ge \sum _{S\in \mathcal C_b(\mathcal W^c)}\dfrac{1}{|S||\mathcal C(S)|}}, \end{aligned}$$

  (4)

  and therefore, $\varvec{\alpha }_a\ge \varvec{\alpha }_b$.

• (ii) Assume that $a \succ b$, i.e., $a \succsim b$ and $b \succsim /a$. As $b \succsim /a$ there exists $M\subseteq N$ such that $a,b\notin M$, $M\cup \{a\} \in \mathcal W$ and $M\cup \{b\} \notin \mathcal W$. Thus, a is critical in $T=M\cup \{a\}$, and this coalition T cannot be obtained by either of the two cases analyzed in the first part of the proof. Thus, there is at least one more strictly positive addend in the left part of the inequality (4) than in the right part, and this implies that $\varvec{\alpha }_a> \varvec{\alpha }_b$.    $\square$

Two power indices are said to be ordinally equivalent in a given simple game if they induce the same hierarchy on the set of players. Two power indices are said to be ordinally equivalent in a class of simple games if they are ordinally equivalent for all games in the class.

The following Corollary is an immediate consequence of Proposition 5.1.

Corollary 5.2

The Banzhaf index, the Johnston index and the $\varvec{\alpha }$ index are ordinally equivalent in complete simple games.

6 Conclusion

We have seen that a single probabilistic unified approach serves to generate several families of power indices. Each family has three members according to the kind of winning coalitions considered. The unified approach admits several models that are generated by the probabilities assigned to coalitions. Thus, model 1 contains the Johnston; Deegan and Packel; and Alonso, Freixas and Molinero power indices, while model 2 contains the Banzhaf, Holler, and Alonso and Freixas power indices.

We have shown that some new models can naturally be defined by illustrating one of them that leads to three new power indices. It is remarkable that the new index based on winning coalitions containing crucial players is ordinally equivalent to the Johnston and to the Banzhaf indices in complete simple games.