Core stability of the Shapley value for cooperative games

Abstract

Our objective is to analyze the relationship between the Shapley value and the core of cooperative games with transferable utility. We first characterize balanced games, i.e., the set of games with a nonempty core, through geometric properties. We show that the set of balanced games generates a polyhedral cone and that a game is balanced if and only if it is a nonnegative linear combination of some simple games. Moreover, we show that the set of games whose Shapley value lies in the core also yields a polyhedral cone and that a game obeys this property if and only if it is a nonnegative linear combination of simple games satisfying certain properties. By-products, we also show that the number of games that correspond to the extreme rays of the polyhedron coincides with the number of minimal balanced collections.

1 Introduction

One of the objectives of cooperative game theory is to explore a “desirable” solution: How to allocate the surplus that players obtain from their cooperation. The Shapley value (Shapley 1953b) and the core should be the most well-known solution concepts. The Shapley value is a single-valued solution, which assigns a payoff to each player based on his/her contributions to a coalition. Since the seminal study of Shapley (1953b), many studies have been devoted to analyzing the properties of the Shapley value.¹ The Shapley value has not only normative properties but also a variety of applications and strategic foundations.² In contrast, the core is a set-valued solution, which is a set of payoff allocations from which no groups of players have an incentive to deviate. Its axiomatic properties and strategic foundations have also been intensively studied.³ The concept of the core is, because of its simplicity and generality, used in a wide range of fields including microeconomics, bargaining theory, and matching theory.

If the Shapley value lies in the core, it can be seen as a stable allocation that is robust against any coalitional deviations. In this sense, the Shapley value should be an attractive core selection. However, in general, the Shapley value may be outside the core. Hence, it is important to identify the condition that guarantees the Shapley value lies in the core. One of the most eminent conditions is convexity, introduced by Shapley (1971). He shows that if a game is convex, the Shapley value lies in the core. Inarra and Usategui (1993) and Izawa and Takahashi (1998) propose a weaker condition called average convexity and show that it is also a sufficient condition.⁴ In addition to the sufficient conditions above, they provide some necessary and sufficient conditions. Although these necessary and sufficient conditions are important steps toward understanding the Shapley value and the core, because of their complexity, it is not straightforward to derive applicable insights from the conditions.⁵ Therefore, in this paper, we attempt to provide a new necessary and sufficient condition for the Shapley value to be in the core.

To this end, we first consider a geometric property of the set of balanced games, namely, the set of games with a nonempty core.⁶ Bondareva (1963) and Shapley (1967) show that a game is balanced if and only if a weighted sum of the worth of every coalition is less than that of the grand coalition. These weights are called balanced vectors, and it can be shown that the set of balanced vectors is convex. Based on this result, we show that the set of balanced games yields a polar cone of a polyhedral cone that is generated from extended balanced vectors. Moreover, we obtain the explicit representation of the generating matrix for the polyhedral cone. Then, by applying Minkowski-Weyl’s theorem, which is often used in the theory of convex polyhedra, we obtain the explicit characterization of the extreme rays of the set of balanced games. As a result, we also show that a game is balanced if and only if the game has a nonnegative linear combination of the games, each of which corresponds to the extreme rays: singleton unanimity games, negative singleton unanimity games, and negative standard basis games with strict subsets of the grand coalition. This result is a generalization of the decomposition result of Abe (2019), which describes the relationship between the nonemptiness of the core and the class of zero-normalized nonnegative games.

Building on the decomposition result of the balanced games, we characterize the set of games whose Shapley value is an element of the core. We show that the set of such games also generates a certain polyhedral cone. To obtain the extreme rays of the set, we adopt the following two steps. First, we decompose an arbitrary game into the sum of two classes of games: singleton unanimity games and the games whose Shapley value is a zero vector. As elaborated below, the Shapley value (of the original game) lies in the core if and only if the core of the latter class of games contains the zero vector as its element. Considering that the latter class of games can be decomposed into a nonnegative linear combination of negative standard basis games with strict subsets of the grand coalition, we identify the condition by which the Shapley value of the latter class of games coincides with the zero vector. Second, we show that the games that correspond to the extreme rays of the set of extended balanced vectors constitute the extreme rays of the set of the latter class of games. Combining these two steps, we conclude that the Shapley value of a game belongs to the core if and only if it is decomposed into a nonnegative linear combination of some “easy” games. Moreover, by-products, we also show that the number of the above-mentioned extreme rays coincides with the number of minimal balanced collections.

The remainder of this paper is organized as follows. Section 2 provides basic definitions. In Sect. 3, we introduce key results for the polyhedral cone and provide a characterization result of balanced games. Based on the results discussed in Sect. 3, we provide our main result in Sect. 4. In Sect. 5, we provide some discussions. In particular, in Subsection 5.3, we attempt to replace the Shapley value in our conditions with an arbitrary linear solution. Section 6 summarizes the results.

2 Preliminaries

Let $N=\{1,\ldots ,n\}$ be the set of players and a function $v: 2^n \rightarrow {\mathbb {R}}$ with $v(\emptyset )=0$ denote a characteristic function. A coalition of players is a nonempty subset of the player set $S\subseteq N$. We denote the cardinality of coalition S by |S|. We use n to denote |N|. A cooperative game with transferable utility (a TU-game) is a pair (N, v). We fix the player set N throughout this paper and typically use v instead of (N, v) to denote a game. Let ${\mathcal {G}}_N$ be the set of all TU-games with the player set N. We now define a negative standard basis game as follows: For every nonempty $S \subseteq N$,

$$\begin{aligned} u^-_S(T)={\left\{ \begin{array}{ll} -1~~\text {if}~~T=S,\\ 0~~\text {otherwise}. \end{array}\right. } \end{aligned}$$

Similarly, for each nonempty $T \subseteq N$, a unanimity game $u_T \in {\mathcal {G}}_N$ is defined as

$$\begin{aligned} u_T(S)= \left\{ \begin{array}{ll} 1 &\, \mathrm{if}~ T \subseteq S, \\ 0 &\, \mathrm{otherwise}.\\ \end{array} \right. \end{aligned}$$

Shapley (1953a) shows that a game $v \in {\mathcal {G}}_N$ is represented as a unique linear combination of unanimity games: For every game $v\in {\mathcal {G}}_N$, there are unique values $\lambda ^v_T$, $\emptyset \ne T \subseteq N$ such that

$$\begin{aligned} v(S)= \sum _{\emptyset \ne T \subseteq N} \lambda ^v_Tu_T(S)=\sum _{\emptyset \ne R \subseteq S} \lambda ^v_R, \end{aligned}$$

(1)

where $\lambda ^v_T= \sum _{\emptyset \ne R \subseteq T}(-1)^{|T|- |R|}v(R)$. For simplicity, we omit v and write $\lambda _T$ instead of $\lambda ^v_T$ when there is no ambiguity. We use $\lambda$ to denote the vector $(\lambda _T)_{\emptyset \ne T \subseteq N}\in {\mathbb {R}}^{2^n-1}$.

Let $\sigma$ be a permutation of N. For every game v, player i’s marginal contribution in $\sigma$ is $mc_{i,\sigma }(v)=v(\rho ^\sigma _i \cup \{i\})-v(\rho ^\sigma _i)$ where $\rho ^\sigma _i$ is the set of predecessors of player i in $\sigma$. Let $\Pi$ be the set of all permutations. The Shapley value Sh(v) is given as follows: For every $i \in N$,

$$\begin{aligned} Sh_i(v)=\frac{1}{n!}\sum _{\sigma \in \Pi }mc_{i,\sigma }(v). \end{aligned}$$

For every unanimity game, Sh(v) satisfies

$$\begin{aligned} Sh_i(u_T)=\left\{ \begin{array}{ll} 1 / |T| &\, \mathrm{if}~i \in T,\\ 0 &\, \mathrm{otherwise}. \end{array}\right. \end{aligned}$$

Moreover, in view of the linearity of Sh(v) and (1), it follows that

$$\begin{aligned} Sh_i(v) = \sum _{T \subseteq N, i \in T}\lambda _T / |T| \end{aligned}$$

(2)

where $\lambda _T / |T|$ is called Harsanyi’s dividend to the members of T.⁷

The core C(v) is the set of allocations given by

$$\begin{aligned} C(v)=\left\{ x\in {\mathbb {R}}^n \left| \sum _{j\in N}x_j = v(N)\text { and } \sum _{j\in S}x_j \ge v(S) \text { for all} S\subseteq N\right. \right\} . \end{aligned}$$

A game is said to be balanced if it has a non-empty core. Let ${\mathcal {G}}_N^B=\{v \in {\mathcal {G}}_N|C(v) \ne \emptyset \}$ be the set of balanced games. Bondareva (1963) and Shapley (1967) provide the following characterization of balanced games.

Theorem 1

(Bondareva 1963; Shapley 1967) $v \in {\mathcal {G}}_N^B$ if and only if

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N} \gamma _S v(S) \le v(N) \end{aligned}$$

for every $\gamma \in {\mathbb {R}}_{+}^{2^n-2}$ such that

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N, i \in S} \gamma _S=1.\cdots (*) \end{aligned}$$

for every $i \in N$.

The condition in Theorem 1 is called the Bondareva-Shapley condition. A vector $\gamma \in {\mathbb {R}}_{+}^{2^n-2}$ that satisfies the above condition $(*)$ is called a balanced vector, and the set ${\mathcal {B}}(\gamma )=\{S \subsetneq N| \gamma _S>0\}$ is called a balanced collection corresponding to $\gamma$. Note that the set of balanced vectors is convex so that each balanced vector is a convex combination of its extreme points (see, for example, Peleg and Sudhölter 2007). A balanced collection corresponding to an extreme point of the set of balanced vectors is called a minimal balanced collection. Let $K_n$ be the total number of minimal balanced collections of an n-player game.⁸

3 Decomposition of balanced games

In this section, we provide a geometric characterization of the set of balanced games ${\mathcal {G}}_N^B$ and show that each balanced game can be decomposed into some simple games. First, the following observation is useful.

Lemma 1

For every $x \in {\mathbb {R}}^N$ and $v \in {\mathcal {G}}_{N}$, $x \in C(v)$ if and only if

$$\begin{aligned} v=\sum _{i \in N}x_i u_{\{i\}}+\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^- \end{aligned}$$

where $(\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}$.

Proof

By definition, $x \in C(v)$ if and only if

$$\begin{aligned} \sum _{i \in S}x_i\ge v(S), ~\forall ~ S \subsetneq N, \end{aligned}$$

and

$$\begin{aligned} \sum _{i \in N}x_i=v(N). \end{aligned}$$

For any $S \subsetneq N$, let $\alpha ^-_S=\sum _{i \in S}x_i-v(S) \ge 0$. Then, by construction, the above inequalities hold if and only if $v(S) \equiv \sum _{i \in S}x_i-\alpha ^-_S=\sum _{i \in N}x_i u_{\{i\}}(S)+\sum _{\emptyset \ne T \subsetneq N}\alpha ^-_T u_T^-(S)$ for all $S \subsetneq N$ and $v(N)=\sum _{i \in N}x_i=\sum _{i \in N}x_i u_{\{i\}}(N)+\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^-(N)$, which is the desired expression. $\square$

This observation immediately implies the following characterization of balanced games.

Theorem 2

We have $v \in {\mathcal {G}}^B_N$ if and only if it is a sum of a linear combination of singleton unanimity games and a non-negative linear combination of negative standard basis games with $S \subsetneq N$:

$$\begin{aligned} v=\sum _{i \in N}\alpha _i u_{\{i\}}+\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^- \end{aligned}$$

where $(\alpha _i)_{i \in N} \in {\mathbb {R}}^n$ and $(\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}$.

Proof

By Lemma 1, $C(v) \ne \emptyset$ if and only if there is $x \in {\mathbb {R}}^N$ such that

$$\begin{aligned} v=\sum _{i \in N}x_i u_{\{i\}}+\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^- \end{aligned}$$

where $\alpha ^-_S=\sum _{i \in S}x_i-v(S) \ge 0$ for any $S \subsetneq N$. Letting $\alpha _i=x_i$ completes the proof. $\square$

This result can also be interpreted in terms of extreme rays of the set. Each ray coincides with a game as follows.

Corollary 1

The number of the extreme rays of ${\mathcal {G}}_N^B$ is $2^n+2n-2$. Each of them corresponds to a singleton unanimity game, a negative singleton unanimity game, or a negative standard basis game with $S \subsetneq N$.

We can explain why the above result is true in terms of the Bondareva-Shapley condition. Indeed, we show that the above decomposition result and the Bondareva-Shapley condition can be seen as a dual characterization of the balanced games. To see this, we reformulate the Bondareva-Shapley condition as follows.

Proposition 1

We have $v \in {\mathcal {G}}_N^B$ if and only if

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N} \gamma _S v(S)+\gamma _Nv(N) \le 0 \end{aligned}$$

for every $\gamma \in {\mathbb {R}}^{2^n-1}$ such that

$$\begin{aligned} (a)\cdots {\left\{ \begin{array}{ll} \sum \nolimits _{\emptyset \ne S \subseteq N, i \in S} \gamma _S \le 0, \forall i \in N,\\ -\sum \nolimits _{\emptyset \ne S \subseteq N, i \in S} \gamma _S \le 0, \forall i \in N,\\ -\gamma _S \le 0, \forall S \subsetneq N.\\ \end{array}\right. } \end{aligned}$$

Proof

The Bondareva-Shapley condition is equivalent to the following:

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N} \gamma _S v(S)+\gamma _Nv(N) \le 0 \end{aligned}$$

for every $\gamma \in {\mathbb {R}}^{2^n-1}$ such that

$$\begin{aligned} (b)\cdots {\left\{ \begin{array}{ll} \sum \nolimits _{\emptyset \ne S \subsetneq N, i \in S} \gamma _S \le 1, \forall i \in N,\\ -\sum \nolimits _{\emptyset \ne S \subsetneq N, i \in S} \gamma _S \le -1, \forall i \in N,\\ -\gamma _S \le 0, \forall S \subsetneq N,\\ \gamma _N \le -1,\\ -\gamma _N \le 1.\\ \end{array}\right. } \end{aligned}$$

Since $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (b) satisfies (a), the set of vectors satisfying (b) is a subset of the set of vectors satisfying (a). Hence, if $\gamma \cdot v \le 0$ for every $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (a), it also holds for all $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (b).⁹

Now, suppose that $\gamma \cdot v \le 0$ for every $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (b). Take any $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (a). Note that $\gamma _N \le 0$ because $\gamma _S \ge 0$ for all $S \subsetneq N$. If $\gamma _N=0$, then $\gamma ={{\textbf {0}}}$, and $\gamma \cdot v \le 0$ holds. If $\gamma _N<0$, let $\gamma '_S=\frac{\gamma _S}{-\gamma _N}>0$ for all $S \subsetneq N$ and $\gamma '_N=-1$. Then, $\gamma '=(\gamma '_S)_{S \subseteq N}$ satisfies (b). Moreover, by the assumption,

$$\begin{aligned} \sum _{S \subsetneq N}\gamma _Sv(S)+\gamma _Nv(N)=(-\gamma _N)\Bigl (\sum _{S \subsetneq N}(\frac{\gamma _S}{-\gamma _N})v(S)-v(N)\Bigr )=(-\gamma _N)(\gamma ' \cdot v)\le 0. \end{aligned}$$

Hence, if $\gamma \cdot v \le 0$ for every $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (b), it also holds for all $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying (a). $\square$

The set $P=\{x \in {\mathbb {R}}^d| Ax \le {{\textbf {0}}}\}$ for some matrix $A \in {\mathbb {R}}^{m \times d}$ is called a polyhedral cone, and the $P^o=\{y \in {\mathbb {R}}^d| x \cdot y \le 0, \forall x \in P\}$ is called a polar cone of P. Note that the set of vectors $\gamma \in {\mathbb {R}}^{2^n-1}$ satisfying the condition (a) is a polyhedral cone represented as a matrix $R^t \in {\mathbb {R}}^{(2^n+2n-2) \times (2^n-1)}$ such that $P=\{\gamma \in {\mathbb {R}}^{2^n-1}|R^t \gamma \le {{\textbf {0}}}\}$. The set of balanced vectors, which is given as $(*)$ in Theorem 1, is a cross-section of the polyhedral cone with $\gamma _N=-1$. Proposition 1 shows that we can identify the set of balanced games with a polar cone of P by enlarging the set of balanced vectors. The following result plays an important role in finding another representation of a cone.

Theorem 3

(Minkowski-Weyl’s Theorem) For $P \subseteq {\mathbb {R}}^d$, the following two statements are equivalent:

• (1) There exists a matrix $A \in {\mathbb {R}}^{m \times d}$ for some m such that $P=\{x \in {\mathbb {R}}^d| Ax \le {{\textbf {0}}}\}$.

• (2) There exists a matrix $R \in {\mathbb {R}}^{d \times k}$ for some k such that $P=\{x \in {\mathbb {R}}^d| x=R\mu , \mu \ge {{\textbf {0}}}\}$.

A matrix A is called a generating matrix of P. The representation of cone P in the manner of (1) is called its H-representation and that of (2) is called its V-representation.¹⁰ A pair of matrices (A, R) that represents the same cone $P \subseteq {\mathbb {R}}^d$ is called a double description pair (DD-pair). For a DD-pair (A, R), as a corollary of Theorem 3, $(R^t, A^t)$ is also a DD-pair, and the cone $P^o=\{y \in {\mathbb {R}}^d| R^ty \le {{\textbf {0}}}\}=\{y \in {\mathbb {R}}^d| y=A^t\mu , \mu \ge {{\textbf {0}}}\}$ is the polar cone of P.

Applying the above discussion to the set of balanced games, we obtain the result that $v \in {\mathcal {G}}_N^B$ if and only if v is represented as

$$\begin{aligned} v=R\mu , \mu \ge {{\textbf {0}}}. \end{aligned}$$

By this expression, we can see that the column vectors of R correspond to extreme rays of ${\mathcal {G}}_N^B$ and, because of (a), each of them corresponds to a singleton unanimity game, a negative singleton unanimity game, or a negative standard basis game with $S \subsetneq N$. Therefore, we obtain the decomposition result in Theorem 2.

Table 1 shows $R^t$ for $n=3$ where $R^t_i$ is the i-th row vector of $R^t$. This decomposition result is also useful for considering a certain subclass of balanced games. If we consider 0-normalized games,¹¹ then $R^t_4, R^t_5, R^t_6, R^t_7, R^t_8$ and $R^t_9$ are excluded as extreme rays and $R^t_1+R^t_4, R^t_2+R^t_5, R^t_3+R^t_6$ appear as new extreme rays. In general, it can be obtained by considering the condition for the existence of nonnegative core allocations. In the same manner, as in Proposition 1, the problem reduces to

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N, |S| \ge 2} \gamma _S v(S)+\gamma _Nv(N) \le 0 \end{aligned}$$

for every $\gamma \in {\mathbb {R}}^{2^n-n-1}$ such that

$$\begin{aligned} (b)'\cdots {\left\{ \begin{array}{ll} \sum \nolimits _{\emptyset \ne S \subseteq N, |S|\ge 2, i \in S} \gamma _S \le 0, \forall i \in N,\\ -\gamma _S \le 0, \forall S \subsetneq N, |S| \ge 2.\\ \end{array}\right. } \end{aligned}$$

Then, 0-normalized balanced games can be written as

$$\begin{aligned} v={\tilde{R}}\mu , \mu \ge {{\textbf {0}}}, \end{aligned}$$

where ${\tilde{R}}$ is the generating matrix of the cone corresponding to $(b)'$. Table 2 shows ${\tilde{R}}^t$ for $n=3$ where ${\tilde{R}}^t_i$ is the i-th row vector of ${\tilde{R}}^t$.

In addition, every nonnegative 0-normalized game is represented as the nonnegative linear combination of 0-normalized simple N-monotonic veto-controlled games, which is first shown by Abe (2019).¹² We can straightforwardly prove this characterization result as a corollary of Theorem 2. Since the case of $v(N)=0$ is obvious, without loss of generality, we assume that $v(N)=1$. Then, by Theorem 2, v is balanced if and only if

$$\begin{aligned}{\left\{ \begin{array}{ll} \alpha _{\{i\}}-\alpha ^-_{\{i\}}=0, \forall i \in N,\\ \sum _{i \in N}\alpha _{\{i\}}=1,\\ \sum _{i \in S} \alpha _{\{i\}}-\alpha ^-_S \in [0,1], \forall S \subsetneq N,\\ \alpha _i, \alpha ^-_S \ge 0, \forall i \in N, S \subsetneq N. \end{array}\right. } \end{aligned}$$

Since the set of vectors $\alpha =\Bigl ( (\alpha _i)_{i \in N}, (\alpha ^-_S)_{S \subsetneq N} \Bigr ) \in {\mathbb {R}}^{2^n+n-2}$ satisfying the above conditions is convex, it is sufficient to consider its extreme points. Then, we can see that $\alpha$ is an extreme point if and only if there is $i \in N$ such that

$$\begin{aligned} {\left\{ \begin{array}{ll} \alpha _{\{i\}}=\alpha ^-_{\{i\}}=1, \alpha _{\{j\}}=0, \forall j \ne i,\\ \alpha ^-_S=0, \forall S \subseteq N \setminus \{i\},\\ \alpha ^-_S \in \{0,1\}, \forall S \subsetneq N,~\text {with}~i \in S. \end{array}\right. } \end{aligned}$$

Notice that i is a veto player in the game corresponding to such $\alpha$ so that it is a veto-controlled game. Moreover, we can see that the game is 0-normalized, simple, and N-monotonic. Table 3 shows the extreme points in the case of $n=3$.

Table 1 Extreme points of balanced games for $n=3$

Table 2 Extreme points of 0-normalized balanced games for $n=3$

Table 3 Extreme points of 0-normalized nonnegative balanced games for $n=3$

4 The Shapley value and the core

Let ${\mathcal {G}}_N^{Sh}=\{v \in {\mathcal {G}}_N| Sh(v) \in C(v)\}$ be the set of games whose Shapley value lies in the core. It follows that ${\mathcal {G}}_N^{Sh}\subsetneq {\mathcal {G}}_N^B$. In this section, we characterize the set ${\mathcal {G}}_N^{Sh}$ given the decomposition result of ${\mathcal {G}}_N^B$ discussed in Theorem 2.

For each balanced vector $\gamma \in {\mathbb {R}}^{2^n-2}_{+}$, let us define

$$\begin{aligned} v^{\gamma }=\sum _{S \subsetneq N}|S|\gamma _Su_S. \end{aligned}$$

Then, $Sh_i(v^{\gamma })=1$ for every $i \in N$ because, by (2), for every $i \in N$,

$$\begin{aligned} Sh_i(v^{\gamma })=\sum _{\emptyset \ne S\subsetneq N, i \in S} \frac{|S|\gamma _S}{|S|}=\sum _{\emptyset \ne S \subsetneq N, i \in S} \gamma _S=1. \end{aligned}$$

In other words, the balanced vector $\gamma$ yields a game $v^{\gamma }$ in which the Shapley value assigns 1 to every player.¹³ In the same vein, we construct another game that is useful for our further analysis. We say that the vector $\beta =\Bigl ((\beta _S)_{S \subsetneq N}, \beta _N \Bigr ) \in {\mathbb {R}}^{2^n-2}_{+} \times {\mathbb {R}}$ is an extended balanced vector if for every $i \in N$,

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N, i \in S}\beta _S+\beta _N=0. \end{aligned}$$

Note that this condition is equivalent to (a): $\beta$ with $\beta _N=-1$ being a balanced vector. For every extended balanced vector $\beta =\Bigl ((\beta _S)_{S \subsetneq N}, \beta _N \Bigr ) \in {\mathbb {R}}^{2^n-2}_{+} \times {\mathbb {R}}$, let us define

$$\begin{aligned} v^{\beta -}=-\sum _{S \subsetneq N}|S|\beta _Su_S-n\beta _N u_N. \end{aligned}$$

Lemma 2

For every extended balanced vector $\beta =\Bigl ((\beta _S)_{S \subsetneq N}, \beta _N \Bigr ) \in {\mathbb {R}}^{2^n-2}_{+} \times {\mathbb {R}}$, the game $v^{\beta -}$ has the following properties.

• (i) $Sh_i(v^{\beta -})=0$ for every $i \in N$.

• (ii) There is $(\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}$ such that $v^{\beta -}=\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^-$.

• (iii) $v^{\beta -}$ is a nonnegative linear combination of $(v^{\beta _k-})_{k=1}^{K_n}$ where $\beta _k=(\gamma _k, -1)$ and ${\mathcal {B}}(\gamma _k)$ is a minimal balanced collection. That is, there is $\mu \in {\mathbb {R}}^{K_n}_{+}$ such that $v^{\beta -}=\sum _{k=1}^{K_n}\mu _k v^{\beta _k-}$.

Proof

(i) It follows by construction: For every $i \in N$,

$$\begin{aligned} Sh_i(v^{\beta -})=-\sum _{\emptyset \ne S\subseteq N, i \in S} \frac{|S|\beta _S}{|S|}=-\bigl (\sum _{\emptyset \ne S \subsetneq N, i \in S} \beta _S+\beta _N\bigr )=0. \end{aligned}$$

(ii) we have

$$\begin{aligned} v^{\beta -}= & \, -\sum _{T \subsetneq N}|T|\beta _Tu_T-n\beta _N u_N\\= & \, \sum _{T \subsetneq N}|T|\beta _T\bigl (\sum _{T \subseteq S}u^-_S \bigr )-n\beta _N u_N\\= & \, \sum _{S \subseteq N}\Bigl (\sum _{T \subseteq S}|T|\beta _T\Bigr )u^-_S\\= & \, \sum _{S \subsetneq N}\Bigl (\sum _{T \subseteq S}|T|\beta _T\Bigr )u^-_S\\= & \, \sum _{S \subsetneq N}\alpha ^-_S u^-_S \end{aligned}$$

since $\Bigl (\sum _{T \subseteq N}|T|\beta _T\Bigr )=\sum _{i \in N}\Bigl (\sum _{\emptyset \ne T \subsetneq N, i \in T}\beta _T+\beta _N\Bigr )=0$. Then, $\alpha ^-_S=\Bigl (\sum _{T \subseteq S}|T|\beta _T\Bigr )\ge 0$ follows because $(\beta _S)_{S \subsetneq N} \in {\mathbb {R}}^{2^n-1}_{+}$.

(iii) For each balanced vector $\gamma$, let $\beta (\gamma )=(\gamma , -1)$. Since the set of extended balanced vectors is a polyhedral cone whose extreme rays are $\beta (\gamma _k)=\beta _k$ where ${\mathcal {B}}(\gamma _k)$ is a minimal balanced collection, for every extended balanced vector $\beta$, the corresponding game $v^{\beta -}$ can be represented as a nonnegative linear combination of $(v^{\beta _k-})_{k=1}^{K_n}$, namely, $v^{\beta -}=\sum _{k=1}^{K_n}\mu _k v^{\beta _k-}$ where $(\mu _k)_{k=1}^{K_n}\ge {{\textbf {0}}}$. $\square$

Lemma 2 provides a representation of the games in a strict subset of

$$\begin{aligned} {\mathcal {G}}_N^-=\Bigl \{v \in {\mathbb {R}}^{2^n-1}|v=\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^-, \ (\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}, \ Sh(v)=\mathbf {0}\Bigr \}. \end{aligned}$$

Moreover, by (ii) of Lemma 2, there is a one-to-one relationship between each $v \in {\mathcal {G}}_N^-$ and $v^{\beta -}$ with $\beta \in {\mathbb {R}}^{2^n-1}$ such that

$$\begin{aligned}{\left\{ \begin{array}{ll} \sum \nolimits _{\emptyset \ne S \subsetneq N, i \in S}\beta _S+\beta _N=0,\\ \sum _{T \subseteq S}|T|\beta _T \ge 0, \cdots (**) \end{array}\right. } \end{aligned}$$

for every $S \subsetneq N$, which is a weaker condition than $(\beta _S)_{S \subsetneq N} \in {\mathbb {R}}^{2^n-1}_{+}$. We call vectors $\beta \in {\mathbb {R}}^{2^n-1}$ that satisfy the above condition weakly extended balanced vectors. The following Lemma shows that there is also a one-to-one relationship between an extreme ray of the set of weakly extended balanced vectors and that of extended balanced vectors. Moreover, we can provide an explicit linear transformation between them.

Lemma 3

For every $v \in {\mathcal {G}}_N^-$, there is $\mu \in {\mathbb {R}}^{K_n}_{+}$ such that $v=\sum _{k=1}^{K_n}\mu _k v^{{\tilde{\beta }}_k-}$ where each ${\tilde{\beta }}_k$ is an extreme ray of the set of weakly extended balanced vectors and is a linear transformation of an extended balanced vector $\beta _k=(\gamma _k, -1)$ such that ${\mathcal {B}}(\gamma _k)$ is a minimal balanced collection.

Proof

For every $\beta \in {\mathbb {R}}^{2^n-2}$, the condition $\beta \ge {{\textbf {0}}}$ is equivalent to

$$\begin{aligned} E_{2^n-2} \beta \ge {{\textbf {0}}}, \end{aligned}$$

where $E_{2^n-2} \in {\mathbb {R}}^{(2^n-2) \times (2^n-2)}$ is the identity matrix. Similarly, the condition $(**)$ is represented by

$$\begin{aligned} A \beta \ge {{\textbf {0}}}, \end{aligned}$$

where $A \in {\mathbb {R}}^{(2^n-2) \times (2^n-2)}$ and it has full rank. Since an extreme ray of a polyhedral cone in ${\mathbb {R}}^k$ is characterized by the $k-1$ linearly independent equations of its generating matrix, an extreme ray of extended balanced vectors must satisfy

$$\begin{aligned} (E_{2^n-2})_I \beta ={{\textbf {0}}} \end{aligned}$$

and that of the set of weakly extended balanced vectors must satisfy

$$\begin{aligned} A_I \beta ={{\textbf {0}}}, \end{aligned}$$

where both $(E_{2^n-2})_I, A_I \in {\mathbb {R}}^{|I| \times (2^n-2)}$ are sub-matrices of $E_{2^n-2}$ and A for some index set $I \subseteq \{1,\dots 2^n-2\}$, respectively.

Then, we can see that, for every index set $I \subseteq \{1,\dots 2^n-2\}$ and $\beta$ satisfying $(E_{2^n-2})_I \beta ={{\textbf {0}}}$, we have

$$\begin{aligned} {{\textbf {0}}}= & \, (E_{2^n-2})_I \beta \\= & \, (AA^{-1})_I\beta \\= & \, A_IA^{-1}\beta \\= & \, A_I{\tilde{\beta }} \end{aligned}$$

where ${\tilde{\beta }}=A^{-1} \beta$, and, conversely, for every index set $I \subseteq \{1,\dots 2^n-2\}$ and $\beta$ satisfying $A_I\beta ={{\textbf {0}}}$, we have

$$\begin{aligned} {{\textbf {0}}}= & \, A_I\beta \\= & \, (E_{2^n-2})_I A\beta \\= & \, (E_{2^n-2})_I {\hat{\beta }} \end{aligned}$$

where ${\hat{\beta }}=A\beta$. Therefore, there is a one-to-one relationship between an extreme ray of the extended balanced vectors and that of weakly extended balanced vectors, which implies the result. $\square$

Tables 4 and 5 show $v^{{\tilde{\beta }}_k-}$ for $n=3,4$ respectively. In each column of $\gamma _k$, we only describe the weight on each $S \in {\mathcal {B}}(\gamma _k)$.

Table 4 $v^{{\tilde{\beta }}_k-}$ for $n=3$

Table 5 $v^{{\tilde{\beta }}_k-}$ for $n=4$. Each ${\mathcal {B}}$ is symmetric under permutation

Now, we state our main result of the decomposition of ${\mathcal {G}}_N^{Sh}$. In the following statement, the definition of ${\tilde{\beta }}_k$ is the same as that in Lemma 3.

Theorem 4

Let $v \in {\mathcal {G}}_N$. We have $Sh(v) \in C(v)$ if and only if v is the sum of (i) a linear combination of singleton unanimity games and (ii) a nonnegative linear combination of $(v^{{\tilde{\beta }}_k-})_{k=1}^{K_n}$:

$$\begin{aligned} v=\sum _{i \in N}\alpha _i u_{\{i\}}+\sum _{k=1}^{K_n}\mu _k v^{{\tilde{\beta }}_k-} \end{aligned}$$

where $(\alpha _i)_{i \in N}=Sh(v)$ and $(\mu _k)_{k=1}^{K_n} \ge {{\textbf {0}}}$.

Proof

By the proof of Lemma 1, $Sh(v) \in C(v)$ if and only if

$$\begin{aligned} v=\sum _{i \in N}Sh_i(v)u_{\{i\}}+\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^- \end{aligned}$$

where $(\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}$. Then, by construction, $Sh(\sum _{\emptyset \ne S \subsetneq N}\alpha _S u_S^-)=\mathbf {0}$. Since $\sum _{\emptyset \ne S \subsetneq N}\alpha _S u_S^- \in {\mathcal {G}}_N^-$, by Lemma 3, it can be represented as

$$\begin{aligned} \sum _{\emptyset \ne S \subsetneq N}\alpha _S u_S^-=\sum _{k=1}^{K_n}\mu _k v^{{\tilde{\beta }}_k-} \end{aligned}$$

where $(\mu _k)_{k=1}^{K_n} \ge {{\textbf {0}}}$. Therefore, v is decomposed as follows:

$$\begin{aligned} v=\sum _{i \in N}Sh_i(v)u_{\{i\}}+\sum _{k=1}^{K_n}\mu _k v^{{\tilde{\beta }}_k-}, \end{aligned}$$

which completes the proof. $\square$

This result and Lemma 3 suggest that we can count the number of extreme rays of ${\mathcal {G}}_{N}^{Sh}$. The number of nontrivial extreme rays is equal to the number of minimal balanced games as follows.

Corollary 2

The number of extreme rays of ${\mathcal {G}}_N^{Sh}$ is $2n+K_n$. Each of them corresponds to a singleton unanimity game, a negative singleton unanimity game, or a game $v^{{\tilde{\beta }}_k-}$ corresponding to minimal balanced collections as in Lemma 3.

Before closing this section, we compare our result with other conditions studied in the literature. Inarra and Usategui (1993) show that $v \in {\mathcal {G}}_{N}^{Sh}$ if and only if for every $T \subseteq N$,

$$\begin{aligned} \sum _{\emptyset \ne S \subseteq N}\frac{(n-s)!(s-1)!}{n!}h_T(S)(v(S)-v(S \setminus T)-v(S \cap T))\ge 0, \end{aligned}$$

where

$$\begin{aligned} h_T(S)= \left\{ \begin{array}{ll} |S|\cdot \bigl ( \frac{|S \cap T|}{|S|}-\frac{|T\setminus S|}{|N \setminus S|} \bigr ) &\, \mathrm{if}~S \ne N,\\ |T| &\, \mathrm{if}~S=N. \end{array} \right. \end{aligned}$$

Izawa and Takahashi (1998) show that $v \in {\mathcal {G}}_{N}^{Sh}$ if and only if for every $T \subseteq N$,

$$\begin{aligned} \sum _{S \subset N}\sum _{i \in S \cap T}\frac{(n-s)!(s-1)!}{n!}(v^i(S)-v^i(S \cap T))\ge 0, \end{aligned}$$

where $v^i(S)=v(S)-v(S \setminus \{i\})$. Since both conditions are written as a linear transformation of v, we can observe that there is $A \in {\mathbb {R}}^{m \times (2^n-1)}$ such that ${\mathcal {G}}_{N}^{Sh}=\{v \in {\mathcal {G}}_{N}| A v \ge {{\textbf {0}}} \}$. Hence, these conditions also show that ${\mathcal {G}}_{N}^{Sh}$ is a polyhedral cone. However, both conditions neither provide any information about its extreme rays nor any reduced expression of the generating matrix. In contrast, our approach has the following three advantages. First, we can explicitly construct each extreme ray. Second, we can decompose every game in the class ${\mathcal {G}}_{N}^{Sh}$ into simple games, each of which corresponds to an extreme ray. Finally, and more importantly, we can apply our method to other linear solutions, whereas the two conditions above are applicable only for the Shapley value. In the next section, we conclude our results and elaborate on the third advantage, i.e., applicability, mentioned above.

5 Discussion

5.1 Convex games

Convexity and average convexity are two widespread sufficient conditions for the Shapley value to lie in the core.¹⁴ In particular, if a game $v \in {\mathcal {G}}_{N}$ is convex, Edmond (1970) and Shapley (1971) independently show that the vector of marginal contributions, $(mc_{i,\sigma }(v))_{i \in N}$, is in the core for every ordering $\sigma \in \Pi$ and thus that $Sh(v) \in C(v)$. Moreover, Ichishi (1981) shows its converse: $(mc_{i,\sigma }(v))_{i \in N} \in C(v)$ for every $\sigma \in \Pi$ only if v is convex. By associating their results with our Theorem 2, we can observe that a game $v \in {\mathcal {G}}_{N}$ is convex if and only if for every $\sigma \in \Pi$ there are $(\alpha ^{\sigma }_i)_{i \in N} \in {\mathbb {R}}^n$ and $(\alpha ^{\sigma -}_S)_{S \subsetneq N} \ge {{\textbf {0}}}$ such that

$$\begin{aligned} v=\sum _{i \in N}\alpha ^{\sigma }_i u_{\{i\}}+\sum _{\emptyset \ne S \subsetneq N}\alpha ^{\sigma -}_S u_S^- \end{aligned}$$

and $mc_{i,\sigma }(\sum _{\emptyset \ne S \subsetneq N}\alpha ^{\sigma -}_S u_S^-)=0$ for all $i \in N$. Since the set of convex games is also a polyhedral cone, a convex game can be further decomposed into the sum of simple games as in Theorem 4. A similar observation holds for average convex games.

In the Online Appendix, which is available on the authors’ webpages, we provide the H-representation of ${\mathcal {G}}_{N}^{Sh}$ and that of the sets of convex games and average convex games. Moreover, we demonstrate the relationship among these sets based on the representations. However, obtaining V-representations of those sets is not necessarily straightforward. For example, one of the difficulties is to obtain extreme rays of the set of convex games. In this case, we must consider not only the set

$$\begin{aligned} {\mathcal {G}}_N^{\sigma -}=\Bigl \{w \in {\mathbb {R}}^{2^n-1}|w=\sum _{\emptyset \ne S \subsetneq N}\alpha ^-_S u_S^-, \ (\alpha ^-_S)_{S \subsetneq N} \ge {{\textbf {0}}}, \ mc_{i,\sigma }(w)=\mathbf {0}\Bigr \} \end{aligned}$$

for all $\sigma \in \Pi$ but also the consistency of the representations for all $\sigma \in \Pi$ in the above sense, which is not covered by Theorems 2 and 4. To deal with such difficulty is still an open question. However, our methods provided in this paper would be a useful tool.

5.2 Allocation schemes and decompositions

Our decomposition approach is closely related to the notion of allocation schemes. An allocation scheme is a collection of allocations that assigns an S-dimensional allocation to every coalition S, i.e., $(x^S)_{S\subseteq N}$ where $x^S \in {\mathbb {R}}^s$. Sprumont (1990) introduces a concept called a population monotonic allocation scheme (PMAS), defined as follows: For every $S, T \subseteq N$, $S\supseteq T$ $\Rightarrow$ $x^S_j\ge x^T_j$ for every $j\in T$. He shows that a game has a PMAS if and only if it can be decomposed into the sum of singleton unanimity games and nonnegative linear combinations of simple monotonic veto-controlled games and that if a game is convex, then (an extended version of) the Shapley value generates a PMAS.

We emphasize that our decomposition result for ${\mathcal {G}}_{N}^{Sh}$ and Sprumont’s (1990) result are independent, i.e., each one does not imply the other. Indeed, the Shapley value of a simple monotonic veto-controlled game does not always lie in the core, which suggests that possessing a PMAS is not a sufficient condition for the Shapley value to be in the core. Moreover, a game $v \in {\mathcal {G}}_{N}^{Sh}$ may lack a PMAS. To see this, we consider an exact assignment game (Hoffmann and Sudhölter 2007). A game is exact if for every $S\subseteq N$, there is a core element x such that $\sum _{j\in S}x_j=v(S)$. For instance, an assignment game with two buyers and two sellers, where a pair of one buyer and one seller produces surplus 1, is an exact assignment game. Hoffmann and Sudhölter (2007) show that the Shapley value of an exact assignment game is in the core, i.e., an exact assignment game is in ${\mathcal {G}}_{N}^{Sh}$, while as demonstrated by Sprumont (1990), this assignment game has no PMAS. Therefore, Sprumont’s decomposition does not apply to this game.

Although a game $v \in {\mathcal {G}}_{N}^{Sh}$ does not have any PMAS in general, it may have an allocation scheme satisfying less demanding properties. For example, the definition of exact games enables an allocation scheme to consist of core elements, which is less demanding than population monotonicity. We conjecture that some properties of allocation schemes may lead to another decomposability of games.¹⁵ Combining such properties and our Theorem 4 must be helpful to understand the reason why an exact assignment game is in ${\mathcal {G}}_{N}^{Sh}$ in terms of the decomposition of games. In addition, every average convex game is in ${\mathcal {G}}_{N}^{Sh}$ and is decomposed as demonstrated in Subsection 5.1. Therefore, if there is a general connection between the decomposability and the notion of allocation schemes, it must be a key to answering the long-standing open question; “Does an average convex game have a PMAS?”

5.3 Generalization to linear solutions

Our results can be a more powerful method when we consider the relationship between the core and arbitrary linear solutions including the Shapley value.¹⁶ We elaborate on this point below by borrowing the arguments by Yokote et al. (2016).

For each nonempty $T \subseteq N$, a commander game ${\bar{u}}_T \in {\mathcal {G}}_N$ is defined as

$$\begin{aligned} {\bar{u}}_T(S)= \left\{ \begin{array}{ll} 1 &\, \mathrm{if}~ |T \cap S|=1, \\ 0 &\, \mathrm{otherwise}.\\ \end{array} \right. \end{aligned}$$

Yokote et al. (2016) show that $\{{\bar{u}}_T\}_{\emptyset \ne T \subseteq N}$ is another basis of ${\mathcal {G}}_N$: A game v is represented as $v=\sum _{\emptyset \ne T \subseteq N} d_T \bar{u}_T$, where $d=(d_T)_{\emptyset \ne T \subseteq N}$ is the coefficient of the corresponding ${\bar{u}}_T$. Note that ${\bar{u}}_{\{i\}}=u_{\{i\}}$ for every $i \in N$. Moreover, Yokote et al. (2016) show that, for every $i \in N$, $d_{\{i\}}=Sh_i(v)$, that is, the coefficients of singleton commander games coincide with the Shapley value and commander games $({\bar{u}}_T)_{T, |T| \ge 2}$ span the null space of the Shapley value; $Sh({\bar{u}}_T)={{\textbf {0}}}$ for every $T \subseteq N$ with $|T| \ge 2$. Hence, each game v is uniquely represented as

$$\begin{aligned} v=\sum _{i \in N}Sh_i(v)u_{\{i\}}+\sum _{\emptyset \ne T \subseteq N, |T|\ge 2}d_T {\bar{u}}_T. \end{aligned}$$

(3)

Since game v is uniquely represented as the linear combination of commander games by (3), we write

$$\begin{aligned} v=v^++w \end{aligned}$$

where $Sh_i(w)=0$ for every $i \in N$. Therefore, $Sh(v) \in C(v)$ if and only if $Sh(w)={{\textbf {0}}} \in C(w)$.

If a solution f is linear, in view of (1), $f_i(v)=\sum _{\emptyset \ne T \subseteq N}\lambda _Tf_i(u_T)$ for every $i \in N$. Hence, if we can identify a new basis $\bigl ( (u_{\{i\}})_{i \in N}, (u^f_S)_{S \subseteq N, |S|\ge 2} \bigr )$ such that $f(u^f_S)={{\textbf {0}}}$ for every $S \subseteq N$ with $|S|\ge 2$, then, by the same argument as above, we have $f(v) \in C(v)$ if and only if $f(w^f)={{\textbf {0}}} \in C(w^f)$ where $v=\sum _{i \in N}f_i(v)u_{\{i\}}+w^f$. To find the condition for ${{\textbf {0}}} \in C(w^f)$, suppose that $f_i(u_T)$ is written as $f_i(u_T)=\frac{f_{i,T}}{f_T}$ for some $f_{i,T} \in {\mathbb {R}}$ and $f_T>0$. For instance, if $f=Sh$,

$$\begin{aligned} f_{i,T}={\left\{ \begin{array}{ll} 1~\text {if}~i \in T,\\ 0~ \text {otherwise}. \end{array}\right. } f_T=|T|. \end{aligned}$$

Now, consider the following constraints: For every $\beta ^f=\Bigl ((\beta ^f_S)_{S \subsetneq N}, \beta ^f_N \Bigr ) \in {\mathbb {R}}^{2^n-2}_{+} \times {\mathbb {R}}$ and every $i \in N$,

$$\begin{aligned} \sum _{S \subsetneq N}f_{i,S}\beta ^f_S+f_{i,N}\beta ^f_N=0. \end{aligned}$$

A vector $\beta ^f$ satisfying the above condition can be seen as a weighted generalized balanced vector. Now, define a game

$$\begin{aligned} v^{\beta ^f-}= & \, -\sum _{S \subsetneq N}f_T\beta _Su_S-f_T\beta _N u_N\\= & \, \sum _{S \subsetneq N} \Bigl (\sum _{T \subseteq S}f_T\beta ^f_T\Bigr )u_S^-. \end{aligned}$$

In the same manner as Lemma 2, $f_i(v^{\beta ^f-})=0$ for all $i \in N$. Moreover, each $v^{\beta ^f-}$ can be decomposed into a nonnegative linear combination of the games derived from the extreme rays of weighted generalized balanced vectors. Hence, the remaining step is to consider the extreme rays of the following polyhedral cone

$$\begin{aligned}{\left\{ \begin{array}{ll} \sum \nolimits _{S \subsetneq N}f_{i,S}\beta ^f_S+f_{i,N}\beta ^f_N=0, \forall i \in N,\\ \sum \nolimits _{T \subseteq S}f_T\beta ^f_T \ge 0, \forall S \subsetneq N. \end{array}\right. } \end{aligned}$$

Since the matrix that constitutes the inequality constraints has full rank (i.e, ignoring $\beta _N$ and consider the constraints in dimension ${\mathbb {R}}^{2^n-2}$) by $f_T>0$ for all $T \subseteq N$, the same argument as in Lemma 3 generates the extreme rays as desired.

As a special case, Yokote et al. (2016) propose a basis $\bigl ( (u_{\{i\}})_{i \in N}, (u^f_S)_{S \subseteq N, |S|\ge 2} \bigr )$ when f is a weighted Shapley value and a (extended version of) discounted Shapley value. We can straightforwardly apply the above procedure even to these cases. In addition, since our method is applicable for every linear solution as long as a suitable basis is obtained, we can similarly obtain the core selection result for every linear solution.

6 Summary

In this paper, we provide the geometric characterization of balanced games and a new necessary and sufficient condition for the Shapley value to be in the core. To be more specific, we show that all balanced games are decomposed into some simple games. This decomposition approach is applied to the characterization of the class of games whose core contains the Shapley value. We show that all games whose Shapley value lies in the core can be decomposed into some simple games with certain conditions. This result shows that (i) different classes of games may have some common geometric properties and that (ii) we can apply the common properties to the analysis of the relationship among solution concepts in the classes. Moreover, the attempt to generalize the Shapley value to an arbitrary linear solution is also provided.