Power, Cooperation Indices and Coalition Structures

Abstract

We introduce an allocation rule for measuring power in voting situations defined by a TU-game, a cooperation index and a coalition structure, and characterize it axiomatically. This rule is an extension of the Owen coalition value; in fact, also a variety of previously studied game situations is embodied and unified by our model. Two numerical examples illustrate the application of the new value.

Earlier versions of this article appeared in 2000 in Homo Oeconomicus 17, 11–29, and in 2001 as a chapter of Power Indices and Coalition Formation (M. J. Holler and G. Owen, eds), Kluwer, 153–173.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The main purpose of this chapter is to define a coalition value for TU-games endowed with a cooperation index and a coalition structure. The notion of cooperation index (equivalent to that of weighted hypergraph) was introduced in Amer and Carreras (1995). It provides the foundations for a quantitative theory of restricted cooperation that exhibits high precision and flexibility and generalizes several earlier qualitative methods. (For further details on the significance and scope of cooperation indices, we refer the reader to the above reference.) The value we associate with situations described by a game and a cooperation index is a generalization of the Shapley value.

A further step is then suggested by the usefulness of the coalition value as a tool for the analysis of the game dynamics—coalition formation—, which demands an extension of this concept to the new situations we are considering. In fact, this is a crucial point for a full development of the cooperation index theory, because it is only natural to suppose that the greatest incidence of a cooperation index will be precisely found in the bargaining process that leads to the formation of coalitions.

We have tried to find an axiomatic system as simple and powerful as possible to characterize the (generalized) coalition value. A strong symmetry principle (that of balanced contributions), already suggested in Myerson (1980) and in Hart and Mas-Colell (1989), has been used to this end. As a first application of this principle, we present in Sect. 2 a new axiomatization of the generalized Shapley value for games with a cooperation index. In Sect. 3, the (classical) coalition value is characterized by using two forms of the strong symmetry principle, one for players within any block and another for blocks of the coalition structure, together with a weak version of efficiency.

Next, still in Sect. 3, we define a (generalized) coalition value for game situations where not only a coalition structure but also a cooperation index are given and characterize it, using again two forms of the strong symmetry principle. Besides, some special cases are considered where our new coalition value reduces to more familiar values—in particular to the generalized Shapley value, and not only when the coalition structure is trivial—or remains unaltered after local modifications of the coalition structure.

Finally, two numerical examples are considered in Sect. 4. A concluding remark is in order. Both the Shapley and the coalition value have been commonly used as measures of power by applying them to simple games. One could then ask why we do not reduce ourselves to consider only this kind of games. The answer is that, as will be seen below, modifying a simple game by means of a cooperation index usually produces a non-simple game—from which we derive the generalized Shapley and coalition values—, still having a natural interpretation as a “political game”. Hence we develop our theory within the more general framework of (TU) cooperative games, although all our examples will start with a simple game.

1.1 Notation

We shall be concerned with games with transferable utility (TU-games), i.e. pairs $(N,v)$ where $N$ is a finite set of players and $v : 2^N \longrightarrow \mathbb{R}$ is the characteristic function, which assigns to every coalition $S \subseteq N$ a real number $v(S)$ and satisfies $v(\phi ) = 0$. A carrier for a game $(N,v)$ is a subset $K \subseteq N$ such that $v(S) = v(S \cap K)$ for any $S \subseteq N$. As pointed out in Roth (1988), a player $i \in N$ is null in $(N,v)$ if $v(S) = v(S\setminus \{i\})$ for all $S \subseteq N$. The function $v$ is said to be superadditive if $v(S \cup T) \ge v(S) + v(T)$ whenever $S \cap T = \phi$. If $T \subseteq S$ we shall write $S_T = S\setminus T$. Given a game $(N,v)$ and a coalition $T \subseteq N$, $v_T$ will denote the restriction of $v$ to $2^{N_T}$; it defines a game $(N_T,v_T)$.

Let $N$ be a finite set and let $g^N$ be the set of all unordered pairs (called links and written $i:j$) of distinct elements of $N$. Every $g \subseteq g^N$ is a graph on $N$, and one can then speak of paths and connected components in any $S \subseteq N$. A coalition structure in $N$ is a partition $\mathcal{B }$ of $N$ into nonempty subsets, called blocks. If $T \subseteq N$, $\mathcal{B }_T$ will denote the coalition structure induced by $\mathcal{B }$ in $N_T$. If $I \in \mathcal{B }$, $\mathcal{B }_I$ will denote the coalition structure $\mathcal{B }\setminus \{I\}$ in $N_I$. When $T = \{i\}$ we shall simply write $N_i$, $v_i$ and $\mathcal{B }_i$. Finally, given natural numbers $s \le n$ we define $\gamma (n,s) = \frac{(s-1)!(n-s)!}{n!}$. Further notation will be introduced below.

2 Game Situations and Allocation Rules

To solve a cooperative game is commonly interpreted as defining one or more payoff vectors that might be accepted by all the players according to some rationality criteria. In the case of simple games, which are very often used to represent political decision-making bodies, payoff vectors are usually interpreted as distributions of power among the agents. The Shapley value (Shapley 1953) is an essential contribution to this problem, because it applies to any game $(N,v)$ and selects for it a unique payoff vector $\Upphi (N,v) \in {\mathbb{R}}^N$, which assigns to every player $i \in N$ a payoff denoted by $\Upphi _i(N,v)$.

When considering games with additional information—not stored in the characteristic function—the preceding notions need to be generalized. A game situation will be a triple $(N,v,\mathcal{I })$, where $(N,v)$ is a game and $\mathcal{I }$ is a mathematical object that contains the external data we wish to take into account to study the game. An allocation rule will be a map $X$ that assigns to every game situation $(N,v,\mathcal{I })$ a payoff vector $X(N,v,\mathcal{I }) \in {\mathbb{R}} ^N$.

For instance, the Shapley value itself is an allocation rule for situations where $\mathcal{I } = \phi$; the Myerson value (Myerson 1977) is an allocation rule for situations of the form $(N,v,g)$, where $g$ is a communication graph on $N$; the Aumann-Drèze value (Aumann and Drèze 1974) and the coalition value (Owen 1977; see also Owen 1995) are allocation rules for situations $(N,v,\mathcal{B })$, where $\mathcal{B }$ is a coalition structure in $N$.

This section is devoted to recall the generical principle of strong symmetry and to obtain a new characterization for the generalized Shapley value associated with game situations defined by a cooperation index. Roughly speaking, the principle states: the variation that the payoff to player $i$ undergoes when player $j$ (and all additional information concerning him) leaves the game must be equal to the variation of the payoff to player $j$ if $i$ leaves the game.

A version of this principle has already been used by Myerson (1980), with the name of “balanced contributions”, to characterize an extension of the Myerson value to NTU-games endowed with a (unweighted) communication hypergraph. Hart and Mas-Colell (1989) use another form of the principle, together with efficiency, to axiomatize the Shapley value. As they point out (about their version), “the principle is a straightforward generalization of the equal division of surplus idea for two-person problems and seems to be a most natural way to compare the relative position (or strengths) of the players.”

Here, we wish only to point out that “elementary” proofs (by induction on the number of players) for both the characterization of the Shapley value (without using potential theory) and that of the Myerson value (for TU-games) can be achieved using the standard technique of Theorem 2.1.

For the sake of completeness and also for their repeated use in Sect. 3, we recall some definitions and results from Amer and Carreras (1995). A game situation with a cooperation index is a triple $(N,v,p)$ whose third component is a function $p : 2^N \longrightarrow [0,1]$ such that $p(\{i\}) = 1$ for all $i \in N$. Generalizing Myerson’s (1980) terminology, every $T\subseteq N$ such that $p(T) > 0$ will be called a $p$-conference. Overlapping conferences define in a natural way “paths” between players, and hence a notion of connectedness; the connected components, called islands, form a partition $N/p$ of $N$. More generally, $P^{+}(S,p)$ will denote the set of partitions of a given $S\subseteq N$ into conferences. If $T\subseteq N$, $p_T$ will denote the restriction of $p$ to $2^{N_T}$, and will be written $p_i$ when $T = \{i\}$.

Finally, we recall (Amer and Carreras 1995, Theorem 4.1) that there exists a unique allocation rule $\Uppsi$, applicable to every game situation with a cooperation index $(N,v,p)$, that satisfies the following axioms:

• 1. Local superefficiency: for any island $I\in N/p$

  $$ \sum \limits _{i \in I} \Uppsi _i(N,v,p) = \max _{P \in P^{+}(I,p)} \sum \limits _{T \in P} v(T)p(T). $$

• 2. Fairness: Given $R\subseteq N$ and indices $p_1, p_2$ such that $p_1(S) = p_2(S)$ for all $S \ne R$,

  $$ \Uppsi _i(N,v,p_1) - \Uppsi _i(N,v,p_2) = \Uppsi _j(N,v,p_1) - \Uppsi _j(N,v,p_2) \qquad \forall i,j \in R. $$

This allocation rule, that will be called the generalized Shapley value, is defined by $\Uppsi (N,v,p) = \Upphi (N,v/p)$, where $(N,v/p)$ is the $p$-restricted game given by

$$ (v/p)(S) = \max _{P \in P^{+}(S,p)} \sum \limits _{T \in P} v(T)p(T) \qquad \forall S \subseteq N.$$

Our alternative characterization for $\Uppsi$ is as follows.

Theorem 2.1

There exists a unique allocation rule$X$, applicable to every game situation with a cooperation index$(N,v,p)$, that satisfies the following axioms:

• 1. Local superefficiency;

• 2. Strong symmetry: if$i,j \in T$ and$T$ is a$p$-conference,

  $$X_i(N,v,p) - X_i(N_j,v_j,p_j) = X_j(N,v,p) - X_j(N_i,v_i,p_i). $$

This rule is$X = \Uppsi$, the generalized Shapley value.

Proof

(Existence) It suffices to show that $\Uppsi$ satisfies strong symmetry. From the fact that $P^{+}(S,p_i) = P^{+}(S,p)$ for any $S \subseteq N_i$ it follows that $v_i/p_i = (v/p)_i$ and, given that $\Uppsi (N,v,p) = \Upphi (N,v/p)$, strong symmetry for $\Uppsi$ is a consequence of the Shapley value strong symmetry (see e.g. Hart and Mas-Colell 1989).

(Uniqueness) Let $X^1, X^2$ be allocation rules satisfying (1) and (2). We shall show, by induction on $n = | N |$, that $X^1(N,v,p) = X^2(N,v,p)$ for any game situation $(N,v,p)$. If $n = 1$ only local superefficiency matters. Let $n > 1$. For any $i, j \in T$, $T$ being any island, strong symmetry says that

$$\begin{aligned}&X^1_i(N,v,p) - X^1_i(N_j,v_j,p_j) = X^1_j(N,v,p) - X^1_j(N_i,v_i,p_i),\\&X^2_i(N,v,p) - X^2_i(N_j,v_j,p_j) = X^2_j(N,v,p) - X^2_j(N_i,v_i,p_i). \end{aligned}$$

Subtracting these equalities and using the inductive hypothesis it follows that

$$ X^1_i(N,v,p) - X^2_i(N,v,p) = X^1_j(N,v,p) - X^2_j(N,v,p), $$

and hence the function $d$, given by $d(i) = X^1_i(N,v,p) - X^2_i(N,v,p)$, is a constant function on each island $I \in N/p$. Using now local superefficiency, $X^1_i(N,v,p) = X^2_i(N,v,p)$ is true within each island, and hence in $N$.$\square$

Let us consider, now, a first example of application of the generalized Shapley value that shows how to get an a priori evaluation of the power distribution when a cooperation index matters.

Example 2.2

Let $(N,v)$ be the straight majority game $[2;1,1,1]$, that is, the game where

$$ v(S) = 1 \quad \text{ if} \qquad \vert S \vert \ge 2, \qquad v(S) = 0 \quad \text{ otherwise}, $$

and let $p$ be the cooperation index given as follows:

$$\begin{aligned}&p(\{i\}) = 1 \quad \text{ for}\quad i = 1,2,3; \quad p(\{1,2\}) = 0.7;\\&p(\{1,3\}) = 0.5; \quad p(\{2,3\}) = 0; \quad p(N) = 0. \end{aligned}$$

The modified game $(N,v/p)$ is given by

$$\begin{aligned}&(v/p)(\{i\}) = 0 \quad \text{ for}\quad i = 1,2,3; \quad (v/p)(\{1,2\}) = 0.7;\\&(v/p)(\{1,3\}) = 0.5; \quad (v/p)(\{2,3\}) = 0; \quad (v/p)(N) = 0.7 \end{aligned}$$

and the modified Shapley value is

$$ \Uppsi (N,v,p) = \Upphi (N,v/p) = (0.4333,0.1833,0.0833), $$

whereas the Shapley value for the original game is constant:

$$ \Upphi (N,v) = (0.3333,0.3333,0.3333). $$

The modified value reflects that player 1 is the best placed to form coalitions and to take profit; player 2 is also in a better position than player 3. In the original game the players shared 1, whereas in the modified one this amount is reduced to 0.7. A possible interpretation of this fact is the following: if the players play the game many times, they will form different coalitions depending on the play, but, in the end, they will share an average of 0.7 per play (if the cooperation index remains unaltered). This seems to be the case of political parties that, instead of forming a coalition for the entire legislature, sign partial commitments with different groups depending on the issue and obtain, then, an inefficient distribution of power.

3 Coalition Value and Cooperation Indices

The coalition value is an allocation rule for game situations with a coalition structure $(N,v,\mathcal{B })$. It differs from the Aumann-Drèze value in that it does not consider $\mathcal{B }$ as a final structure for the game but as a starting point for further negotiations at a higher level (that of blocks in the quotient game): this difference is reflected in the efficiency condition. The coalition value generalizes the Shapley value, which arises not only when $\mathcal{B } = \{N\}$ but also when $\mathcal{B } = \{\{i\} / i \in N\}$: these are the so-called trivial structures. Characterizations somewhat different from the original one may be found, e.g., in Hart and Kurz (1983) and Winter (1992).

Our first result in this section states a new axiomatization for the coalition value, using the strong symmetry principle at two levels: for individuals (players) and for blocks. Note that this allows us to dispense with the null-player and additivity axioms, which are necessary in other formulations mentioned above. It will be useful, throughout this section, to write

$$ X_K(N,v,\mathcal{I })= \sum \limits _{i \in K} X_i(N,v,\mathcal{I }) $$

for any allocation rule $X$ and any $K \subseteq N$.

Theorem 3.1

There exists a unique allocation rule$X$, applicable to every game situation with a coalition structure$(N,v,\mathcal{B })$, that satisfies the following axioms:

• 1. Efficiency: $\sum \nolimits _{i \in N} X_i(N,v,\mathcal{B }) = v(N)$;

• 2. Block strong symmetry: for all $I,J \in \mathcal{B }$

  $$X_I(N,v,\mathcal{B }) - X_I(N_J,v_J,\mathcal{B }_J) = X_J(N,v,\mathcal{B }) - X_J(N_I,v_I,\mathcal{B }_I); $$

• 3. Inner strong symmetry: for all $K \in \mathcal{B }$ and all $i,j \in K$

  $$ X_i(N,v,\mathcal{B }) - X_i(N_j,v_j,\mathcal{B }_j) = X_j(N,v,\mathcal{B }) - X_j(N_i,v_i,\mathcal{B }_i). $$

This rule is$X = {\hat{y}}$, the coalition value.

Proof

(Existence) Since our efficiency axiom already appears in other axiomatizations of the coalition value (e.g. Winter 1992), it is sufficient to check that ${\hat{y}}$ satisfies both strong symmetry postulates. Let ${\mathcal{B}} = \{K^{1},K^{2},\ldots,K^{m}\}$, $M = \{1,2,\ldots ,m\}$ be a set of representatives and $(M,u)$ be the quotient game of $(N,v)$ by $\mathcal{B }$, defined by

$$ u(T) = v\biggl (\bigcup \limits _{q \in T} K^q\biggl ) \qquad \forall T \subseteq M.$$

(Block strong symmetry) We know (Owen 1977) that for any block, say, $K = K^r$,

$$ {\hat{y}}_K(N,v,\mathcal{B }) = \sum \limits _{i \in K} {\hat{y}}_i(N,v,\mathcal{B }) = \Upphi _r(M,u). $$

Moreover, if $I = K^{i}$ and $(M_i,w)$ is the quotient game of $(N_I,v_I)$ by $\mathcal{B }_I$, it follows that $w = u_i$. The Shapley value strong symmetry yields therefore, for all blocks $I = K^{i}$ and $J = K^{j}$,

$$\begin{aligned}&{\hat{y}}_I(N,v,\mathcal{B }) - {\hat{y}}_I(N_J,v_J,\mathcal{B }_J) = \Upphi _i(M,u) - \Upphi _i(M_j,u_j) \\&\qquad = \Upphi _j(M,u) - \Upphi _j(M_i,u_i) = {\hat{y}}_J(N,v,\mathcal{B }) - {\hat{y}}_J(N_I,v_I,\mathcal{B }_I). \end{aligned}$$

(Inner strong symmetry) Let $K = K^r \in \mathcal{B }$ and assume that $i,j \in K$. The explicit formula for the coalition value (Owen 1977) gives

$$ {\hat{y}}_i(N,v,\mathcal{B }) = \sum \limits _{\begin{array}{c} T \subseteq M\\ r \notin T \end{array}} \sum \limits _{\begin{array}{c} S \subseteq K\\ i \in S \end{array}} \gamma (m,t+1)\gamma (k,s)[v({\tilde{T}} \cup S) - v({\tilde{T}} \cup S_i)] $$

where ${\tilde{T}} = \cup _{q \in T} K^q$, and $m$, $t$, $k$ and $s$ are, respectively, the cardinalities of $M$, $T$, $K$ and $S$. Applying again Owen’s formula we obtain

$$ {\hat{y}}_i(N_j,v_j,\mathcal{B }_j) = \sum \limits _{\begin{array}{c} T \subseteq M\\ r \notin T \end{array}} \sum \limits _{\begin{array}{c} S \subseteq K_j\\ i \in S \end{array}} \gamma (m,t+1)\gamma (k-1,s)[v({\tilde{T}} \cup S) - v({\tilde{T}} \cup S_i)].$$

A straightforward calculation leads to the following equality:

$$\begin{aligned}&{\hat{y}}_i(N,v,\mathcal{B }) - {\hat{y}}_i(N_j,v_j,\mathcal{B }_j)\\=&\qquad \; \sum \limits _{\begin{array}{c} T \subseteq M\\ r \notin T \end{array}} \sum \limits _{\begin{array}{c} S \subseteq K\\ i,j \in S \end{array}} \gamma (m,t+1) \gamma (k,s)[v({\tilde{T}} \cup S) - v({\tilde{T}} \cup S_i) - v({\tilde{T}} \cup S_j) + v({\tilde{T}} \cup S_{\{i,j\}})]. \end{aligned}$$

The symmetrical appearance of $i$ and $j$ in this expression justifies that

$$ {\hat{y}}_i(N,v,\mathcal{B }) - {\hat{y}}_i(N_j,v_j,\mathcal{B }_j) = {\hat{y}}_j(N,v,\mathcal{B }) - {\hat{y}}_j(N_i,v_i,\mathcal{B }_i). $$

(Uniqueness) Let $X^1$, $X^2$ be allocation rules satisfying (1)–(3). We shall show, by induction on $n = |N|$, that $X^1(N,v,\mathcal{B }) = X^2(N,v,\mathcal{B })$ for all game situations $(N,v,\mathcal{B })$. For $n = 1$ this follows from efficiency. Let $n > 1$. Block strong symmetry and the inductive hypothesis imply that the function $d$, defined by $d(I) = X^1_I(N,v,\mathcal{B }) - X^2_I(N,v,\mathcal{B })$ for every $I \in \mathcal{B }$, is constant. Efficiency implies that $d$ vanishes. Inner strong symmetry and the induction hypothesis apply to prove that the function $\delta _I$, defined by $\delta _I(i) = X^1_i(N,v,\mathcal{B }) - X^2_i(N,v,\mathcal{B })$ within each block $I \in \mathcal{B }$, is constant on $I$. In fact, $\delta _I$ vanishes too, since $0 = d(I) = \sum \nolimits _{i \in I} \delta _I(i)$, and hence $X^1_i(N,v,\mathcal{B }) = X^2_i(N,v,\mathcal{B })$ for all $i \in I$ and all $I \in \mathcal{B }$, i.e. for all $i \in N$. $\square$

The coalition value has been used to study the dynamics of coalition formation in game situations of types that could be described by particular cooperation indices. For example, in Carreras and Owen (1988) and (1996), Carreras et al. (1993), and Bergantiños (1993): all these papers show applications of game theory to political science. The procedure is always based on the computation of the coalition value for the ${\mathcal{I}}$-restricted game under different coalition structures that are considered “plausible” according to $\mathcal{I }$. This suggests, in fact, that a set of new allocation rules—one for each type of situation—can be defined in this way, and it seems therefore interesting to find a common axiomatic characterization for them. (We also provide in Sect. 4 two numerical examples illustrating that procedure.)

In order to generalize the coalition value to qualitatively restricted game situations, the case of $(N,v,g,\mathcal{B })$ is perhaps a most basic step in this program and, indeed, what might be called the Myerson coalition value has been defined and axiomatized in Vázquez-Brage et al. (1996). In the present work, we complete this approach by adopting the widest point of view, that of the cooperation indices, and study therefore a game situation of the form $(N,v,p,\mathcal{B })$. A (generalized) coalition value is defined and characterized using the strong symmetry principle.

Let us consider a game situation $(N,v,p,\mathcal{B })$, where $p$ is a cooperation index and $\mathcal{B }$ is a coalition structure. We will use definitions and results from Amer and Carreras (1995) that have been remembered in Sect. 2, just preceding Theorem 2.1. One more definition is needed: we shall say that two $\mathcal{B }$-blocks are linked by $p$ if there exists a $p$-conference that intersects both blocks. This defines a graph on $\mathcal{B }$ and allows us to speak of paths between blocks: the connected components of $\mathcal{B }$ relatively to this graph will be called superblocks.

We define an allocation rule $V$, applicable to every game situation of the form $(N,v,p,\mathcal{B })$, as follows:

$$ V(N,v,p,\mathcal{B }) = {\hat{y}}(N,v/p,\mathcal{B }), $$

where $v/p$ is the $p$-restricted game. We call $V$ the generalized coalition value.

Theorem 3.2

There exists a unique allocation rule$X$, applicable to every game situation$(N,v,p,\mathcal{B })$, that satisfies the following axioms:

• 1. Local superefficiency: for every island $I{\in N/p}$

  $$ \sum \limits _{i \in I} X_i(N,v,p,\mathcal{B }) = \max _{P \in P^{+}(I,p)} \sum \limits _{T \in P} v(T)p(T); $$

• 2. Block strong symmetry: if $R,S \in \mathcal{B }$ are linked by $p$

  $$\begin{aligned}&X_R(N,v,p,\mathcal{B }) - X_R(N_S,v_S,p_S,\mathcal{B }_S) \\&\qquad= X_S(N,v,p,\mathcal{B }) - X_S(N_R,v_R,p_R,\mathcal{B }_R); \end{aligned}$$

• 3. Inner strong symmetry: for all $R \in \mathcal{B }$ and all $i,j \in R$

  $$ X_i(N,v,p,\mathcal{B }) - X_i(N_j,v_j,p_j,\mathcal{B }_j) = X_j(N,v,p,\mathcal{B }) - X_j(N_i,v_i,p_i,\mathcal{B }_i). $$

This rule is$X = V$, the generalized coalition value.

Proof

(Existence) We will prove that $V$ satisfies properties (1)–(3). Let $(N,v,p,\mathcal{B })$ be a given situation. (Local superefficiency) Define, for any island $I \in N/p$, a game $u^{I}$ in $N$ as follows:

$$ u^{I}(S) = \max _{P \in P^{+}(I \cap S,p)} \sum \limits _{T \in P} v(T)p(T) \qquad \forall S \subseteq N.$$

If $N/p = \{I_1,I_2,\dots ,I_k\}$, it can be shown (Amer and Carreras 1995, Proposition 3.5) that

$$ v/p = \sum \limits _{r=1}^k u^{I_r}.$$

Since each $I \in N/p$ is a carrier for $u^{I}$, the additivity of the classical coalition value yields, for every island $I$,

$$ \sum \limits _{i \in I} V_i(N,v,p,\mathcal{B }) = \sum \limits _{i \in I} {\hat{y}}_i(N,u^{I},\mathcal{B }) = u^{I}(N) = \max _{P \in P^{+}(I,p)} \sum \limits _{T \in P} v(T)p(T). $$

(Block strong symmetry) This directly follows from the block strong symmetry of the coalition value ${\hat{y}}$, because $v_R/p_R = (v/p)_R$ for every block $R \in \mathcal{B }$. (Inner strong symmetry) The property derives, once more, from the corresponding property of the classical coalition value, using in this case that $v_i/p_i = (v/p)_i$ for any $i \in N$.

(Uniqueness) Let $X^1$, $X^2$ be allocation rules that satisfy (1)–(3). We shall show, by induction on $n = |N|$, that $X^1(N,v,p,\mathcal{B }) = X^2(N,v,p,\mathcal{B })$ for any game situation $(N,v,p,\mathcal{B })$. For $n = 1$ use local superefficiency only. Let $n > 1$. Block strong symmetry and the inductive hypothesis imply, as in Theorem 3.1, that the function $d$, defined by $d(R) = X^1_R(N,v,p,\mathcal{B }) - X^2_R(N,v,p,\mathcal{B })$ for every $R \in \mathcal{B }$, is constant on every superblock of $\mathcal{B }$. Then, every superblock $\mathcal{U }$ is, as a subset of $N$, isolated with respect to $p$-connectedness, and hence $\mathcal{U }$ is the union of some islands, say, $I_{1},I_{2},\ldots ,I_p$. If $R_1,R_2,\ldots ,R_q$ are the blocks which form $\mathcal{U }$, we have

$$\begin{aligned} \sum \limits _{h=1}^q d(R_h) &= \sum \limits _{h=1}^q X^1_{R_h}(N,v,p,\mathcal{B }) - \sum \limits _{h=1}^q X^2_{R_h}(N,v,p,\mathcal{B }) \\ &= \sum \limits _{t=1}^p X^1_{I_t}(N,v,p,\mathcal{B }) - \sum \limits _{t=1}^p X^2_{I_t}(N,v,p,\mathcal{B })\\ &= \sum \limits _{t=1}^p (v/p)(I_t)- \sum \limits _{t=1}^p (v/p)(I_t) = 0, \end{aligned}$$

and, $d$ being a constant function on $\mathcal{U }$, it follows that $d(R) = 0$ for any $R$ in $\mathcal{U }$ and therefore for any $R \in \mathcal{B }$, since $\mathcal{U }$ was arbitrary. Finally, let $i,j \in R \in \mathcal{B }$. Inner strong symmetry and the inductive hypothesis apply to show that the function $d_R$, defined by $d_R(i) = X^1_i(N,v,p,\mathcal{B }) - X^2_i(N,v,p,\mathcal{B })$ for every $i \in R$, is constant. Using that $\sum \nolimits _{i \in R} d_R(i) = d(R) = 0$ we conclude that $d_R$ vanishes. Thus, we have $X^1_i(N,v,p,\mathcal{B }) = X^2_i(N,v,p,\mathcal{B })$ for every $i \in R$ and every $R \in \mathcal{B }$, i.e. for every $i \in N$. $\square$

Now, let us describe the behavior of the generalized coalition value $V$ in some special cases of game situations of the form $(N,v,p,\mathcal{B })$.

Examples 3.3

(a) If $p(S) = 1$ for all $S \subseteq N$, then $v/p = v^{e}$ (the superadditive extension of $v$) and $V(N,v,p,\mathcal{B }) = {\hat{y}}^{e}(N,v,\mathcal{B })$, where ${\hat{y}}^{e}$ denotes the IR-coalition value defined by ${\hat{y}}^{e}(N,v,\mathcal{B }) = {\hat{y}}(N,v^{e},\mathcal{B })$. If, moreover, $v$ is superadditive, then $V(N,v,p,\mathcal{B }) = {\hat{y}}(N,v,\mathcal{B })$.

(b) When $\mathcal{B } = \{N\}$, block strong symmetry does not matter, whereas the two other axioms in Theorem 3.2 become those imposed to $\Uppsi$ in Theorem 2.1; therefore, $V(N,v,p,\{N\}) = \Uppsi (N,v,p)$.

(c) In a similar way, if $\mathcal{B } = \{\{i\} / i \in N\}$, inner strong symmetry does not say anything, the two other axioms coincide with those of Theorem 2.1 and, again, $V(N,v,p,\{\{i\} / i \in N\}) = \Uppsi (N,v,p)$.

(d) Assume $v$ is superadditive, let $\mathcal{B }$ be arbitrary and take $p = p_\mathcal{B }$, defined by

$$p_\mathcal{B }(S) = \left\{ \begin{array}{ll} 1&\text{if}\; S\subseteq K \text{for some}\; K \in \mathcal{B }, \\ 0&\text{ otherwise.} \end{array}\right. $$

The meaning of $p_\mathcal{B }$ is obvious: the players may freely negotiate among them within each block, but they cannot communicate at all with players belonging to other blocks. Then, $V(N,v,p_\mathcal{B },\mathcal{B })=\Upphi _0(N,v,\mathcal{B }) = \Uppsi (N,v,p_\mathcal{B })$, where $\Upphi _0$ is the Aumann-Drèze value. Note that the generalized values $V$ and $\Uppsi$ coincide, even though $\mathcal{B }$ is not trivial but arbitrary, and that the Aumann-Drèze value is shown to be a particular case of the generalized coalition value.

To analyze the following examples we need some elementary properties of the coalition value. Every game $v$ in $N$ can be uniquely written as $v = \sum \nolimits _{T \subseteq N} a_T u_T$, where $u_T$ is the $T$-unanimity game in $N$ and $a_T = \sum \nolimits _{R \subseteq T} (-1)^{t-r} v(R)$ for every nonempty coalition $T \subseteq N$ ($t$ and $r$ are the cardinalities of $T$ and $R$).

Remark 3.4

If $K$ is a carrier for $(N,v)$, then $a_T = 0$ for all $T$ not contained in $K$. From this it follows immediately that if a block of $\mathcal{B }$ is a carrier for $(N,v)$ then ${\hat{y}}(N,v,\mathcal{B })=\Uppsi (N,v)$.

Remark 3.5

Let $(N,v)$ be a game and let $\mathcal{B} = \{K_{1},K_{2},\ldots ,K_{m}\}$ be a coalition structure such that $K_1 = K^{\prime }_0 \cup K^{\prime }_1$, $K^{\prime }_0 \cap K^{\prime }_1 = \emptyset$ and all members of $K^{\prime }_0$ are null players in $(N,v)$. Let $\mathcal{B }^{\prime } = \{K^{\prime }_0,K^{\prime }_1,K_2,\ldots ,K_m\}$. Then

$$ {\hat{y}}(N,v,\mathcal{B }) = {\hat{y}}(N,v,\mathcal{B }^{\prime }). $$

Examples 3.6

(a) If $\mathcal{B } = N/p$, then $V(N,v,p,N/p) = \Uppsi (N,v,p)$, since applying the coalition value additivity to $v/p = \sum \nolimits _{I \in N/p} u^{I}$ (recall the proof of Theorem 3.2) yields $V(N,v,p,N/p) = \sum \nolimits _{I \in N/p} {\hat{y}}(N,u^{I},N/p)$, and, using that each island $I \in N/p$ is a carrier for $(N,u^{I})$, Remark 3.4 above gives

$$ V(N,v,p,N/p) = \sum \limits _{I \in N/p} {\hat{y}}(N,u^{I},N/p) = \Uppsi (N,v/p) = \Uppsi (N,v,p). $$

We meet again a situation where $\mathcal{B }$ is not trivial but the generalized values $V$ and $\Uppsi$ coincide.

(b) Let $(N,v,p,\mathcal{B })$ be a game situation where $\mathcal{B } = \{K_1,K_2,\ldots ,K_m\}$, and assume that $K_1 = K^{\prime }_0 \cup K^{\prime }_1$, $K^{\prime }_0 \cap K^{\prime }_1 = \emptyset$ and $K^{\prime }_0$, $K^{\prime }_1$ are nonempty and lie in different islands. Let $\mathcal{B }^{\prime } = \{K^{\prime }_0,K^{\prime }_1,K_2,\ldots ,K_m\}$. Therefore

$$ V(N,v,p,\mathcal{B }) = V(N,v,p,\mathcal{B }^{\prime }). $$

To prove this we apply again the coalition value additivity to $v/p = \sum \nolimits _{I \in N/p} u^{I}$ and use Remark 3.5 to obtain

$$ V(N,v,p,\mathcal{B }) = \sum \limits _{I \in N/p} {\hat{y}}(N,u^{I},\mathcal{B }) = \sum \limits _{I \in N/p}{\hat{y}}(N,u^{I},\mathcal{B }^{\prime }) = V(N,v,p,\mathcal{B }^{\prime }). $$

Some comments are in order: we have never demanded any kind of compatibility, between the cooperation index $p$ (or its islands) and the coalition structure $\mathcal{B }$, to formalize the theory in this section. But, as follows from our latter statement, the players will have no interest in forming blocks with members of other islands, and therefore the only interesting coalition structures are, in practice, those where each island splits into blocks; thus, superblocks (defined before Theorem 3.2) are reduced to be islands.

(c) Let us assume, now, that a block is included in an island but is not connected (by conferences). Then, this block cannot split into connected components without changing the coalition value, as the following counterexample shows. Let $N = \{1,2,3\}$ and $v(S) = 1$ if $|S| \ge 2$, $v(S) = 0$ otherwise. Let $p$ be the cooperation index defined by $p(S) = 0$ if $S = \{2,3\}$ and $p(S) = 1$ otherwise, and let $\mathcal{B } = \{\{1\},\{2,3\}\}$. Then, $(v/p)(S) = v(S)$ if $S \ne \{2,3\}$ and $(v/p)(\{2,3\}) = 0$; thus, $V(N,v,p,\mathcal{B }) = (0.50,0.25,0.25)$. If block $\{2,3\}$ is subdivided, a new coalition structure $\mathcal{B }^{\prime } = \{\{1\},\{2\}, \{3\}\}$ arises, for which $V(N,v,p,\mathcal{B }^{\prime }) = (0.66,0.16,0.16)$.

An obvious question: if players $2$ and $3$ cannot communicate because $p(\{2,3\}) = 0$, how can they form a block in $\mathcal{B }$? The null cooperation index assigned to $\{2,3\}$ means that they will not agree to form a coalition, but they may agree in other questions, e.g. in that they will never form separately a coalition with player $1$! A situation of this kind arose at the beginning of 1993 in the Parliament of Aragón (Spain). Parties $1$ and $2$ were holding a coalition government, but a proposal of party $2$ about a deep amendment of the Autonomy Statute was refused with the votes of parties $1$ and $3$ ($2$ is a regionalist party, whereas $1$ and $3$ are the main parties at the national level and are not especially inclined to give further competences to regions).

4 Two Examples

This final section is devoted to considering two numerical instances where we shall use the generalized coalition value as a “dynamic” measure of power, leaving to the generalized Shapley value the “static” role of describing the initial conditions for the bargaining.

Example 4.1

Let us consider a parliamentary body where four parties share 50 seats, giving rise to the weighted majority game $(N,v) \equiv [26;20,15,11,4]$. Formally, this is a very simple situation. Any coalition formed by two of the three main parties is stable, because the classical coalition value allocates 0.5 units to each one of its members and they cannot better this allocation by going elsewhere. But, perhaps, things are not so simple. Assume that parties are politically located in a classical left-to-right axis as is shown in Fig. 1.

Fig. 1

Party-distribution on a left-to-right axis in Example 4.1

To take into account this ideological component, we introduce a cooperation index $p$, derived from the distances between parties. For instance, we find

$$ \begin{aligned}p(\{1,2\})&= 1 - d(1,2) = 0.3000 \\ p(\{1,3,4\})&= 1 - \sqrt{d(1,4)^2 + d(4,3)^2} = 0.7764 \end{aligned}$$

and so on, until

$$ p(N) = 1 - \sqrt{d(1,4)^2 + d(4,3)^2 + d(3,2)^2} = 0.5417. $$

The modified game is therefore

$$\begin{aligned}v/p = &\;0.3 \,u_{\{1,2\}} + 0.7 \,u_{\{1,3\}} + 0.6 \,u_{\{2,3\}}\\&\; - 0.9 \,u_{\{1,2,3\}} + 0.1615 \,u_{\{1,2,4\}} + 0.0764 \,u_{\{1,3,4\}}- 0.1615 \,u_N. \end{aligned}$$

From looking at the initial configuration, given by

$$ \Uppsi (N,v,p) = (0.2389,0.1635,0.3351,0.0389), $$

it follows that party 3 is really the strongest player. An evaluation of the generalized coalition value $V(N,v,p,\mathcal{B })$ for different coalition structures—essentially, those where only a $v$-winning coalition forms—is provided in Table 1, where the first row gives the generalized Shapley value. It tells us that $\mathcal{B } = \{\{1\},\{2,3\},\{4\}\}$ is the only stable one, and yields

$$ V(N,v,p,\mathcal{B }) = (0.0755,0.2519,0.4236,0.0255). $$

(Note that player 1 is indifferent between coalitions $\{1,3\}$ and $\{1,2,4\}$, player 2 is indifferent between $\{2,3\}$ and $\{1,2,4\}$, player 3 between $\{2,3\}$ and $\{1,3,4\}$, and player 4 would prefer that coalition $\{1,2\}$ forms. Player 4 might thus promote coalition $\{1,2,4\}$ and leave it immediately, but the residual coalition $\{1,2\}$ would then dissolve because player 2 prefers to enter $\{2,3\}$).

Table 1 Generalized coalition values in Example 4.1

Thus, coalition $\{2,3\}$ is not “winning” in the classical sense. It obtains $V_{\{2,3\}}(N,v,p,\mathcal{B }) = 0.6755$, which is more than $(v/p)(\{2,3\}) = 0.6000$ but far from $(v/p)(N) = 0.7764$, and the difference is allocated to players 1 and 4 (which is no longer a dummy player because of its central position). This may be interpreted as caused by disagreements between players 2 and 3, which will be often obliged to negotiate with 1 and/or 4. On the other hand, player 3 receive much more than player 2, and this is in accordance with Owen’s (1977) intracoalitional bargaining model if one compares the allocations to players 1, 2, and 3 under $\{1,2\}$ and $\{1,3\}$ in $v/p$. Summing up, the modified model seems to provide a more realistic view of the political complexity of this situation.

Before proceeding with our second example—the analysis of a real world situation—, the question of how to determine a cooperation index is worthy of mention. The cooperation degree of a given coalition (say, of parties) may depend on many factors: pure ideological positions, strategic conveniences, past experience, future compromises, existence of simultaneous settings where the involved parties (or some of them) are meeting and probably bargaining... In Example 4.1 we have suggested a way for computing the cooperation index exclusively in terms of the left-to-right ideological positions. If one wants to take into account additional components that influence the relationships between parties, two main procedures seem to be plausible.

The first one is purely theoretical, and needs to assume that every factor can be numerically described. In this case, the basic point will be to find a function, of as many variables as factors we have so defined, mapping in a reasonable way the domain of these variables (a cartesian product) into the interval $[0,1]$ of the real line. In our opinion, this is an interesting field of research.

The second method is rather of empirical nature, no necessarily more subjective than the former and, surely, easier to use in practice. By enquiring appropriate people, one can obtain a good estimation of the cooperation degree of every coalition. “Appropriate people” means here, e.g., party leaders or spokesmen, political scientists and observers, mass media (press, radio, television) commentators and, still better, a combination of all of them. A comparison of parties’ programatic manifestos should be added as a complementary way (last, but not least) for obtaining the cooperation degree of any coalition. Other possibilities will be welcome.

In the following example we have assumed the role of political observers, and have established what we feel is a reasonable cooperation index in view of the actual behavior of the involved parties.

A final remark on this question. The coalition value is a continuous function of the unanimity coordinates of the game, for it is linear. On the other hand, the unanimity coordinates of the modified game $v/p$ are easily seen to be continuous functions of the cooperation index $p$, viewed as a vector variable in the $(2^n-n-1)$-dimensional unit cube. Thus we conclude that the generalized coalition value is a continuous function of the cooperation index, and hence small enough errors in evaluating $p$ will give rise to negligible differences in our analysis of the coalition dynamics of a game by means of $V$ (as can be checked in Example 4.1).

Example 4.2

The case of the Congreso de los Diputados (Lower House of the Spanish Parliament) during the 1993–1996 Legislature will be studied here. Eleven parties elected members to the Congreso in June 1993, giving rise to the following weighted majority game:

$$ (N,v) \equiv [176;159,141,18,17,5,4,2,1,1,1,1]. $$

This is an “apex game”, because all but the four main parties are null players and the set of minimal winning coalitions is

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

Disregarding the null players, we obtain a 4-person game whose Shapley value is given by

$$ \Upphi (N,v) = (0.5000,0.1667,0.1667,0.1667). $$

Formally, the coalition formation is easy to analyze. Only the minimal winning coalitions are stable, and yield the following coalition values:

$$ {\hat{y}}(N,v,\{1,2\}) = (0.6667,0.3333,0,0) $$

(and analogous results for the two other binary coalitions) and

$$ {\hat{y}}(N,v,\{2,3,4\}) = (0,0.3333,0.3333,0.3333) $$

(an oversized majority such as $\{1,i,j\}$ allocates the same payoff to player 1 as $\{1,i\}$ or $\{1,j\}$, but divides 0.3333 equally among $i$ and $j$ and is therefore not interesting for these two players).

There are, however, complex relationships between the Spanish parties. We shall introduce a cooperation index to describe the political structure and will then obtain very different and much more clear results in analyzing the coalition formation. For a better understanding of our index, let us first identify the agents of our game.

Player 1 is the Partido Socialista Obrero Español (PSOE), a left-to-center party that obtained absolute majority in 1982 and 1986 and just 175 seats in 1989. Player 2 is the Partido Popular (PP), a strong and growing center-right party. Player 3 is Izquierda Unida (IU), a coalition headed by the old communist party. Player 4 is Convergència i Unió (CiU), a regionalist middle-of-the-road coalition which was enjoying absolute majority in the Catalonian Parliament since 1984 and was very interested in influencing the national policy without entering the government.

Finally, we shall also mention player 5: it is the Partido Nacionalista Vasco (PNV), another middle-of-the-road regionalist party that is holding with PSOE a coalition government in the Basque Country since 1986. The reason to include it is that this party seems to be very important from the cooperation index point of view; it fails, however, to escape from its dummy position when we modify the game.

We shall define a cooperation index that takes into account these political characteristics of the parties. Three reasonable assumptions will make our task easier:

• 1. Coalitions $S$ of more than 3 parties are highly improbable, and will then be assigned $p(S) = 0$.

• 2. We need to specify $p(S)$ for winning coalitions only (recall the definition of the modified game $v/p$).

• 3. Once $p(S)$ is given for every coalition $S$ such that $\vert S \vert = 2$, we assume that, for every $T$ with $\vert T \vert = 3$,

  $$ p(T) = \min \{p(S) : S \subseteq T, \vert S \vert = 2\}. $$

These prerequisites and our own opinion about the relationships between parties give rise to a cooperation index that we describe as follows:

$$\begin{array}{ccc}p(\{1,2\}) = 0,& p(\{2,4\}) = 0.4,& p(\{1,3,4\}) = 0.2, \\p(\{1,3\}) = 0.3,& p(\{2,5\}) = 0.5,& p(\{1,3,5\}) = 0.2, \\p(\{1,4\}) = 0.9,& p(\{3,4\}) = 0.2,& p(\{1,4,5\}) = 0.9, \\p(\{1,5\}) = 1.0,& p(\{3,5\}) = 0.2,& p(\{2,3,4\}) = 0.1, \\p(\{2,3\}) = 0.1,& p(\{4,5\}) = 1.0, \end{array}$$

and $p(S) = 0$ otherwise if $\vert S \vert > 1$. The modified game is therefore

$$ v/p = 0.3\, u_{\{1,3\}} + 0.9\, u_{\{1,4\}} - 0.3\, u_{\{1,3,4\}} + 0.1\, u_{\{2,3,4\}} - 0.1\, u_{\{1,2,3,4\}}.$$

Notice that, in spite of its very good degree of affinity with two basic parties (PSOE and CiU), PNV is still a null player after modifying the game; thus it will be left aside definitively in our study of the coalition bargaining. Also notice that $(v/p)(N) = 0.9$, and therefore no coalition will share more than this amount among their members. We have already given an interpretation of this inefficiency elsewhere in this chapter. By looking at $v$-winning coalitions with no more than 3 players, the generalized coalition value gives the results contained in Table 2.

Table 2 Generalized coalition values in Example 4.2

A comparison of the Shapley value for games $v$ and $v/p$ (first row of Table 2) tells us that PP and IU lose power, PSOE remains more or less equally, and CiU gets a much better position. There are three stable coalitions: the first one is $\{1,4\}$, whose players, PSOE and CiU, share all the available power; the second is $\{1,3\}$, formed by PSOE and IU, but they control only a power of 0.6 and leave therefore 0.3 to CiU; the third stable coalition is $\{2,3,4\}$ and, again, its members, PP, IU, and CiU, obtain only 0.5 in all, thus leaving an important fraction of power in PSOE’s hands. Finally, note that PSOE holds its optimal value also in oversized coalitions ($\{1,2,3\}$ and $\{1,2,4\}$), but they are not stable.

One can then conclude that any observer of the Spanish political life should agree with this mathematical description of the strategic and ideological tensions at the Congreso during the last Legislature. In particular, our result would be found satisfactory because, indeed, a parliamentary coalition between PSOE and CiU has been supporting a minority government of the socialist party. Furthermore, the sharing of power among these two parties, given by the fourth row of Table 2, corresponds very closely to a generalized opinion that PSOE’s cabinet has been dominated by the conditional support of CiU, which has very often imposed its criteria on economic and regional (autonomic) policies.