Preserving coalitional rationality for non-balanced games

In cooperative games, the core is one of the most popular solution concept since it ensures coalitional rationality. For non-balanced games however, the core is empty, and other solution concepts have to be found. We propose the use of general solutions, that is, to distribute the total worth of the game among groups rather than among individuals. In particular, the \(k\)-additive core proposed by Grabisch and Miranda is a general solution preserving coalitional rationality which distributes among coalitions of size at most \(k\), and is never empty for \(k\ge 2\). The extended core of Bejan and Gomez can also be viewed as a general solution, since it implies to give an amount to the grand coalition. The \(k\)-additive core being an unbounded set and therefore difficult to use in practice, we propose a subset of it called the minimal negotiation set. The idea is to select elements of the \(k\)-additive core mimimizing the total amount given to coalitions of size greater than 1. Thus the minimum negotiation set naturally reduces to the core for balanced games. We study this set, giving properties and axiomatizations, as well as its relation to the extended core of Bejan and Gomez. We give a method of computing the minimum bargaining set, and lastly indicate how to eventually get classical solutions from general ones.

1. Although in its formulation it is not. We call it \(\mathsf {G}\)-extended core when rewritten as a general solution.

2. This will be seen as a consequence of Proposition 3 (iv) with \(k=n\).

3. The original definition is expressed through \(k\)-additive games, and is equivalent to this one. Specifically, viewing classical payoff vectors as additive games, the core can be defined as \(\{\phi \in \mathcal {G}^1(N)\mid \phi (S)\ge v(S),\forall S\subseteq N, \phi (N)=v(N)\}\). This viewpoint is the current one in decision theory, where coalitional rationality is rather called dominance. Now, the generalization of this definition to \(k\)-additive games is straightforward, and leads to the original definition of the \(k\)-additive core in Miranda and Grabisch (2010) (and moreover explains its name): \(\{\phi \in \mathcal {G}^k(N)\mid \phi (S)\ge v(S),\forall S\subseteq N, \phi (N)=v(N)\}\). The equivalence is clearly seen by the definition of \(k\)-additive games and Eq. (2), and we see that the Möbius transform plays the rôle of the generalized payoff vector. Although this view is mathematically more natural and elegant, we have opted for the definition based on payoff vectors, since it is closer to game theory.

4. A polyhedron is pointed if it has vertices (equivalently, if it contains no line).

5. Up to the natural identification between payoff vectors and general payoff vectors.

6. A more general solution would be to allow real-valued amounts, that is, even in the case of benefit, some players would have to pay something. But we do not see any convincing example where this method would be relevant. In game theory, for example when defining the selectope Derks et al. (2000), sharing functions are assumed to take values in \([0,1]\). It is the same for division rules in bankruptcy or tax problems Thomson (2003) (another way to consider the above sharing problem; see Sect. 5).

7. Up to the natural identification between payoff vectors and general payoff vectors. The same remark applies to the next item.

8. This is the case of all \(L_p\) norms, except \(L_\infty \). However, for the latter a simple modification of the proof makes the statement valid for \(L_\infty \) too: it suffices to take for \(S\) a maximizer of \(x_S\) and assume that \(x_S\) is positive.

9. A game \(v\) is symmetric if \(v(S)\) depends only on the cardinality of \(S\) for each \(S\).

Authors and Affiliations

1. Paris School of Economics, University of Paris I, 106-112, Bd de l’Hôpital, 75013, Paris, France

   Stéphane Gonzalez & Michel Grabisch

Corresponding author

Correspondence to Stéphane Gonzalez.

Appendix

Proof of Theorem 5

First we need the following result.

Proposition 10

Let \(v\) be a game on \(N\). Suppose it exists \(S\subset N, |S|\ge 2\), such that for all \(x \in \mathsf {I}_1^n(v), x_S=0\). Then the following holds.

1. (i)

   For all \(x \in \mathsf {I}_1^n(v)\), for all \(T\subseteq S, |T|\ge 2\), we have \(x_T=0\).

2. (ii)

   There exists \(T\supseteq S, T\ne N\), such that \(\mathsf {C}(v_T)\ne \emptyset \).

Proof

1. (i)

   Suppose there exists \(x \in \mathsf {I}_1^n(v)\) and \(T\subseteq S\) such that \(x_S=0\) and \(x_T<0\). Then the payoff \(x'\) defined by

   

   belongs to \(\mathsf {I}_1^n(v)\), which contradicts the definition of \(S\).

2. (ii)

   Take \(S\subset N, |S|\ge 2\), such that for all \(x \in \mathsf {I}_1^n(v), x_S=0\). We prove that if \(\forall T\supseteq S, T\ne N\), we have \(\mathsf {C}(v_T) = \emptyset \), then there exists \(x\in \mathsf {I}_1^n(v)\) such that \(x_S<0\).

Let \(\tilde{x}\in \mathsf {GEC}(v)\subseteq \mathsf {I}_1^n(v)\). We put

Observe that \(t>0\). Indeed, \(t=0\) would imply that for some \(T\supseteq S, T\ne N, \sum _{K\subseteq T}\tilde{x}_K=v(T)\). Since \(\tilde{x}\in \mathsf {GEC}\), its coordinates are 0 for all nonsingleton subsets of \(T\). Therefore, \(\sum _{i\in T'}\tilde{x}_i\ge v(T')\) for all \(T'\subset T\), and \(\sum _{i\in T}\tilde{x}_i= v(T)\). It follows that the vector \((\tilde{x}_i)_{i\in N}\) is an element of the core \(\mathsf {C}(v_T)\), a contradiction.

Then the general payoff vector \(x\) defined by

belongs to \(\mathsf {I}_1^n(v)\).\(\square \)

(of Theorem 5) (i) \(\Rightarrow \) (ii). Let \(x\in \mathsf {I}_1^n(v)\). By Corollary 1, we have \((x_1,\ldots ,x_n)\in \mathsf {C}(v^{\bar{t}(v)})\), which yields \(\sum _{i\in T}x_i=v(T)\). Therefore if \(x_S<0\), we would have \(\sum _{S\subseteq T}x_T<v(T)\), which contradicts \(x\in \mathsf {I}_1^n(v)\).

(ii) \(\Rightarrow \) (i). Define \(T\) as a maximal element (in the sense of inclusion) of \(\{L \supseteq S, \, x_L=0, \, \forall x\in \mathsf {I}_1^n(v)\}\). Suppose \(T=N\). Then for all \(x\in \mathsf {I}_1^n(v), x_N=0\), which implies that \(\bar{t}(v)=0\) since \(\mathsf {GEC}(v)\subseteq \mathsf {I}_1^n(v)\). Therefore \(\mathsf {C}(v)\ne \emptyset \), and (i) holds for \(T=N\).

We assume now that \(T\ne N\). Due to Proposition 10 (i) and the definition of \(T\), for any set \(L\subseteq T, |L|\ge 2\), we have \(x_L=0\) for all \(x\in \mathsf {I}_1^n(v)\), and for all \(L\supset T, x_L\ne 0\) for at least one \(x\in \mathsf {I}_1^n(v)\). It follows that

For the rest of the proof, we introduce the shorthand \(\phi ^x\) for \(m^{-1}(x)\), where \(x\) is a general payoff vector. From the above equation and Corollary 1, it suffices to show that \(\phi ^x(T)=v(T)\) for all \(x\in \mathsf {I}_1^n(v)\) in order to prove that \(y(T)=v(T)\) for all \(y\in \mathsf {C}(v^{\bar{t}(v)})\). Suppose then that there exists \(x_0\in \mathsf {I}_1^n(v)\) such that \(\phi ^{x_0}(T)>v(T)\). We distinguish two cases.

Suppose first that \(T=N\setminus i\). Suppose there exists \(x\in \mathsf {I}_1^n(v)\) such that \(\phi ^x(N\setminus i)>v(N\setminus i)\). Take \(x'\in \mathsf {I}_1^n(v)\) such that \(x'_N<0\) (necessarily exists otherwise \(T=N\)), and build the payoff vector \(x''=\frac{1}{2}(x+x')\). Define \(\tilde{x}\) by

Then \(\tilde{x}\in \mathsf {I}_1^n(v)\), although \(\tilde{x}_{N\setminus i}<0\), a contradiction.

Suppose next that \(T\) is not of the form \(N\setminus i\). We know that for all \(T'\supset T, T'\ne N\), there exists \(x^{T'}\in \mathsf {I}_1^n(v)\) such that \(x^{T'}_{T'}<0\). Define \(\tilde{x}=\sum _{T'\supset T, T'\ne N}\alpha _{T'}x^{T'}\), with \(\alpha _{T'}\in (0,1), \sum _{T'\supset T,T'\ne N}\alpha _{T'}=1\). Then by convexity of \(\mathsf {I}_1^n(v)\), it follows that \(\tilde{x}\in \mathsf {I}_1^n(v)\), and we have \(\tilde{x}_{T'}<0\), for all \(T'\supset T, T\ne N\). Consider the payoff vector \(x'=\frac{1}{2}(x_0+\tilde{x})\), which belongs to \(\mathsf {I}_1^n(v)\) by convexity, and put

and choose \(\tilde{K}\) which realizes the minimum of \(\min _{T\subset K\subset N}(-x'_K)\). Build \(x^*\) as follows:

We claim that \(x^*\in \mathsf {I}_1^n(v)\), which contradicts the hypothesis \(x_T=0\) for all \(x\in \mathsf {I}_1^n(v)\). Indeed, it suffices to verify coalitional rationality:

1. (i)

   If \(K\supseteq \tilde{K}\), we have \(\phi ^{x^*}(K)=\phi ^{x'}(K)\ge v(K)\).

2. (ii)

   If \(K\supseteq T\) and \(K\not \supseteq \tilde{K}\), then

   $$\begin{aligned} \phi ^{x^*}(K)=\phi ^{x'}(K)-\epsilon \ge \phi ^{x'}(K) - (\phi ^{x'}(K)-v(K))=v(K). \end{aligned}$$
3. (iii)

   If otherwise \(K\subseteq T\), then \(\phi ^{x^*}(K)=\phi ^{x'}(K)\ge v(K)\). \(\square \)

Reprints and permissions