The core and the steady bargaining set for convex games

Within the class of zero-monotonic and grand coalition superadditive cooperative games with transferable utility, the convexity of a game is characterized by the coincidence of its core and the steady bargaining set. As a consequence it is proved that convexity can also be characterized by the coincidence of the core of a game and the modified Zhou bargaining set à la Shimomura.

1. Let \(N=\{1,2,3,4\}\) be the set of players and \(v(N)=2\), \(v(\{1,2,3\})=v(\{1,2,4\})=v(\{1,3,4\})=v(\{2,3,4\})=1\), \(v(\{1,3\})=v(\{1,4\})=v(\{2,3\})=1\) and \(v(S)=0\), otherwise. Notice that the core of this game is non-emtpy. The payoff vector \(x=(\frac{1}{2},1\frac{1}{2},0,0)\in {\mathcal {MB}}^{*}(N,v)\), but \(x\not \in {\mathcal {Z}}^{*}(N,v)\). Moreover, the payoff vector \(x'=(\frac{1}{2},1,\frac{1}{4},\frac{1}{4})\in {\mathcal {Z}}^{*}(N,v)\), but \(x'\not \in C(N,v)\). With respect to the steady bargaining set notice \(x'=(\frac{1}{2},1,\frac{1}{4},\frac{1}{4})\in {\mathcal {SB}}(N,v)\), but \(x'\not \in C(N,v)\). The Example 2 (with \(a=1\)) in Shimomura (1997) provides an example of a superadditive game where the steady bargaining set is strictly included in the Zhou bargaining set.

2. These authors prove that particular payoff vectors constructed based upon orderings of players \(\theta =(i_1,i_2,\ldots ,i_n)\) (the reduced marginal worth vector \(rm^{\theta }(v)\)) are the extreme core elements of an almost convex balanced game. In particular, if \(\theta =(1,2,\ldots ,n)\), we have \(rm^{\theta }_{1}(v)=v(N)-v(N{\setminus } \{1\})\) and \(rm^{\theta }_{2}(v)=\min \{v(N{\setminus } \{1\})-v(N{\setminus } \{1,2\}),\,v(N)-v(N{\setminus } \{2\})\}=v(N)-v(N{\setminus } \{2\})\), where the last equality follows from (5).

3. An aspiration of a game (N, v) is a vector \(x'\in {\mathbb {R}}^N\) satisfying all cores inequalities, i.e. \(x'(S)\ge v(S)\), for all \(S\subseteq N\).

4. A game has a large core if any aspiration \(x'\) of the game can be represented by a core allocation x, i.e. there exists \(x\in C(N,v)\,:\, x_i\le x'_i\), for all \(i\in N\).

5. We are using the fact that for any \(\delta \in \mathcal {PK}(N{\setminus } I^{\theta ^{*}},\omega )\) and for any \(i\in N{\setminus } I^{\theta ^{*}}\),

   $$\begin{aligned} \min _{R\subseteq N{\setminus } I^{\theta ^{*}}: i\in R}\{\omega (R)-\omega (R{\setminus } \{i\})\}\le \delta _i\le \max _{R\subseteq N{\setminus } I^{\theta ^{*}}: i\in R}\{\omega (R)-\omega (R{\setminus } \{i\})\}. \end{aligned}$$

6. The symbol \(\varsubsetneq \) between two coalitions \(S\varsubsetneq T\) means \(S\subseteq T\) and \(S\ne T\).

7. Notice that the set Y is a non-empty box since it can be rewritten as

   $$\begin{aligned} Y=\{\alpha \in \mathbb {R}^{N{\setminus } T^{*}}\mid \,0\le \alpha _i\le |J^{\theta ^{*}}|\cdot \varepsilon _3, \text{ for } \text{ all } \;i\in N{\setminus } T^{*}, \text{ and } \alpha (N{\setminus } T^{*})=|J^{\theta ^{*}}|\cdot \varepsilon _3\}. \end{aligned}$$

   .

Authors and Affiliations

1. Facultat d’Economia i Empresa, Universitat de Barcelona, Av. Diagonal 690, Barcelona, Spain

   Josep Maria Izquierdo & Carles Rafels

Corresponding author

Correspondence to Josep Maria Izquierdo.

The authors acknowledge the support from research grants ECO2014-52340-P (Ministerio de Economía y Competitividad) and 2014SGR40 (Generalitat de Catalunya).

Appendix

Proof of Claim 1

Let us recall that the claim is under the hypothesis \(C(N,v)={\mathcal {SB}}(N,v)\). Next, assume \(|{\mathcal {S}}^{\theta ^{*}}_{min}(v)|=1\), say \({\mathcal {S}}^{\theta ^{*}}_{min}(v)=\{S^{*}\}\), where \(\theta ^{*}=(i_1,i_2,\ldots ,i_n)\). Then, we shall prove that there exists \(x\in {\mathcal {SB}}(N,v)\) but \(x\not \in C(N,v)\), which contradicts the hypothesis of the coincidence of the core and the steady bargaining set. Along the proof of this claim we will analyze and prove several subclaims.

SubClaim 1.1

The coalition \(S^{*}\) is included in \(T^{*}=\{i_1,\ldots ,i_{t^{*}}\}\).

Proof

Let us suppose that there exists \(i_{t'}\in S^{*}\) with \(t'\in \{t^{*}+1, t^{*}+2,\ldots ,n\}\). Then, define the vector \(x\in \mathbb {R}^N\) as \(x_{i_{t^{*}}}=\ell ^{\theta ^{*}}_{i_{t^{*}}}(v)-\varepsilon _2\), \(x_{i_{t'}}=\ell ^{\theta ^{*}}_{i_{t'}}(v)+\varepsilon _2\) and \(x_{i_k}=\ell ^{\theta ^{*}}_{i_k}(v)\), else, where

By (11), the parameter \(\varepsilon _2\) is well-defined. To end the proof, we show that \(x\in C(N,v)\) contradicting \(\ell ^{\theta ^{*}}(v)\) to be the lexmin core vector of v relative to \(\theta ^{*}\). To see this point, it is straightforward that \(x(N)=v(N)\). Moreover, if \(M\subseteq N\), \(M\ne N\), and \(i_{t^{*}}\not \in M\) then \(x(M)\ge \ell ^{\theta ^{*}}(v)(M)\ge v(M)\). If \(i_{t^{*}}\in M\) and \(\ell ^{\theta ^{*}}(v)(M)>v(M)\), then \(x(M)\ge \ell ^{\theta ^{*}}(v)(M)-\varepsilon _2> \ell ^{\theta ^{*}}(v)(M)- (\ell ^{\theta ^{*}}(v)(M)- v(M))=v(M)\). Finally, if \(i_{t^{*}}\in M\) and \(\ell ^{\theta ^{*}}(v)(M) =v(M)\) then \(M\in {\mathcal {S}}^{\theta }(v)\), and \(S^{*}\subseteq M\) since there is a unique minimal coalition in \({\mathcal {S}}^{\theta ^{*}}(v)\). Thus \(i_{t'}\in M\). Hence, \(x(M)=\ell ^{\theta ^{*}}(v)(M)\ge v(M)\) and \(x\in C(N,v)\), ending the proof of this subclaim. \(\square \)

SubClaim 1.2

The number of players in \(T^{*}=\{i_1,\ldots ,i_{t^{*}}\}\) is at least three, i.e. \(t^{*}\ge 3\).

Proof

It is clear that if \(t^{*}=1\) then \(T^{*}=\{i_1\}\) and the unique minimal coalition in \({\mathcal {S}}^{\theta ^{*}}(v)\) must be \(S^{*}=\{i_1\}\). Then, by (9), \(\ell ^{\theta ^{*}}_{i_1}(v)>m^{\theta ^{*}}_{i_1}(v)=v(\{i_1\})\) which contradicts \(S^{*}\in {\mathcal {S}}^{\theta ^{*}}(v)\). Moreover if \(t^{*}=2\) then \(T^{*}=\{i_1,i_2\}\), \(\ell ^{\theta ^{*}}_{i_1}(v)=m^{\theta ^{*}}_{i_1}(v)=v(\{i_1\})\) by (8), and \(\ell ^{\theta ^{*}}_{i_2}(v)>m^{\theta ^{*}}_{i_2}(v)=v(\{i_1,i_2\})-v(\{i_1\})\ge v(\{i_2\})\), where the last inequality comes from zero-monotonicity. From this we deduce \(\ell ^{\theta ^{*}}_{i_1}(v)+\ell ^{\theta ^{*}}_{i_2}(v)>v(\{i_1,i_2\})\), which contradicts the fact that the unique minimal coalition in \({\mathcal {S}}^{\theta ^{*}}(v)\) must be a subset of \(T^{*}\) (see Subclaim 1.1.). \(\square \)

Let us recall (see (10)) that any subgame \((R,v_R)\), with \(R\subseteq T^{*}\), \(R\ne T^{*}\), is a convex game. Therefore, the maximal marginal contribution of player \(i_{t^{*}}\in N\) to any subcoalition^{Footnote 6} \(Q\varsubsetneq T^{*}{\setminus } \{i_{t^{*}}\}\) is attained at a coalition containing \(t^{*}-2\) players; that is, without loss of generality

SubClaim 1.3

\(\ell ^{\theta ^{*}}_{i_{t^{*}}}(v)=v(\{i_1,i_2,\ldots ,i_{t^{*}-2},i_{t^{*}}\})-v(\{i_1,i_2,\ldots ,i_{t^{*}-2}\})\).

Proof

First, by (8), if \(\ell ^{\theta ^{*}}_{i_{t^{*}}}(v)<v(\{i_1,i_2,\ldots ,i_{t^{*}-2},i_{t^{*}}\})-v(\{i_1,i_2,\ldots ,i_{t^{*}-2}\})\) \(=v(\{i_1,i_2,\ldots ,i_{t^{*}-2},i_{t^{*}}\})-\ell ^{\theta ^{*}}(v)(\{i_1,i_2,\ldots ,i_{t^{*}-2}\})\), then

which contradicts \(\ell ^{\theta ^{*}}(v)\in C(N,v)\).

On the other hand, if \(\ell ^{\theta ^{*}}_{i_{t^{*}}}(v)>v(\{i_1,i_2,\ldots ,i_{t^{*}-2},i_{t^{*}}\})-v(\{i_1,i_2,\ldots ,i_{t^{*}-2}\})\), then, since \(\ell ^{\theta ^{*}}(v)\in C(N,v)\),

Thus, \(\ell ^{\theta ^{*}}(v)(Q\cup \{i_{t^{*}}\})>v(Q\cup \{i_{t^{*}}\})\), for all \(Q\varsubsetneq \{i_1,i_2,\ldots ,i_{t^{*}-1}\}\). However adding this result to ( 11) we reach a contradiction with Subclaim 1.1. \(\square \)

Next, let us define

Notice that, by (8) (i), \(\ell ^{\theta ^{*}}(v)(T^{*}{\setminus } \{i_{t^{*}}\})=m^{\theta ^{*}}(v)(T^{*}{\setminus } \{i_{t^{*}}\})=v(T^{*}{\setminus } \{i_{t^{*}}\})\) and so \(i_{t^{*}}\in J^{\theta ^{*}}\). Furthermore, by Subclaim 1.3 it follows that \(i_{t^{*}-1}\in J^{\theta ^{*}}\) and thus \(\{i_{t^{*}-1}, i_{t^{*}}\}\subseteq J^{\theta ^{*}}\). Therefore,

Finally, by zero-monotonicity of the game v, it holds

To check this last point, notice that, by zero-monotonicity of v, if \(\ell ^{\theta ^{*}}_i(v)=v(\{i\})\) then \(\ell ^{\theta ^{*}}(v)(T^{*})=\ell ^{\theta ^{*}}_i(v)+\ell ^{\theta ^{*}}(v)(T^{*}{\setminus } \{i\})=v(\{i\})+v(T^{*}{\setminus } \{i\})\le v(T^{*})\) which contradicts (11). Next, let us prove the following subclaim.

SubClaim 1.4

For all \(S \subseteq T^{*}\) such that \(\ell ^{\theta ^{*}}(v)(S)=v(S)\), then \(J^{\theta ^{*}}{\setminus } S\ne \varnothing \).

Proof

Since \(i_{t^{*}}\in J^{\theta ^{*}}\), the result is trivial if \(i_{t^{*}}\not \in S\). If \(i_{t^{*}}\in S\), let

such that \(i_{{\kappa }}\not \in S\) and \(i_{{ \kappa }}+1,i_{{\kappa }}+2,\ldots , i_{t^{*}}\in S\). Notice that the index

is well-defined since, by (11), we have

. We next prove that

. To see this, first notice that

Notice that

and thus we describe

, where

. Moreover, and for all

, let us denote by

the set of predecessors of player \(i_{r_j}\) relative to the ordering

Then, we have

where the first inequality follows from (2), the convexity of the subgame \((T^{*}{\setminus } \{i_{\kappa }\},v_{T^{*}{\setminus } \{i_{\kappa }\}})\) and the fact that, for all \(j=1,\ldots ,m-1\), we have

the second inequality follows from the convexity of the subgame \((T^{*}{\setminus } \{i_{\kappa }\},v_{T^{*}{\setminus } \{i_{\kappa }\}})\), and the third one by taking in (3) \(M=P^{\theta ^{*}}_{i_{r_{m}}}\cup \{i_{t^{*}}\}\cup \{i_{r_m}\}\) and \(M'=T^{*}{\setminus } \{i_{r_1},i_{r_{2}},\ldots , i_{r_{m}}, i_{\kappa }\}\). Therefore, we obtain that \(m^{\theta ^{*}}(v)(T^{*}{\setminus } (S\cup \{i_{{\kappa }}\}))\le v(T^{*}{\setminus } \{i_{\kappa }\})-v(S)\). Using this inequality in (24) we obtain

Therefore, we conclude that \(v(T^{*}{\setminus } \{i_{{\kappa }}\})= \ell ^{\theta ^{*}}(v)(T^{*}{\setminus } \{i_{{ \kappa }}\})\) which implies \(i_{\kappa } \in J^{\theta ^{*}}{\setminus } S\), as we want to prove. \(\square \)

Once we have proved the above subclaims, let us define the vector \(\beta \in \mathbb {R}^N\) as

where

By (23),

Hence, define the game \((N{\setminus } T^{*},\omega )\) as follows:

Let us remark that \(\omega (R)\le |J^{\theta ^{*}}|\cdot \varepsilon _3\), for any \(\varnothing \ne R\subseteq N{\setminus } T^{*}\). To check it, simply notice that \(\omega (R)=v(R\cup Q^{*})-\beta (R\cup Q^{*})\) for some \(Q^{*}\subseteq T^{*}\), and thus \(\omega (R)=v(R\cup Q^{*})-\beta (R\cup Q^{*})=v(R\cup Q^{*})-\ell ^{\theta ^{*}}(R\cup Q^{*})+|Q^{*}\cap J^{\theta ^{*}}|\cdot \varepsilon _3\le |Q^{*}\cap J^{\theta ^{*}}|\cdot \varepsilon _3\le |J^{\theta ^{*}}|\cdot \varepsilon _3\). Moreover, for the case \(R=N{\setminus } T^{*}\) we have \(\omega (N{\setminus } T^{*})=|J^{\theta ^{*}}|\cdot \varepsilon _3\), just by taking \(Q=T^{*}\) in its definition.

Next, define the subset Y of vectors in \(\mathbb {R}^{N{\setminus } T^{*}}\) as follows:

Notice that Y is a non-empty and compact subset of the preimputation set \(I^{*}(N{\setminus } T^{*},\omega )\), and thus, by Schmeidler (1969), the kernel^{Footnote 7} of the game \((N{\setminus } T^{*},\omega )\) relative to Y is non-empty, i.e. \(\mathcal {K}(N{\setminus } T^{*}, \omega , Y)\ne \varnothing \).

Hence, select an element \(\delta \) in the kernel of the game \((N{\setminus } T^{*}, \omega )\) relative to Y, i.e. \(\delta \in \mathcal {K}(N{\setminus } T^{*},\omega , Y)\), and define the vector \(x\in \mathbb {R}^N\) as follows:

The vector x is an imputation of the game (N, v): clearly, x is efficient, \(x(N)=v(N)\); moreover, by definition of \(\varepsilon _3\) and (23), we have \(x_i=\ell ^{\theta ^{*}}_i(v)-\varepsilon _3 \ge v(\{i\})\), for all \(i\in J^{\theta ^{*}}\), \(x_i=\ell ^{\theta ^{*}}_i(v)\ge v(\{i\})\), for all \(i\in T^{*}{\setminus } J^{\theta ^{*}}\) and, since \(\delta _i\ge 0\), \(x_i=\beta _i+\delta _i=\ell ^{\theta ^{*}}_i(v)+\delta _i\ge v(\{i\})\), for all \(i\in N{\setminus } T^{*}\).

However, it is not in the core of the game (N, v) since \(x(T^{*}{\setminus } \{i_{t^{*}}\})=\ell ^{\theta ^{*}}(v)(T^{*}{\setminus } \{i_{t^{*}}\})-(|J^{\theta ^{*}}|-1)\varepsilon _3 = v(T^{*}{\setminus } \{i_{t^{*}}\})-(|J^{\theta ^{*}}|-1)\varepsilon _3 < v(T^{*}{\setminus } \{i_{t^{*}}\})\). We finally check that x is in the steady bargaining set of the game (N, v). To this aim take \(S\subseteq N\) such that \(v(S)-x(S)>0\). Notice that, since \(x\in I(N,v)\), then \(|S|\ge 2\). Furthermore, it holds that

since otherwise \(S\cap J^{\theta ^{*}}= \varnothing \) and we would have

reaching a contradiction with \(v(S)-x(S)>0\). Next, we shall prove there exists \(M\subseteq N\) such that \(M{\setminus } S\ne \varnothing \), \(S{\setminus } M\ne \varnothing \), \(S\cap M\ne \varnothing \) and \(v(M)-x(M)\ge v(S)-x(S)\). We distinguish two cases.

A: :

\(S \subseteq T^{*}=\{i_1,\ldots ,i_{t^{*}}\}\). By the way we have defined \(\varepsilon _3\), and being \(S\subseteq T^{*}\), let us first see that \(\ell ^{\theta ^{*}}(v)(S)=v(S)\). To check it, let us suppose that \(\ell ^{\theta ^{*}}(v)(S)>v(S)\), then \(v(S)-x(S)=v(S)-\ell ^{\theta ^{*}}(v)(S)+|S\cap J^{\theta ^{*}}|\cdot \varepsilon _3\le v(S)-\ell ^{\theta ^{*}}(v)(S)+n\cdot \varepsilon _3< 0\), which contradicts the hypothesis \(v(S)-x(S)>0\). Moreover, by (26), \(S\cap J^{\theta ^{*}}\ne \varnothing \), and, by Subclaim 1.4, \(J^{\theta ^{*}}{\setminus } S\ne \varnothing \). Let \(j\in J^{\theta ^{*}}{\setminus } S\) and \(i\in J^{\theta ^{*}}\cap S\) and take \(M=T^{*}{\setminus } \{i\}\). Notice that \(j\in M{\setminus } S\), \(i\in S{\setminus } M\) and, since \(|S|\ge 2\), \(M\cap S\ne \varnothing \). Furthermore, since \(i\in J^{\theta ^{*}}\) we have \(\ell ^{\theta ^{*}}(v)(M)=v(M)\), and thus

$$\begin{aligned} v(M)-x(M)= & {} v(M)-\ell ^{\theta ^{*}}(v)(M)+(|J^{\theta ^{*}}|-1)\cdot \varepsilon _3\\= & {} v(S)-\ell ^{\theta ^{*}}(v)(S)+(|J^{\theta ^{*}}|-1)\cdot \varepsilon _3 \ge v(S)-x(S), \end{aligned}$$

where the inequality follows since \(j \in J^{\theta ^{*}}{\setminus } S\).

B: :

\(S\cap (N{\setminus } T^{*})\ne \varnothing \). First let us remark that \(S\cap (N{\setminus } T^{*})\ne N{\setminus } T^{*}\), or equivalently \(N{\setminus } (T^{*}\cup S)\ne \varnothing \); this holds since, otherwise, \(S\cap (N{\setminus } T^{*})=N{\setminus } T^{*}\) and

$$\begin{aligned} v(S)-x(S)&=v(S)-\beta (S)-\delta (N{\setminus } T^{*})= v(S)-\beta (S)-\omega (N{\setminus } T^{*})\nonumber \\&=v(S)-\beta (S)-|J^{\theta ^{*}}|\cdot \varepsilon _3\nonumber \\&= v(S)-\ell ^{\theta ^{*}}(v)(S)+|S\cap J^{\theta ^{*}}|\cdot \varepsilon _3-|J^{\theta ^{*}}|\cdot \varepsilon _3\le 0, \end{aligned}$$

(27)

reaching a contradiction.

Hence, let \(i\in S\cap (N{\setminus } T^{*})\) and select \(j\in (N{\setminus } T^{*}){\setminus } S=N{\setminus } (T^{*}\cup S)\) such that

Let us prove that such a player j exists. To check it, suppose that, given an arbitrary \(k\in (N{\setminus } T^{*}){\setminus } S\), we would have \(s^{\omega }_{ki}(\delta )< s^{\omega }_{ik}(\delta )\). Since \(\delta \in \mathcal {K}(N{\setminus } T^{*},\omega ,Y)\) then we would have that either \(\delta _k=0\) or \(\delta _i=|J^{\theta ^{*}}|\cdot \varepsilon _3\). However, \(\delta _i=|J^{\theta ^{*}}|\cdot \varepsilon _3\) is not possible since, by a similar reasoning as in (27), we would reach a contradiction with \(v(S)-x(S)>0\). Therefore, we obtain that \(\delta _k=0\). Since k was chosen arbitrarily, we would conclude that \(\delta _k=0\) for all \(k\in (N{\setminus } T^{*}){\setminus } S\) and thus

But then,

getting a contradiction with \(v(S)-x(S)>0\).

Now, by definition and taking agents i and j as in (28), we have

for some \(R^{*}\subseteq N{\setminus } T^{*}\), with \(j\in R^{*}\) but \(i\not \in R^{*}\), and some \(Q^{*}\subseteq T^{*}\). Hence, by (28), it follows that

Notice that \(i\in S{\setminus } (R^{*}\cup Q^{*})\) and \(j\in (R^{*}\cup Q^{*}){\setminus } S\). Furthermore, if \(S\cap (R^{*} \cup Q^{*})\ne \varnothing \), then take \(M=R^{*}\cup Q^{*}\) and we are done. Otherwise, in case \(S\cap (R^{*}\cup Q^{*})=\varnothing \) we have, by (26), \((R^{*}\cup Q^{*})\cap J^{\theta ^{*}}\ne \varnothing \).

Hence, since we are supposing \(S\cap (R^{*}\cup Q^{*})=\varnothing \), \((R^{*}\cup Q^{*})\cap J^{\theta ^{*}}\ne \varnothing \) and \(S\cap J^{\theta ^{*}}\ne \varnothing \) (see (26)), we conclude that

Therefore,

Hence, it easily follows that

for all \(k\in J^{\theta ^{*}}\). Finally, by (26) and the fact that \(J^{\theta ^{*}}\subseteq T^{*}\), we have \(S\cap T^{*}\ne \varnothing \). At this point we distinguish two cases:

• B.1 If \(|S\cap T^{*}|=1\), i.e. \(S\cap T^{*}=\{i'\}\), then take \(M=T^{*}{\setminus } \{k\}\) where \(k\in J^{\theta ^{*}}{\setminus } S\) (such a player exists since \(|J^{\theta ^{*}}|\ge 2\), see (22)). In this subcase, \(i'\in M\cap S\), \(M{\setminus } S\ne \varnothing \), since by Subclaim 1.2, \(t^{*}\ge 3\), and \(S{\setminus } M\ne \varnothing \), by the hypothesis of case B.

• B.2 If \(|S\cap T^{*}|\ge 2\), then take \(M=T^{*}{\setminus } \{k\}\) where \(k\in J^{\theta ^{*}}\cap S\) (such a player exists by (26)). In this subcase, \( M\cap S\ne \varnothing \) since \(|S\cap T^{*}|\ge 2\) , \(M{\setminus } S\ne \varnothing \) since, by (30), \(S\cap J^{\theta ^{*}}\varsubsetneq J^{\theta ^{*}}\), and \(S{\setminus } M\ne \varnothing \), by the hypothesis of case B.

In both cases B.1 and B.2, \(M=T^{*}{\setminus } \{k\}\), for some \(k\in J^{\theta ^{*}}\). Thus, by (31), we are done.

From both cases A and B, we have shown that \(x\not \in C(N,v)\), but \(x \in {\mathcal {SB}}(N,v)\), getting a contradiction with the hypothesis \(C(N,v)={\mathcal {SB}}(N,v)\). \(\square \)

Reprints and permissions