1 Introduction
In this paper we analyze a class of transferable utility games, called three-valued simple games. The class of three-valued simple games is a natural extension of the class of simple games, introduced by Von Neumann and Morgenstern (1944) and widely applied in the literature to model decision rules in legislatures and other decision-making bodies. In a simple game, a coalition is either ‘winning’ or ‘losing’, i.e., there are two possible values for each coalition. The concept of three-valued simple games goes one step further than simple games in the sense that there are three, instead of only two, possible values.
Simple games often represent simple voting games in which the way of determining which coalitions are winning is structured in the sense that each voter has two options: voting ‘yes’ or voting ‘no’. Felsenthal and Machover (1997) generalized simple voting games by introducing ternary voting games, which recognizes abstention as an option next to the ‘yes’ and ‘no’ votes. Ternary voting games are extended by introducing (j, k) simple voting games (see Freixas and Zwicker 2003) with several levels of approval in the input (j levels) and the output (k levels). Note that simple voting games correspond to the case \((j,k)=(2,2)\) and ternary voting games to \((j,k)=(3,2)\). Freixas (2005b) generalized the Shapley–Shubik index (cf. Shapley and Shubik 1954) for (j, k) simple voting games and provided a characterization for the class of (j, 2) simple voting games. Other indices for (classes of) (j, k) simple voting games are studied in Freixas (2005a) and Freixas (2012). Gibbard (1973) analyzed voting in a more general setting than (j, k) simple voting but mainly focussed on the possible manipulation of voting schemes. Finally, we mention Hsiao and Raghavan (1993) who in the general framework of multi-choice cooperative games are the first to analyze input or effort levels on the part of the players in joining cooperating coalitions.
Anzeige
Note that there is a major conceptual difference between (j, k) simple voting games and three-valued simple games. Although, of course, every three-valued simple game can be considered as a (2, 3) simple voting game, the definition of a three-valued simple game (and in fact of a simple game too) does not require a specification of the exact structure of how the values of the various coalitions are obtained. In (j, k) simple voting games such a specification is provided in the definition. We will illustrate this conceptual difference in a more concrete example later on, namely Example 3.3.
This paper formally defines the class of three-valued simple games and focuses on analyzing the core and the Shapley value of these games. We study how the results for simple games can be extended to three-valued simple games. We extend the notion of veto players in simple games, to the notion of vital players, primary vital players and secondary vital pairs in three-valued simple games. It is known that in simple games the core is fully determined by the veto players. In a similar way, we introduce the vital core which fully depends on (primary and secondary) vital players. The vital core is shown to be a subset of the core. We discuss two classes of three-valued simple games such that the core and the vital core coincide.
Dubey (1975) characterized the Shapley value on the class of simple games. The essence of this characterization is the transfer property. We will show that the transfer property can also be used for a characterization of the Shapley value for three-valued simple games. In order to obtain this characterization we introduce a new axiom, called unanimity level efficiency. We prove that the combination of the axioms of efficiency, symmetry, the dummy property, the transfer property and unanimity level efficiency fully determines the Shapley value for a three-valued simple game. Moreover, also the logical independence of these five axioms is shown. At last, as an illustration, a parliamentary bicameral system is modelled as a three-valued simple game and analyzed on the basis of the Shapley value.
The organization of this paper is as follows. Section 2 formally introduces three-valued simple games. In Sect. 3 the core of three-valued simple games is investigated. Section 4 provides a characterization for the Shapley value on the class of three-valued simple games.
Anzeige
2 Simple and three-valued simple games
In this section we recall the formal definition of simple games and define three-valued simple games.
With N a non-empty finite set of players, a transferable utility (TU) game is a function \(v: 2^N \rightarrow {\mathbb {R}}\) which assigns a number to each coalition \(S \in 2^N\), where \(2^N\) denotes the collection of all subsets of N. By convention, \(v(\emptyset )=0\). Let \(\text {TU}^N\) denote the class of all TU-games with player set N.
A game \(v \in \text {TU}^N\) is called simple ifA coalition is winning if \(v(S) = 1\) and losing if \(v(S) = 0\). Let \(\text {SI}^N\) denote the class of all simple games with player set N.
(i)
\(v(S) \in \{0,1\}\) for all \(S \subset N\),
(ii)
\(v(N)=1\),
(iii)
\(v(S) \le v(T)\) for all \(S, T \in 2^N\) with \(S \subset T\) (monotonicity).
In this paper we investigate a new subclass of TU-games, the class of three-valued simple games. A game \(v \in \text {TU}^N\) is called three-valued simple ifLet \(\text {TSI}^N\) denote the class of all three-valued simple games with player set N. The concept of three-valued simple games goes one step further than simple games in the sense that there are three, instead of only two, possible values. Next to the value 0, we have chosen the values 1 and 2. Of course, the relative proportion between these two values may depend on the application at hand and the concept of three-valued simple games (and its results) can be generalized to three-valued TU-games with coalitional values 0, 1 or \(\beta \) with \(\beta >1\).
(i)
\(v(S) \in \{0,1,2\}\) for all \(S \subset N\),
(ii)
\(v(N)=2\),
(iii)
\(v(S) \le v(T)\) for all \(S, T \in 2^N\) with \(S \subset T\) (monotonicity).
3 The core of three-valued simple games
In this section we investigate the core of three-valued simple games. For this, we extend the concept of veto players in simple games, to the concept of vital players, primary vital players and secondary vital pairs in three-valued simple games.
The core C(v) of a game \(v \in \text {TU}^N\) is defined as the set of all allocations \(x \in {\mathbb {R}}^N\) such that \(\sum _{i \in N}{x_i}=v(N)\) (efficiency) and \(\sum _{i \in S}{x_i} \ge v(S)\) for all \(S \subset N\) (stability). Hence, the core consists of all possible allocations of v(N) for which no coalition has the incentive to leave the grand coalition. Consequently, if the core is empty, then it is not possible to find a stable allocation of v(N).
Recall that for a simple game \(v \in \text {SI}^N\) the set of veto players are those players who belong to every coalition with value 1, i.e.,In addition, the core of \(v \in \text {SI}^N\) is fully determined by its set of veto players, namelywhere for \(S \in 2^N {\backslash } \{\emptyset \}\), the characteristic vector \(e^S \in {\mathbb {R}}^N\) is defined asfor all \(i \in N\).
$$\begin{aligned} \text {veto}(v)= \bigcap \{S~|~v(S)=1\}. \end{aligned}$$
$$\begin{aligned} C(v)=\text {Conv}(\{e^{\{i\}}~|~i \in \text {veto}(v)\}), \end{aligned}$$
$$\begin{aligned} e_i^S = {\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } \; i \in S, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
We characterize the core of a three-valued simple game using the concept of vital players which is similar to the concept of veto players in simple games. Proposition 3.1 below states that only the vital players of a three-valued simple game can receive a positive payoff in the core, while all other players receive zero. Here, for \(v \in \text {TSI}^N\) the set of vital players is defined byHence, the vital players are those players who belong to every coalition with value 2.
$$\begin{aligned} \text {Vit}(v)=\bigcap \left\{ S~|~v(S)=2\right\} . \end{aligned}$$
Proposition 3.1
Let \(v \in \mathrm{TSI}^N\). If \(x \in C(v)\) and \(i \in N {\backslash }\mathrm{Vit}(v)\), then \(x_i=0\).
Proof
Let \(x \in C(v)\) and \(i \in N{\backslash }\text {Vit}(v)\). Since \(i \not \in \text {Vit}(v)\), there exists a \(T \subseteq N {\backslash } \{i\}\) with \(v(T)=2\). Clearly, since \(x \in C(v)\), we have \(x \ge 0\). Then, because of efficiency and stability of \(x \in C(v)\),so \(x_i=0\). \(\square \)
$$\begin{aligned} x_i \le v(N) - \sum _{j \in T}{x_j} \le v(N) - v(T) = 0, \end{aligned}$$
Using the concept of vital players, Proposition 3.2 provides a sufficient condition for emptiness of the core of a three-valued simple game.
Proposition 3.2
Let \(v \in \mathrm{TSI}^N\). If \(\mathrm{Vit}(v)=\emptyset \) or \(v(N {\backslash } \mathrm{Vit}(v))>0\), then \(C(v)=\emptyset \).1
Proof
First, assume \(\text {Vit}(v)=\emptyset \). Suppose \(C(v) \ne \emptyset \) and let \(x \in C(v)\). Then, from Proposition 3.1 we know \(x_i=0\) for all \(i \in N\). Consequently, \(\sum _{i \in N}{x_i}=0\) which contradicts the efficiency condition of \(x \in C(v)\).
Second, assume \(v(N {\backslash } \text {Vit}(v))>0\). Suppose \(C(v) \ne \emptyset \) and let \(x \in C(v)\). Then, from Proposition 3.1 we know \(x_i=0\) for all \(i \in N {\backslash } \text {Vit}(v)\) and therefore \(\sum _{i \in N {\backslash } \text {Vit}(v)}{x_i}=0<v(N {\backslash } \text {Vit}(v))\), which contradicts the stability condition of \(x \in C(v)\). \(\square \)
From Proposition 3.2 it follows that only the set of permissible three-valued simple games may have a non-empty core, where a game \(v \in \text {TSI}^N\) is called permissible if the following two conditions are satisfied:As a consequence, from now on we focus only on the set of permissible three-valued simple games and define for every permissible three-valued simple game, a reduced game where the player set is reduced to the set of vital players. We define this reduced game in such a way that the core of a permissible three-valued simple game equals the core of the reduced game, when extended with zeros for all players outside the set of vital players (see Proposition 3.4).
(i)
\(\text {Vit}(v) \ne \emptyset \),
(ii)
\(v(N {\backslash } \text {Vit}(v))=0\).
For a permissible game \(v \in \text {TSI}^N\) the reduced three-valued simple game \(v_r \in \text {TU}^{\text {Vit}(v)}\) is defined byfor all \(S \subseteq \text {Vit}(v)\). The following proposition states that a reduced permissible game \(v_r\) is also a three-valued simple game and, interestingly, allows for only one coalition with value 2.
$$\begin{aligned} v_r(S) = v(S \cup (N {\backslash } \text {Vit}(v))), \end{aligned}$$
Proposition 3.3
Let \(v \in \mathrm{TSI}^N\) be permissible. Then, \(v_r \in \mathrm{TSI}^{\mathrm{Vit}(v)}\) withfor all \(S \subset \mathrm{Vit}(v)\).
$$\begin{aligned} v_r(S) \in \{0,1\}, \end{aligned}$$
Proof
From the definition of \(v_r\) it immediately follows that \(v_r \in \mathrm{TSI}^{\text {Vit}(v)}\). Suppose that there exists an \(S \subset \text {Vit}(v)\) with \(v_r(S)=2\). Then \(v(S \cup (N {\backslash } \text {Vit}(v)))=2\) and consequently, using the definition of \(\text {Vit}(v)\), we have \(\text {Vit}(v) \subseteq S\), which is a contradiction. \(\square \)
In a reduced three-valued simple game the number of coalitions with value 2 is reduced to one, only the grand coalition has value 2, and thus \(\text {Vit}(v_r)=\text {Vit}(v)\). This property makes it easier to characterize the core of reduced three-valued simple games compared to non-reduced three-valued simple games.
For a permissible game \(v \in \text {TSI}^N\) and for an \(x \in {\mathbb {R}}^{\text {Vit}(v)}\) we define \(\overline{x}^0 \in {\mathbb {R}}^N\) asFor a set \(X \subseteq {\mathbb {R}}^{\text {Vit}(v)}\), we define \(\overline{X}^0 \subseteq {\mathbb {R}}^N\) as \(\overline{X}^0= \{\overline{x}^0~|~x \in X\}\).
$$\begin{aligned} \overline{x}^0_i = {\left\{ \begin{array}{ll} x_i &{} \quad \text{ if } \; i \in \text {Vit}(v), \\ 0 &{} \quad \text{ if } \; i \in N {\backslash } \text {Vit}(v). \end{array}\right. } \end{aligned}$$
Proposition 3.4
Let \(v \in \text {TSI}^N\) be permissible. Then,
$$\begin{aligned} C(v)=\overline{C(v_r)}^0 \end{aligned}$$
Proof
(“\(\subseteq \)”) Let \(x \in C(v)\) and let \(S \subseteq \text {Vit}(v)\). From Proposition 3.1 we havewhere the inequality follows from stability of \(x \in C(v)\). Because of efficiency of \(x \in C(v)\) and due to Proposition 3.1 we havewhere the last equality follows from Proposition 3.3. Hence, \(x \in \overline{C(v_r)}^0\).
$$\begin{aligned} \sum _{i \in S}{x_i} = \sum _{i \in S \cup (N {\backslash } \text {Vit}(v))}{x_i} \ge v(S \cup (N {\backslash } \text {Vit}(v)))=v_r(S), \end{aligned}$$
$$\begin{aligned} \sum _{i \in \text {Vit}(v)}{x_i}= \sum _{i \in N}{x_i}=v(N)=2=v_r(\text {Vit}(v)), \end{aligned}$$
(“\(\supseteq \)”) Let \(x \in \overline{C(v_r)}^0\) and let \(S \subseteq N\). Then,where the first inequality follows from stability of \(x \in C(v_r)\) and the second inequality follows from monotonicity of v and the fact that \(S \subseteq (S \cap \text {Vit}(v)) \cup (N {\backslash } \text {Vit}(v))\). Because of efficiency of \(x \in C(v_r)\) we havewhere the penultimate equality follows from Proposition 3.3. Hence, \(x \in C(v)\). \(\square \)
$$\begin{aligned} \sum _{i \in S}{x_i} = \sum _{i \in S \cap \text {Vit}(v)}{x_i} \ge v_r(S \cap \text {Vit}(v)) = v((S \cap \text {Vit}(v)) \cup (N {\backslash } \text {Vit}(v))) \ge v(S), \end{aligned}$$
$$\begin{aligned} \sum _{i \in N}{x_i} = \sum _{i \in \text {Vit}(v)}{x_i}= v_r(\text {Vit}(v)) = 2 = v(N), \end{aligned}$$
Proposition 3.4 states that the core of a permissible three-valued simple game follows from the core of the corresponding reduced game by extending the vectors with zeros for the non-vital players. This proposition is illustrated in the following example.
Example 3.1
Let \(N=\{1,2,3,4\}\) and consider the game \(v \in \text {TSI}^N\) given byNote that v is permissible since \(\text {Vit}(v)=\{1,2,3\} \ne \emptyset \) and \(v(N {\backslash } \text {Vit}(v))=v(\{4\})=0\). The corresponding reduced three-valued simple game \(v_r\) is given in Table 1.
$$\begin{aligned} v(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S \in \{\{1,2,3\},N\}, \\ 1 &{} \quad \text{ if } \; S \in \{\{1,2\},\{2,3\},\{1,2,4\},\{2,3,4\}\}, \\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$
Table 1
S
|
\(\{1\}\)
|
\(\{2\}\)
|
\(\{3\}\)
|
\(\{1,2\}\)
|
\(\{1,3\}\)
|
\(\{2,3\}\)
|
\(\{1,2,3\}\)
|
|---|---|---|---|---|---|---|---|
\(v_r(S)\)
| 0 | 0 | 0 | 1 | 0 | 1 | 2 |
Sincewe have, according to Proposition 3.4, that
\(\square \)
$$\begin{aligned} C(v_r)= \text {Conv} \left( \begin{pmatrix} 0 \\ 2 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \right) , \end{aligned}$$
$$\begin{aligned} C(v)= \text {Conv} \left( \begin{pmatrix} 0 \\ 2 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \right) . \end{aligned}$$
As Example 3.1 suggests, the extreme points of the core of three-valued simple games have a specific structure which we will describe using the notion of the vital core. The extreme points depend in particular on the set of vital players that belong to every coalition with value 1 or 2 in \(v_r\) and the set of pairs of vital players such that for every coalition with value 1 in \(v_r\) at least one player of such a pair belongs to the coalition. For a permissible three-valued simple game \(v \in \text {TSI}^N\) we define the set of primary vital players of v byand define the set of secondary vital pairs of v byUsing the primary vital players and the secondary vital pairs, the vital core VC(v) of a permissible game \(v \in \text {TSI}^N\) is defined byThe vital core2 is a subset of the core as is seen in the following theorem.
$$\begin{aligned} \text {PVit}(v)= \bigcap \left\{ S \subseteq \text {Vit}(v)~|~v_r(S) \in \{1,2\} \right\} , \end{aligned}$$
$$\begin{aligned} \text {SVit}(v)= \{\{i,j\} \subseteq \text {Vit}(v) {\backslash } \text {PVit}(v)~|~i \ne j, \{i,j\} \cap S \ne \emptyset \quad \text { for all } \; S \quad \text { with } \; v_r(S)=1\}. \end{aligned}$$
$$\begin{aligned} VC(v)= & {} \text {Conv}(\{2e^{\{i\}}~|~i \in \text {PVit}(v)\} \\&\cup \{e^{\{i,j\}}~|~i \in \text {PVit}(v), j \in \text {Vit}(v) {\backslash } \text {PVit}(v)\} \\&\cup \{e^{\{i,j\}}~|~\{i,j\} \in \text {SVit}(v)\}). \end{aligned}$$
Theorem 3.5
Let \(v \in \text {TSI}^N\) be permissible. Then,3
$$\begin{aligned} VC(v) \subseteq C(v). \end{aligned}$$
Proof
Due to Proposition 3.4 together with the fact that C(v) is a convex set, it is sufficient to show that \(2e^{\{i\}} \in C(v_r)\) for all \(i \in \text {PVit}(v)\), \(e^{\{i,j\}} \in C(v_r)\) for all \(i \in \text {PVit}(v)\) and \(j \in \text {Vit}(v) {\backslash } \text {PVit}(v)\), and \(e^{\{i,j\}} \in C(v_r)\) for all \(\{i,j\} \in \text {SVit}(v)\).4
Let \(i \in \text {PVit}(v)\) and \(S \subset \text {Vit}(v)\). If \(i \in S\), thenIf \(i \not \in S\), then \(v_r(S)=0\) andMoreover, \(\sum _{k \in \text {Vit}(v)}{2e_k^{\{i\}}}=2=v_r(\text {Vit}(v))\). Hence, \(2e^{\{i\}}\) belongs to \(C(v_r)\).
$$\begin{aligned} \sum _{k \in S}{2e_k^{\{i\}}}=2 > 1\ge v_r(S). \end{aligned}$$
$$\begin{aligned} \sum _{k \in S}{2e_k^{\{i\}}}=0=v_r(S). \end{aligned}$$
Next, let \(i \in \text {PVit}(v)\), \(j \in \text {Vit}(v) {\backslash } \text {PVit}(v)\) and \(S \subset \text {Vit}(v)\). If \(i \in S\), thenIf \(i \not \in S\), then \(v_r(S)=0\) andMoreover, \(\sum _{k \in \text {Vit}(v)}{e_k^{\{i,j\}}}=2=v_r(\text {Vit}(v))\). Hence, \(e^{\{i,j\}}\) belongs to \(C(v_r)\).
$$\begin{aligned} \sum _{k \in S}{e_k^{\{i,j\}}} \ge 1 \ge v_r(S). \end{aligned}$$
$$\begin{aligned} \sum _{k \in S}{e_k^{\{i,j\}}} \ge 0 = v_r(S). \end{aligned}$$
Finally, let \(\{i,j\} \in \text {SVit}(v)\) and let \(S \subset \text {Vit}(v)\). If \(S \cap \{i,j\} \ne \emptyset \), thenIf \(S \cap \{i,j\} = \emptyset \), then \(v_r(S)=0\) andMoreover, \(\sum _{k \in \text {Vit}(v)}{e^{\{i,j\}}_k}=2=v_r(\text {Vit}(v))\). Hence, \(e^{\{i,j\}}\) belongs to \(C(v_r)\). \(\square \)
$$\begin{aligned} \sum _{k \in S}{e^{\{i,j\}}_k} \ge 1 \ge v_r(S). \end{aligned}$$
$$\begin{aligned} \sum _{k \in S}{e^{\{i,j\}}_k} =0 = v_r(S). \end{aligned}$$
As the following example shows, the vital core and the core coincide for some three-valued simple games.
Example 3.2
Reconsider the three-valued simple game of Example 3.1. From the reduced game \(v_r\) (see Table 1) it follows thatandTherefore, the vital core of v is given byand, using the results from Example 3.1, we have \(VC(v)=C(v)\). \(\square \)
$$\begin{aligned} \text {PVit}(v)=\{2\} \end{aligned}$$
$$\begin{aligned} \text {SVit}(v)=\left\{ \{1,3\} \right\} . \end{aligned}$$
$$\begin{aligned} VC(v) = \text {Conv} \left( \begin{pmatrix} 0 \\ 2 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \right) , \end{aligned}$$
The result of the previous example is generalized in Theorem 3.6 below which shows that the core and the vital core coincide for the class of convex three-valued simple games. Here a game \(v \in \text {TU}^N\) is called convex iffor all \(S,T \in 2^N, i \in N\) such that \(S \subset T \subseteq N {\backslash } \{i\}\). From Shapley (1971) and Ichiishi (1981) it follows that \(v \in \text {TU}^N\) is convex if and only ifwhere \(\Pi (N)= \{\sigma : N \rightarrow \{1, \ldots , |N|\}~|~\sigma \text { is bijective}\}\) is the set of all orders on N and the marginal vector \(m^{\sigma }(v) \in {\mathbb {R}}^N\), for \(\sigma \in \Pi (N)\), is defined byfor all \(i \in N\).
$$\begin{aligned} v(S \cup \{i\}) - v(S) \le v(T \cup \{i\}) - v(T), \end{aligned}$$
$$\begin{aligned} C(v) = \text {Conv}\left( \{m^{\sigma }(v)~|~\sigma \in \Pi (N) \}\right) , \end{aligned}$$
(1)
$$\begin{aligned} m_i^{\sigma }(v)=v\left( \{j \in N~|~\sigma (j)\le \sigma (i)\}\right) - v\left( \{j \in N~|~\sigma (j) < \sigma (i)\}\right) , \end{aligned}$$
(2)
Theorem 3.6
Proof
From Theorem 3.5 we already know \(VC(v) \subseteq C(v)\), so we only need to prove \(C(v) \subseteq VC(v)\). Together with Proposition 3.4 and the fact \(VC(v)=\overline{VC(v_r)}^0\), it suffices to proveNote that because v is convex and due to the definition of a reduced game, also \(v_r\) is convex. Therefore, because of (1) and because the vital core is a convex set, it suffices to show thatfor all \(\sigma \in \Pi (\text {Vit}(v))\).6
$$\begin{aligned} C(v_r) \subseteq VC(v_r). \end{aligned}$$
$$\begin{aligned} m^{\sigma }(v_r)&\in ~\left\{ 2e^{\{i\}}~|~i \in \text {PVit}(v_r)\right\} \cup \left\{ e^{\{i,j\}}~|~i \in \text {PVit}(v_r), j \in \text {Vit}(v_r) {\backslash } \text {PVit}(v_r)\right\} \\&\cup \left\{ e^{\{i,j\}}~|~\{i,j\} \in \text {SVit}(v_r)\right\} , \end{aligned}$$
Let \(\sigma \in \Pi (\text {Vit}(v))\). Since \(v_r(S) \in \{0,1\}\) for all \(S \subset \text {Vit}(v)\), \(v_r(\text {Vit}(v))=2\) and \(v_r\) is monotonic, \(m^{\sigma }(v_r)\) either contains one two with all other coordinates zero (Case 1) or it contains two ones with all other coordinates zero (Case 2). We thus distinguish between these two cases.
Case 1: [\(m^{\sigma }(v_r)=2e^{\{i\}}\) for some \(i \in \text {Vit}(v)\)]
SetThen, \(v_r(P)=0\) and \(v_r(P \cup \{i\})=2\). Since in a reduced three-valued simple game there is only one coalition, namely the grand coalition \(\text {Vit}(v)\), with value 2, we have \(P \cup \{i\} = \text {Vit}(v)\) and thus \(P= \text {Vit}(v) {\backslash } \{i\}\). Therefore, from monotonicity it follows that \(v_r(S)=0\) for all \(S \subseteq \text {Vit}(v) {\backslash } \{i\}\). Hence, \(i \in S\) for every \(S \subseteq \text {Vit}(v)\) with \(v_r(S) \in \{1,2\}\) and thus \(i \in \text {PVit}(v_r)\). Consequently, we have \(m^{\sigma }(v_r)=2e^{\{i\}}\) with \(i \in \text {PVit}(v_r)\).
$$\begin{aligned} P = \{k \in \text {Vit}(v)~|~\sigma (k) < \sigma (i)\}. \end{aligned}$$
Case 2: [\(m^{\sigma }(v_r)=e^{\{i,j\}}\) for some \(i,j \in \text {Vit}(v)\), \(i \ne j\)]
Without loss of generality assume that \(\sigma (i) < \sigma (j)\). SetThen, \(v_r(P)=0\) and \(v_r(P \cup \{i\})=1\). Since \(v_r(P \cup \{i\})=1\) and \(j \not \in P \cup \{i\}\), we have \(j \not \in \text {PVit}(v_r)\). We distinguish from now on between another two cases: \(i \in \text {PVit}(v_r)\) (Case 2(i)) and \(i \not \in \text {PVit}(v_r)\) (Case 2(ii)).
$$\begin{aligned} P = \{k \in \text {Vit}(v)~|~\sigma (k) < \sigma (i)\}. \end{aligned}$$
Case 2(i): [\(i \in \text {PVit}(v_r)\)]
Then, we have \(m^{\sigma }(v_r)=e^{\{i,j\}}\) with \( i \in \text {PVit}(v_r)\) and \(j \in \text {Vit}(v_r) {\backslash } \text {PVit}(v_r)\).
Case 2(ii): [\(i \not \in \text {PVit}(v_r)\)]
Then, we need to show \(\{i,j\} \in \text {SVit}(v_r)\). Since \(\{i,j\} \subseteq \text {Vit}(v_r) {\backslash } \text {PVit}(v_r)\), it remains to show \(\{i,j\} \cap S \ne \emptyset \) for all \(S \subset \text {Vit}(v)\) with \(v_r(S)=1\). Suppose for the sake of contradiction that there exists a coalition \(S \subset \text {Vit}(v)\) with \(v_r(S)=1\) and \(\{i,j\} \cap S = \emptyset \). Then, due to monotonicity and the fact that \(S \cup P \cup \{i\} \ne \text {Vit}(v)\) because \(j \not \in S\) and \(j \not \in P\), we have \(v_r(S \cup P)=1\) and \(v_r(S \cup P \cup \{i\})=1\). As a consequence,whilewhich is a contradiction with \(v_r\) being convex. Consequently, \(m^{\sigma }(v_r)=e^{\{i,j\}}\) with \(\{i,j\} \in \text {SVit}(v_r)\). \(\square \)
$$\begin{aligned} v_r(S \cup P \cup \{i\})-v_r(S \cup P)=0, \end{aligned}$$
$$\begin{aligned} v_r(P \cup \{i\})-v_r(P)=1, \end{aligned}$$
An example of a class of convex three-valued simple games is the class of double unanimity games. Therefore, Theorem 3.6 implies that the core and the vital core coincide for the class of double unanimity games. For \(T_1, T_2 \in 2^N {\backslash } \{\emptyset \}\), we define the double unanimity game \(u_{T_1, T_2} \in \text {TSI}^N\) byfor all \(S \in 2^N\). Note that a three-value simple double unanimity game is a natural extension of a simple unanimity game \(u_T \in \text {SI}^N\), with \(T\in 2^N {\backslash } \{\emptyset \}\), defined byfor all \(S \in 2^N\).
$$\begin{aligned} u_{T_1,T_2}(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } T_1 \subseteq S \quad \text { and } \quad T_2 \subseteq S, \\ 1 &{} \quad \text{ if } T_1 \subseteq S, T_2 \not \subseteq S \quad \text { or } \; T_1 \not \subseteq S, T_2 \subseteq S, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
$$\begin{aligned} u_T(S) = {\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } \; T \subseteq S, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
The following example illustrates an interactive cooperative operations research situation based on a minimum coloring problem [as introduced by Deng et al. (1999)] that can be modelled as a three-valued simple game. Theorem 3.7 (cf. Musegaas et al. 2016) shows that the core and the vital core coincide for a subclass of minimum coloring games. Note that minimum coloring games are not necessarily convex and thus Theorem 3.7 is not a direct consequence of Theorem 3.6.
Example 3.3
Consider a set of agents \(\{1,2,3,4\}\) who all need access to some facility. However, for some reason, some agents cannot have access to the same facility. The pairs of agents that are in conflict in this way are assumed to be \(\{1,3\}\), \(\{1,4\}\) and \(\{2,4\}\). This situation can be modelled by the conflict graph in Fig. 1. The total costs are assumed to be linearly increasing in the number of facilities used, so the aim is to find the minimum number of facilities that can serve all agents. Clearly, the optimal facility allocation uses two facilities: players 1 and 2 have access to one facility, say facility A, and players 3 and 4 have access to another facility, say facility B.
If we assume that in the initial situation no agents share facilities (and thus four facilities are used), then cooperation in sharing facilities between non-conflicting agents will lead to cost savings. To analyze how to divide the minimal joint costs among the agents a minimum coloring game can be defined. In this minimum coloring game the value of a coalition is equal to the maximal number of facilities a coalition can save by means of sharing facilities. For instance, in our example, the value of the grand coalition will be 2, because initially four facilities were used and by means of optimal cooperation only two facilities are needed. It turns out that the corresponding minimum coloring game \(v \in \text {TU}^N\) is a three-valued simple game and is given byfor all \(S \subseteq N\).
$$\begin{aligned} v(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S=N, \\ 1 &{} \quad \text{ if } \; \{1,2\} \subseteq S \quad \text { or } \; \{2,3\} \subseteq S \quad \text { or } \; \{3,4\} \subseteq S, \quad \text { and } \quad S \ne N, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
Note that it is assumed that all players would want to cooperate and thus in the corresponding three-valued simple game it is analyzed how to divide the maximal joint cost savings due to cooperation among the agents. In order to find a fair allocation of these cost savings, the values of the subcoalitions are taken into account. This illustrates the conceptual difference between three-valued simple games and voting games, where the focus is more on how decision are made instead of taking into account the worth/power of subcoalitions. \(\square \)
Fig. 1
The conflict graph of Example 3.3
×
![]()
Theorem 3.7
Example 3.4 illustrates that there exist three-valued simple games for which the vital core is a strict non-empty subset of the core.
Example 3.4
Let \(v \in \text {TSI}^N\) be given by \(N=\{1, \ldots , 7\}\) andNote that v is permissible since \(\text {Vit}(v)=\{1,2,3,4,5\} \ne \emptyset \) and \(v(N {\backslash } \text {Vit}(v))=v(\{6,7\})=0\). Hence, \(v_r \in \text {TSI}^{\text {Vit}(v)}\) is given byFrom this it follows thatandConsequently,Note that \( \left( 0, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 0, 0 \right) \) belongs to C(v), but does not belong to VC(v) and thus \(VC(v) \subset C(v)\). \(\square \)
$$\begin{aligned} v(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S \in \{N {\backslash } \{6\}, N {\backslash } \{7\},N\}, \\ 1 &{} \quad \text{ if } \; S \not \in \{N {\backslash } \{6\}, N {\backslash } \{7\},N\} \quad \text { and } \quad \{1,3,5\} \subseteq S \quad \text { or } \; \{3,4,5\} \subseteq S \quad \text { or } \\ &{} \quad \, \{1,2,3,6\} \subseteq S \quad \text { or } \; \{1,3,4,7\} \subseteq S \quad \text { or } \; \{2,3,4,6,7\} \subseteq S, \\ 0 &{}\text{ otherwise }. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} v_r(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S= \text {Vit}(v), \\ 1 &{} \quad \text{ if } \; S \in \{\{1,2,3\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{3,4,5\}, \\ &{} \quad \, \{1,2,3,4\},\{1,2,3,5\},\{1,3,4,5\},\{2,3,4,5\}\}, \\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \text {PVit}(v)=\{3\} \end{aligned}$$
$$\begin{aligned} \text {SVit}(v)=\left\{ \{1,4\} \right\} . \end{aligned}$$
$$\begin{aligned} VC(v)=\text {Conv} \left( \begin{pmatrix} 0 \\ 0 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \right) . \end{aligned}$$
4 The Shapley value for three-valued simple games
In this section we analyze the Shapley value for three-valued simple games. In the context of simple games and three-valued simple games, a one-point solution concept like the Shapley value can be interpreted as a measure for the relative influence of each player.
A one-point solution concept f on the class \(\text {G}^N\) with \(\text {G}^N \subseteq \text {TU}^N\) is a function \(f: \text {G}^N \rightarrow {\mathbb {R}}^N\). The Shapley value (Shapley 1953) is a solution concept on \(\text {TU}^N\) defined byfor all \(v \in \text {TU}^N\), where a marginal vector \(m^{\sigma }(v)\) with \(\sigma \in \Pi (N)\) is as defined in (2). A characterization of the Shapley value for simple games is provided by Dubey (1975). The essence of this characterization is the transfer property. A one-point solution concept \(f: \text {G}^N \rightarrow {\mathbb {R}}^N\) on a class \(\text {G}^N \subseteq \text {TU}^N\) such that for all \(v,w \in \text {G}^N\) also \(\max \{v,w\} \in \text {G}^N\) and \(\min \{v,w\} \in \text {G}^N\), satisfies
Dubey (1975) proved that the unique one-point solution concept on \(\text {SI}^N\) that satisfies efficiency, symmetry, the dummy property and the transfer property is the Shapley value (Shapley and Shubik 1954). The aim of this section is to see if the transfer property can also be used for a characterization for three-valued simple games.
$$\begin{aligned} \Phi _i(v) = \frac{1}{|N|!}\sum _{\sigma \in \Pi (N)}{m^{\sigma }(v)}, \end{aligned}$$
-
the transfer property iffor all \(v,w \in \text {G}^N\).8$$\begin{aligned} f(\max \{v,w\})+f(\min \{v,w\})=f(v)+f(w) \end{aligned}$$
First we formulate the properties above to fit on the class \(\text {TSI}^N\). A one-point solution concept \(f: \text {TSI}^N \rightarrow {\mathbb {R}}^N\) satisfiesThe combination of the four properties efficiency, symmetry, dummy property and transfer property9 is not sufficient to characterize the Shapley value on the class of three-valued simple games: see Example A.1 in Appendix A. To obtain a characterization of \(\Phi \) on \(\text {TSI}^N\), we introduce an additional fifth axiom: unanimity level efficiency.
-
efficiency if \(\sum _{i \in N}{f_i(v)}=2\) for all \(v \in \text {TSI}^N\).
-
symmetry if \(f_i(v)=f_j(v)\) for all \(v \in \text {TSI}^N\) and every pair \(i, j \in N\) of symmetric players, where players \(i,j \in N\) are symmetric in v iffor all \(S \subseteq N {\backslash } \{i,j\}\).$$\begin{aligned} v(S \cup \{i\})=v(S \cup \{j\}), \end{aligned}$$
-
the dummy property if \(f_i(v)=v(\{i\})\) for all \(v \in \text {TSI}^N\) and every dummy player \(i \in N\) in v, where player \(i \in N\) is a dummy player in v iffor all \(S \subseteq N {\backslash } \{i\}\).$$\begin{aligned} v(S \cup \{i\})=v(S)+v(\{i\}), \end{aligned}$$
A one-point solution concept \(f: \text {TSI}^N \rightarrow {\mathbb {R}}^N\) satisfiesUnanimity level efficiency intuitively states that in a double unanimity game \(u_{S,T}\) with \(S \subset T\) the players in S can allocate a payoff of 1 between themselves, while for the remaining payoff of 1 (assuming efficiency) the players in S and \(T {\backslash } S\) are treated equally. Formally, the unanimity level efficiency axiom compares the aggregate payoff of coalition S within a double unanimity game \(u_{S,T}\), with \(S \subset T\), to half of the payoffs to S in the double unanimity game \(u_{T,T}\). Note that the double unanimity game \(u_{T,T}\) is a rescaling of the unanimity game \(u_T\) and half of the payoffs to S in the double unanimity game \(u_{T,T}\) equals the payoffs to S in the unanimity game \(u_T\).
-
unanimity level efficiency iffor all \(S, T \in 2^N {\backslash } \{\emptyset \}\) with \(S \subset T\).$$\begin{aligned} \sum _{i \in S}{f_i(u_{S,T})} =1 + \frac{1}{2}\sum _{i \in S}{f_i(u_{T,T})}, \end{aligned}$$(3)
The combination of the axioms of efficiency, symmetry, the dummy property, the transfer property and unanimity level efficiency fully determines the Shapley value for a three-valued simple game.
Theorem 4.1
Proof
12 We first prove that, on \(\text {TSI}^N\), the Shapley value \(\Phi \) satisfies the five axioms mentioned in the theorem. From Shapley (1953) it follows that \(\Phi \) satisfies efficiency, symmetry and the dummy property on \(\text {TU}^N\). Moreover, from Dubey (1975) it follows that \(\Phi \) satisfies the transfer property on \(\text {TU}^N\). Hence, \(\Phi \) also satisfies efficiency, symmetry, the dummy property and the transfer property on \(\text {TSI}^N\), and thus it only remains to prove that \(\Phi \) satisfies unanimity level efficiency on \(\text {TSI}^N\). Note that, for \(S,T \in 2^N\) with \(S \subset T\), we haveandfor all \(i \in N\). Consequently,To finish the proof, we show that the five axioms exactly fix the allocation vector prescribed by the solution concept for every three-valued simple game. Let \(f: \text {TSI}^N \rightarrow {\mathbb {R}}^N \) be a one-point solution concept that satisfies efficiency, symmetry, the dummy property, the transfer property and unanimity level efficiency on \(\text {TSI}^N\). Let \(v \in \text {TSI}^N\) and defineand setObserve the following:Now let \(v \in \text {TSI}^N\) such that \(|\text {MWC}(v)|=m\) with \(m \ge 2\). We use induction to show that f(v) is uniquely determined. Assume that f(w) is uniquely determined for all \(w \in \text {TSI}^N\) with \(|\text {MWC}(w)|<m\). Set \(\text {MWC}_1(v)=\{S_1, S_2, \ldots , S_p\}\) and \(\text {MWC}_2(v)=\{T_1, T_2, \ldots , T_q\}\) with \(p+q=m\). Note that from monotonicity of v it follows thatfor all \(i \in \{1, \ldots , p\}\) and \(j \in \{1, \ldots , q\}\). We distinguish between two cases: \(q=0\) and \(q>0\).
$$\begin{aligned} \Phi _i(u_{S,T})= {\left\{ \begin{array}{ll} \frac{1}{|S|}+\frac{1}{|T|} &{} \quad \text{ if } \; i \in S \\ \frac{1}{|T|} &{} \quad \text{ if } \; i \in T {\backslash } S, \\ 0 &{} \quad \text{ otherwise }, \\ \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \Phi _i(u_{T,T})= {\left\{ \begin{array}{ll} \frac{2}{|T|} &{} \quad \text{ if } \; i \in T \\ 0 &{} \quad \text{ otherwise }, \\ \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \sum _{i \in S}{f_i(u_{S,T})}- \frac{1}{2}\sum _{i \in S}{f_i(u_{T,T})} = |S| \left( \frac{1}{|S|}+\frac{1}{|T|} \right) - \frac{1}{2}|S| \left( \frac{2}{|T|} \right) =1. \end{aligned}$$
$$\begin{aligned} \text {MWC}_1(v)= & {} \{S \subset N~|~v(S)=1 \; \text { and } \; T \subset S \Rightarrow v(T)=0\}, \\ \text {MWC}_2(v)= & {} \{S \subset N~|~v(S)=2 \; \text { and } \; T \subset S \Rightarrow v(T)\in \{0,1\}\}, \end{aligned}$$
$$\begin{aligned} \text {MWC}(v)=\text {MWC}_1(v) \cup \text {MWC}_2(v). \end{aligned}$$
(i)
If \(|\text {MWC}(v)|=0\), then \(v=u_{N,N}\). From efficiency and symmetry it follows that and thus \(f(u_{N,N})\) is uniquely determined.
$$\begin{aligned} f(u_{N,N})= \frac{2}{|N|}e^N, \end{aligned}$$
(4)
(ii)
If \(|\text {MWC}(v)|=1\), then we have either \(|\text {MWC}_1(v)|=0\) and \(|\text {MWC}_2(v)|=1\), or \(|\text {MWC}_1(v)|=1\) and \(|\text {MWC}_2(v)|=0\). If \(|\text {MWC}_1(v)|=0\) and \(|\text {MWC}_2(v)|=1\), then \(v=u_{T,T}\) for some \(T\subset N\). From efficiency, symmetry, and the dummy property it follows that \(f(u_{T,T})= \frac{2}{|T|}e^T\) and thus \(f(u_{T,T})\) is uniquely determined. On the other hand, if \(|\text {MWC}_1(v)|=1\) and \(|\text {MWC}_2(v)|=0\), then \(v=u_{S,N}\) for some \(S\subset N\). From efficiency and symmetry together with unanimity level efficiency it follows that Then, due to efficiency and symmetry, we know \(f(u_{S,N})= \frac{1}{|S|}e^S+\frac{1}{|N|}e^N\) and thus \(f(u_{S,N})\) is uniquely determined.
$$\begin{aligned} \sum _{i \in S}{f(u_{S,N})}=1+ \frac{1}{2}\sum _{i \in S}{f_i(u_{N,N})} = 1+\frac{|S|}{|N|}. \end{aligned}$$
$$\begin{aligned} T_j \not \subseteq S_i, \end{aligned}$$
Case 1: \(q=0\), i.e., \(|\text {MWC}_2(v)| = 0\) and \(p=m\). DefineThen, \(w, w' \in \text {TSI}^N\) andwhileConsequently, we have \(\text {MWC}_1(w) = \{S_2, S_3, \ldots , S_p\}\) and \(\text {MWC}_2(w) = \emptyset \), and thusMoreover, \(\text {MWC}_1(w') \subseteq \{S_1 \cup S_2, S_1 \cup S_3, \ldots , S_1 \cup S_p\}\) and \(\text {MWC}_2(w') = \emptyset \), and thusSince \(v=\max \{u_{S_1,N}, \ldots , u_{S_p,N}\} = \max \{u_{S_1,N}, w\}\) and by the transfer property, we haveand thusSince by our induction hypothesis the right-hand side is uniquely determined, f(v) is uniquely determined.
$$\begin{aligned} w=\max \{u_{S_2,N}, \ldots , u_{S_p,N}\} \quad \text { and } \quad w' = \min \{u_{S_1,N}, w\}. \end{aligned}$$
$$\begin{aligned} w(S)= {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S = N, \\ 1 &{} \quad \text{ if } \; \text { there exists an } \; i \in \{2, \ldots , p\} \quad \text { such that } \; S_i \subseteq S, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
$$\begin{aligned} w'(S)= {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; S = N, \\ 1 &{} \quad \text{ if } \; \text { there exists an } \; i \in \{2, \ldots , p\} \quad \text { such that } \; S_1 \cup S_i \subseteq S, \\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} |\text {MWC}(w)|=p-1=m-1. \end{aligned}$$
$$\begin{aligned} |\text {MWC}(w')| \le p-1 =m-1. \end{aligned}$$
$$\begin{aligned} f(u_{S_1,N})+f(w)=f(\max \{u_{S_1,N},w\})+f(\min \{u_{S_1,N},w\})=f(v)+f(w'), \end{aligned}$$
$$\begin{aligned} f(v)=f(w)+f(u_{S_1,N})-f(w'). \end{aligned}$$
Case 2: \(q>0\), i.e., \(|\text {MWC}_2(v)| > 0\). DefineThen, \(w, w' \in \text {TSI}^N\) andwhileSince \(T_j \not \subseteq S_i\) for all \(i \in \{1, \ldots , p\}\) and \(j \in \{1, \ldots , q\}\), we have \(\text {MWC}_1(w) = \{S_1, S_2, \ldots , S_p\}\) and \(\text {MWC}_2(w) = \{T_2, T_3, \ldots , T_q\}\), and thusMoreover, \(\text {MWC}_1(w') \subseteq \{T_1 \cup S_1, T_1 \cup S_2, \ldots , T_1 \cup S_p\}\) and \(\text {MWC}_2(w') \subseteq \{T_1 \cup T_2, T_1 \cup T_3, \ldots , T_1 \cup T_q\}\), and thusSince \(v=\max \{u_{S_1,N}, \ldots , u_{S_p,N}, u_{T_1,T_1}, u_{T_2,T_2}, \ldots , u_{T_q,T_q}\} = \max \{u_{T_1,T_1}, w\}\) and by the transfer property, we haveand thusSince by our induction hypothesis the right-hand side is uniquely determined, f(v) is uniquely determined too. \(\square \)
$$\begin{aligned} w=\max \{u_{S_1,N}, \ldots , u_{S_p,N}, u_{T_2,T_2}, \ldots , u_{T_q, T_q}\} \quad \text { and } \quad w' = \min \{u_{T_1,T_1}, w\}. \end{aligned}$$
$$\begin{aligned} w(S)= {\left\{ \begin{array}{ll} 2 &{}\quad \text{ if } \; \text { there exists an } \; i \in \{2, \ldots , q\} \quad \text { such that } \; T_i \subseteq S, \\ 1 &{}\quad \text{ if } \; \text { there exists an } \; i \in \{1, \ldots , p\} \quad \text { such that } \; S_i \subseteq S \\ &{}\quad \text {and } \quad T_j \not \subseteq S \quad \text { for all } \; j \in \{2, \ldots , q\}, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
$$\begin{aligned} w'(S)= {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; \text {there exists an } \; i \in \{2, \ldots , q\} \quad \text { such that } \; T_1 \cup T_i \subseteq S, \\ 1 &{} \quad \text{ if } \; \text {there exists an } \; i \in \{1, \ldots , p\} \quad \text { such that } \; T_1 \cup S_i \subseteq S \\ &{} \quad \text {and } \quad T_j \not \subseteq S \quad \text { for all } \; j \in \{2, \ldots , q\}, \\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} |\text {MWC}(w)|=p+(q-1)=m-1. \end{aligned}$$
$$\begin{aligned} |\text {MWC}(w')| \le p+(q-1)=m-1. \end{aligned}$$
$$\begin{aligned} f(u_{T_1,T_1})+f(w)=f(\max \{u_{T_1,T_1},w\})+f(\min \{u_{T_1, T_1},w\})=f(v)+f(w'), \end{aligned}$$
$$\begin{aligned} f(v)=f(w)+f(u_{T_1,T_1})-f(w'). \end{aligned}$$
Applications of the Shapley value for measuring the power in legislative procedures are abundant in the literature. For instance, Bilbao et al. (2002) considered the legislative procedure of the EU-27 Council by means of a combinatorial method based on generating functions for computing the Shapley value efficiently. Likewise, Hausken and Mohr (2001) considered the legislative procedure in the European Council of Ministers. In particular, they decomposed the Shapley value into a matrix for which the elements in each row and in each column of the matrix sum up to the Shapley value of the corresponding player.
Three-valued simple games can be used to more adequately model a bicameral legislature, in which the legislators are divided into two separate houses, the lower house and the upper house, and a bill has to be approved by both houses. Example 4.1 shows how a three-valued simple game can be used to model the bicameral legislature in the Netherlands.
Example 4.1
In the bicameral legislature of the Netherlands, the States General of the Netherlands, the lower house is called the House of Representatives and the upper house is called the Senate. The House of Representatives consists of 150 members and the Senate consists of 75 members. The members of the Senate and House of Representatives each represent a political party. The members of the House of Representatives are elected directly by the Dutch citizens. The members of the Senate, however, are elected indirectly by the members of the provincial councils, who, in turn, are elected directly by the Dutch citizens.
The House of Representatives can accept or reject a bill. A bill is accepted by the House of Representatives only if there is a majority in favor. When a bill is accepted by the House of Representatives it is forwarded to the Senate. Subsequently the Senate can also accept or reject a bill, again via majority voting. If the bill is also accepted by the Senate, then the bill becomes a law.13 Note that the House of Representatives and the Senate are not symmetric in the sense that the House of Representatives also has the right to propose or to revise a bill, while the Senate does not have this right.
The party breakdown of the House of Representatives and the Senate in September 2016 can be found in Table 2, where \(a_i\) and \(b_i\) denote the number of members in the House of Representatives and Senate, respectively, for party i.
Table 2
Party breakdown of the House of Representatives and the Senate of the Netherlands (updated to September 2016), sources: https://www.houseofrepresentatives.nl/members_of_parliament/parliamentary_parties and https://www.eerstekamer.nl/begrip/english_2
Party |
\(a_i\)
|
\(b_i\)
|
|---|---|---|
VVD | 40 | 13 |
PvdA | 36 | 8 |
SP | 15 | 9 |
CDA | 13 | 12 |
D66 | 12 | 10 |
PVV | 12 | 9 |
CU | 5 | 3 |
GL | 4 | 4 |
SGP | 3 | 2 |
PvdD | 2 | 2 |
GrKO | 2 | 0 |
GrBvK | 2 | 0 |
50PLUS | 1 | 2 |
Houwers | 1 | 0 |
Klein | 1 | 0 |
Van Vliet | 1 | 0 |
OSF | 0 | 1 |
Total | 150 | 75 |
The legislature of the Netherlands can be modelled by means of the following simple game \(w \in \text {SI}^N\) where the set of players N is the set of parties and the value w(S) of a coalition \(S \subseteq N\) equals:Hence, we havefor all \(S \subseteq N\). Note, however, that this game does not take into account the asymmetry of the House of Representatives and the Senate.
-
1, if the members of all parties in the coalition form a majority in both the House of Representatives and Senate,
-
0, otherwise.
$$\begin{aligned} w(S) = {\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } \; \sum _{i \in S}{a_i} \ge 76 \quad \text { and } \quad \sum _{i \in S}{b_i}\ge 38, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
Alternatively, a three-valued simple game does offer the opportunity to model the asymmetric bicameral legislature of the Netherlands into a single TU-game. Consider the three-valued simple game \(v \in \text {TSI}^N\) where the set of players N is again the set of parties. Now, the value v(S) of a coalition \(S \subseteq N\) equals:Hence, we havefor all \(S \subseteq N\). For example, since \(a_{\text {VVD}}+a_{\text {PvdA}}=76 \ge 76\) and \(b_{\text {VVD}}+b_{\text {PvdA}}=21 < 38\), we have \(v(\{\text {VVD}, \text {PvdA}\})=1\). Hence, the parties VVD and PvdA have a majority in the House of Representatives, but not in the Senate.
-
2, if the members of all parties in the coalition form a majority in both the House of Representatives and Senate,
-
1, if the members of all parties in the coalition form a majority in the House of Representatives but not in the Senate,
-
0, otherwise.
$$\begin{aligned} v(S) = {\left\{ \begin{array}{ll} 2 &{} \quad \text{ if } \; \sum _{i \in S}{a_i} \ge 76 \quad \text { and } \quad \sum _{i \in S}{b_i}\ge 38, \\ 1 &{} \quad \text{ if } \; \sum _{i \in S}{a_i}\ge 76 \quad \text { and } \quad \sum _{i \in S}{b_i} < 38, \\ 0 &{} \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$
Table 3 provides the rankings according to the Shapley values of the resulting simple and three-valued simple game. Note that generally speaking there are no major differences in the resulting rankings. So, in this case, the basic modelling via a simple game can be seen as a good approximation. \(\square \)
Table 3
The rankings of the parties in the bicameral legislature of the Netherlands based on \(\Phi (w)\) and \(\Phi (v)\), respectively
Ranking | Party | Ranking | Party |
|---|---|---|---|
(a) Ranking according to \(\Phi (w)\)
| (b) Ranking according to \(\Phi (v)\)
| ||
1. | VVD | 1. | VVD |
2. | PvdA | 2. | PvdA |
3. | CDA | 3. | SP |
4. | SP | 4. | CDA |
5. | D66 | 5. | D66 |
6. | PVV | 6. | PVV |
7. | GL | 7. | CU |
8. | CU | 8. | GL |
9. | SGP | 9. | SGP |
10. | PvdD | 10. | PvdD |
11. | 50PLUS | 11. | 50PLUS |
12. | GrKO | 12. | GrKO |
12. | GrBvK | 12. | GrBvK |
14. | OSF | 14. | Houwers |
15. | Houwers | 14. | Klein |
15. | Klein | 14. | Van Vliet |
15. | Van Vliet | 16. | OSF |
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.