Consistency and the core in games with externalities

Abstract

In the presence of externalities across coalitions, Dutta et al. (J Econ Theory 145:2380–2411, 2010) characterize their value by extending Hart and Mas-Colell reduced game consistency. In the present paper, we provide a characterization result for the core for games with externalities by extending one form of consistency studied by Moulin (J Econ Theory 36:120–148, 1985), which is often referred to as the complement-reduced game property. Moreover, we analyze another consistency formulated by Davis and Maschler (Naval Res Logist Quart 12:223–259, 1965), called the max-reduced game property and a final consistency called the projection-reduced game property. In environments with externalities, we discuss some asymmetric results among these different forms of reduced games.

Appendix

To distinguish each form of reduced game, in this appendix, we use symbols $v^{S,\mathcal {P},x}_{m1}$, $v^{S,\mathcal {P},x}_{m2}$, $v^{S,\mathcal {P},x}_{p}$ and $v^{S,x}_{c}$ to denote max(I), max(II), projection and complement-type of reduced game, respectively. Tables 3 and 4 correspond to Tables 1 and 2, respectively. The number assigned to each cell represents the proposition or example describing the cell, e.g., for the proposition showing that the optimistic core satisfies Max-I RGP, see Proposition 5.

Table 3 The relationship between expectation cores and RGP (corresponding to Table 1)

Table 4 The relationship between expectation functions and consistency (corresponding to Table 2)

Proposition 3

If $\psi$ is optimistic or pessimistic, then $\psi$ is CC.

Proof

We denote by $\psi ^{opt}$ the optimistic expectation function. Let (N, v) be a game, and $S\subseteq N$ ($|S|\ge 2$). We define $\mathcal {P}^*$ as follows:

$$\begin{aligned} \mathcal {P}^*:= \psi ^{opt}(N,v,S)=\mathop {\mathrm{arg~max}}\limits _{\mathcal {P'} \in \varPi (N{\setminus } S)} v(S,\mathcal {P'}). \end{aligned}$$

(9)

For any $h\in S$ and $x\in \mathbb {R}^N$, we have

$$\begin{aligned} v^{N{\setminus } h,x}_{c}(S{\setminus } h,\mathcal {P}^*)= & {} v(S,\mathcal {P}^*)-x_h\\= & {} \max _{\mathcal {P'} \in \varPi (N{\setminus } S)}[v(S,\mathcal {P'})-x_h]\\= & {} \max _{\mathcal {P'} \in \varPi (N{\setminus } S)}[v^{N{\setminus } h,x}_{c}(S{\setminus } h,\mathcal {P'})], \end{aligned}$$

where the first equality holds by the definition of complement reduced games, the second by (9) and the last by the definition of complement reduced games. Hence, we obtain

$$\begin{aligned} \mathcal {P}^*=\mathop {\mathrm{arg~max}}\limits _{\mathcal {P'} \in \varPi (N{\setminus } S)} v^{N{\setminus } h,x}_{c}(S{\setminus } h,\mathcal {P'}) = \psi ^{opt}(N{\setminus } h,v^{N{\setminus } h,x}_{c},S{\setminus } h), \end{aligned}$$

and, then, $\psi ^{opt}(N,v,S)=\psi ^{opt}(N{\setminus } h,v^{N{\setminus } h,x}_{c},S{\setminus } h)$, which implies $\psi ^{opt}$ is CC.

By replacing $\max$ with $\min$, we complete the proof of the pessimistic expectation function $\psi ^{pes}$ as well. $\square$

Proposition 4

If $\psi$ satisfies the following condition: for any games (N, v), (M, w), and nonempty coalitions $S\subseteq N$, $T\subseteq M$,

$$\begin{aligned} N{\setminus } S = M{\setminus } T \Longrightarrow \psi (N,v,S) = \psi (M,w,T), \end{aligned}$$

(10)

then $\psi$ satisfies all four types of consistencies: Max-I, Max-II, Projection and Complement.

Proof

We prove CC (or, complement consistency). The other types of consistencies are obtained in the same way. Fix a game (N, v). For any $x\in \mathbb {R}^N$ and $h\in N$, we can specify the complement reduced game $(N{\setminus } h,v^{N{\setminus } h,x}_{c})$. For any S such that $h\in S \subseteq N$, we have

$$\begin{aligned} N{\setminus } S = (N{\setminus } h){\setminus }(S{\setminus } h). \end{aligned}$$

Using (10), we obtain $\psi (N,v,S) = \psi (N{\setminus } h,v^{N{\setminus } h,x}_{c},S{\setminus } h,)$ $\square$

Lemma 4

If $\psi$ is the singleton-expectation, then $\psi$ satisfies (10).

Proof

We denote by $\psi ^{s}$ the singleton-expectation function. For any nonempty T and S with $T\in S\subseteq N$, and any $w:EC(N{\setminus } T)\rightarrow \mathbb {R}$, we have $\psi ^{s}(N,v,S)=\{\{i\}|i \in N{\setminus } S\}=\psi ^{s}(N{\setminus } T,w,S{\setminus } T)$. $\square$

Lemma 5

If $\psi$ is the merge-expectation, then $\psi$ satisfies (10).

Proof

This is similar to Lemma 4. Let $\psi ^{m}$ denote the merge-expectation function. We have $\psi ^{m}(N,v,S)=\{N{\setminus } S\}=\psi ^{m}(N{\setminus } T,w,S{\setminus } T)$. $\square$

Corollary 2

If $\psi$ is the singleton-expectation or the merge-expectation, then $\psi$ satisfies all four types of consistencies.

Proof

See Lemmas 4, 5 and Proposition 4. $\square$

Example 3

Consider the following 4-player game: $N=\{i_1,i_2,i_3,i_4\}$;

$$\begin{aligned}&v(N,\{\emptyset \})=12;\\&v(\{i,j,k\}, \left\{ \{h\}\right\} )=5\ and\ v(\{h\}, \left\{ \{i,j,k\}\right\} )=0,\ \ for\ \{i,j,k,h\}=N;\\&v(\{i,j\}, \left\{ \{k,h\}\right\} )=4,\ \ for\ \{i,j,k,h\}=N;\\&v(\{i,j\}, \left\{ \{k\},\{h\}\right\} )=3\ and\ v(\{k\}, \left\{ \{i,j\},\{h\}\right\} )=1,\ \ for\ \{i,j,k,h\}=N;\\&v(\{i\}, \left\{ \{j\},\{k\},\{h\}\right\} )=2,\ \ for\ \{i,j,k,h\}=N. \end{aligned}$$

Let $x=(3,3,3,3)$, $S=\{i_1,i_2\}$ and player $h=1$. For the optimistic expectation function, we have

$$\begin{aligned} \mathop {\mathrm{arg~max}}\limits _{\mathcal {P}'\in \varPi (N{\setminus } S)}v(S,\mathcal {P}')= \{\{i_3,i_4\}\}, \end{aligned}$$

because $\max _{\mathcal {P}'\in \varPi (N{\setminus } S)}v(S,\mathcal {P}')\!\!=\!\max \{v(S, \{\{i_3,i_4\}\}), v(S,\{\{i_3\},\{i_4\}\})\}\!=\!\!\max \{4, 3 \}$. However, in the Max-I reduced game, we have

$$\begin{aligned} \mathop {\mathrm{arg~max}}\limits _{\mathcal {P}'\in \varPi (N{\setminus } S)}v^{-h}_{m1}(S{\setminus } h,\mathcal {P}')= \{\{i_3\},\{i_4\}\}, \end{aligned}$$

because

$$\begin{aligned} \max _{\mathcal {P}'\in \varPi (N{\setminus } S)}v^{-h}_{m1}(S{\setminus } h,\mathcal {P}')= & {} \max \left\{ \begin{array}{ll} v(S, \{\{i_3,i_4\}\})-x_h,&{} v(S{\setminus } h, \{\{i_1\},\{i_3,i_4\}\}),\\ v(S,\{\{i_3\},\{i_4\}\})-x_h,&{} v(S{\setminus } h, \{\{i_1\},\{i_3\},\{i_4\}\}) \end{array} \right\} \nonumber \\= & {} \max \{4-3 ,1, 3-3, 2\}\nonumber \\= & {} 2, \end{aligned}$$

(11)

which is the worth of the bottom-right element in (11). Hence, $\psi ^{opt}(N,v,S)=\{\{i_3,i_4\}\} \ne \{\{i_3\},\{i_4\}\}=\psi ^{opt}(N{\setminus } h,v^{-h}_{m1},S{\setminus } h)$. For the optimistic expectation function, this example is still valid for Max-II and Projection consistencies as well. For the pessimistic expectation function, we can generate the example by swapping $v(\{i,j\}, \left\{ \{i,j\},\{k,h\}\right\} )$ for $v(\{i,j\}, \left\{ \{i,j\},\{k\},\{h\}\right\} )$.

Lemma 6

Let $(N,v)\in \varGamma$. Let $S\subseteq N$, $\mathcal {P}\in \varPi (N{\setminus } S)$ and $x\in \mathbb {R}^N$. We denote each type of reduced game by $v^{S,\mathcal {P},x}_{m1}$, $v^{S,\mathcal {P},x}_{m2}$, $v^{S,\mathcal {P},x}_{p}$ and $v^{S,x}_{c}$, respectively. Then, for any $T\subseteq S$ $(T\ne \emptyset )$ and $\mathcal {Q}\in \varPi (S{\setminus } T)$, we have

$$\begin{aligned}&v^{S,\mathcal {P},x}_{m1}(T,\mathcal {Q})\ge v^{S,\mathcal {P},x}_{m2}(T,\mathcal {Q}),\\&v^{S,\mathcal {P},x}_{m2}(T,\mathcal {Q})\ge v^{S,\mathcal {P},x}_{p}(T,\mathcal {Q}),\\&v^{S,\mathcal {P},x}_{m2}(T,\mathcal {Q})\ge v^{S,x}_{c}(T,\mathcal {Q}). \end{aligned}$$

Proof

The first inequality follows from the domain of maximization: in view of the definitions, for any $\mathcal {P}\in \varPi (N{\setminus } S)$,

$$\begin{aligned} \{C|C\in \mathcal {P}\} \text { (or, Max-II) } \subseteq \{C|C\subseteq N{\setminus } S\} \text { (or, Max-I) }. \end{aligned}$$

The second (third) inequality holds because we can take $\emptyset$ ($N{\setminus } S$) as maximizer C. $\square$

Proposition 5

The optimistic-core satisfies all types of RGP on $\varGamma _{C^{opt}}$: maxI-RGP, maxII-RGP, projection-RGP and comp-RGP.

Proof

Let $C^{opt}(N,v)$ be the optimistic core of (N, v) and $x\in C^{opt}(N,v)$. We show that the optimistic-core satisfies maxI-RGP. For any $S\subseteq N$, $T\subsetneq S$ $(T\ne \emptyset )$ and $\mathcal {P}\in \varPi (N{\setminus } S)$, we have

$$\begin{aligned}&\sum _{j\in T}x_j - \max _{\mathcal {Q}\in \varPi (S{\setminus } T)} v^{S,\mathcal {P},x}_{m1}(T,\mathcal {Q}) \nonumber \\&\quad =\sum _{j\in T}x_j - \max _{\mathcal {Q}\in \varPi (S{\setminus } T)} \max _{C\subseteq N{\setminus } S}\left[ v(T\cup C, \mathcal {Q} \cup (\mathcal {P}|_{(N{\setminus } S){\setminus } C})) - \sum _{j\in C}x_j \right] \nonumber \\&\quad =\sum _{j\in T}x_j - \left[ v(T\cup C^*, \mathcal {Q}^* \cup (\mathcal {P}|_{(N{\setminus } S){\setminus } C^*})) - \sum _{j\in C^*}x_j\right] \end{aligned}$$

(12)

$$\begin{aligned}&\quad =\sum _{j\in T\cup C^*}x_j - v(T\cup C^*, \mathcal {Q}^* \cup (\mathcal {P}|_{(N{\setminus } S){\setminus } C^*})) \nonumber \\&\quad \ge \max _{\mathcal {P'}\in \varPi (N{\setminus } (T\cup C^*))} \ v(T\cup C^*,\mathcal {P'})- v(T\cup C^*, \mathcal {Q}^* \cup (\mathcal {P}|_{(N{\setminus } S){\setminus } C^*})) \nonumber \\&\quad \ge 0, \end{aligned}$$

(13)

where $C^*,\mathcal {Q}^*$ in (12) are maximizers of the target formula, and (13) holds because $x\in C^{opt}(N,v)$. Similarly, for $T=S$, we have

$$\begin{aligned} \sum _{j\in S}x_j-v^{S,\mathcal {P},x}(S,\{\emptyset \})= & {} \sum _{j\in S}x_j-\left( v(N,\{\emptyset \})-\sum _{j\in N{\setminus } S}x_j \right) \\= & {} \sum _{j\in N}x_j-v(N,\{\emptyset \})\\= & {} 0. \end{aligned}$$

By Lemma 6, we can replace $v^{S,\mathcal {P},x}_{m1}$ with $v^{S,\mathcal {P},x}_{m2}$, $v^{S,\mathcal {P},x}_{p}$ and $v^{S,\mathcal {P},x}_{c}$, respectively. Then, we obtain the desired proposition. $\square$

Example 4

Consider the following 4-player game: $N=\{1,2,3,4\}$,

$$\begin{aligned} v(S,\mathcal {P})= \left\{ \begin{array}{ll} 12 &{} \text {if }(S,\mathcal {P})=(N,\{\emptyset \}),\\ 6 &{} \text {if }(S,\mathcal {P})=(\{i,j\},\{\{k\},\{h\}\}),\\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

Let $x=(x_1,x_2,x_3,x_4)=(1,3,4,4)$. Then, $x\in C^{pes}(N,v)=C^{m}(N,v)$. Now, for $S=\{1,2\}$ and $\mathcal {P}=\{\{3\},\{4\}\}$, we have the following Max-I reduced game:

$$\begin{aligned}&v^{S,P,x}_{m1}(\{1,2\},\{\emptyset \})= 12-(4+4)=4,\\&v^{S,P,x}_{m1}(\{1\},\{\{2\}\})= 6-4=2,\\&v^{S,P,x}_{m1}(\{2\},\{\{1\}\})= 6-4=2. \end{aligned}$$

The restriction of x, $x_S=(1,3)$, is out of the pessimistic core (and the m-core) of the reduced game: $x_S=(1,3)\not \in \{(2,2)\}=C^{pes}(S,v^{S,P,x}_{m1})=C^{m}(S,v^{S,P,x}_{m1})$. We have the Max-II reduced game as well as Max-I.

Example 5

Consider the following 5-player game: $N=\{1,2,3,4,5\}$,

$$\begin{aligned} v(S,\mathcal {P})= \left\{ \begin{array}{ll} 15 &{} \text {if }(S,\mathcal {P})=(N,\{\emptyset \}),\\ 7 &{} \text {if }(S,\mathcal {P})=(\{i,j\},\{\{k\},\{h,l\}\}),\\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

Let $x=(x_1,x_2,x_3,x_4,x_5)=(2,2,4,4,3)$. Then, $x\in C^{s}(N,v)$. For $S=\{3,4\}$ (who obtain 4 in x) and $\mathcal {P}=\{\{1\},\{2,5\}\}$, we have the following Max-I reduced game:

$$\begin{aligned}&v^{S,P,x}_{m1}(\{3,4\},\{\emptyset \})= 15-(2+2+3)=8,\\&v^{S,P,x}_{m1}(\{3\},\{\{4\}\})= 7-2=5,\\&v^{S,P,x}_{m1}(\{4\},\{\{3\}\})= 7-2=5. \end{aligned}$$

Hence, the s-core is empty. We have the same result in Max-II as well as Max-I.

Example 6

Consider the following 4-player game: $N=\{1,2,3,4\}$,

$$\begin{aligned} v(S,\mathcal {P})= \left\{ \begin{array}{ll} 12 &{} \text {if }(S,\mathcal {P})=(N,\{\emptyset \}),\\ 4 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j,k,h\}\}),\\ 4 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j,k\},\{h\}\}),\\ 3 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j\},\{k\},\{h\}\}),\\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

Let $x=(x_1,x_2,x_3,x_4)=(3,3,3,3)$. Then, $x\in C^{pes}(N,v)=C^{s}(N,v)$. For $S=\{1,2\}$ and $\mathcal {P}=\{\{3,4\}\}$, we have the following projection reduced game:

$$\begin{aligned}&v^{S,P,x}_{p}(\{1,2\},\{\emptyset \})= 12-(3+3)=6,\\&v^{S,P,x}_{p}(\{1\},\{\{2\}\})= 4,\\&v^{S,P,x}_{p}(\{2\},\{\{1\}\})=4. \end{aligned}$$

Hence, the pessimistic core and the s-core are empty in the reduced game.

Example 7

Consider the following 4-player game: $N=\{1,2,3,4\}$,

$$\begin{aligned} v(S,\mathcal {P})= \left\{ \begin{array}{ll} 12 &{} \text {if }(S,\mathcal {P})=(N,\{\emptyset \}),\\ 3 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j,k,h\}\}),\\ 4 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j,k\},\{h\}\}),\\ 4 &{} \text {if }(S,\mathcal {P})=(\{i\},\{\{j\},\{k\},\{h\}\}),\\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

Let $x=(x_1,x_2,x_3,x_4)=(3,3,3,3)$. Then, $x\in C^{m}(N,v)$. For $S=\{1,2\}$ and $\mathcal {P}=\{\{3,4\}\}$, we have the following projection reduced game:

$$\begin{aligned}&v^{S,P,x}_{p}(\{1,2\},\{\emptyset \})= 12-(3+3)=6,\\&v^{S,P,x}_{p}(\{1\},\{\{2\}\})= 4,\\&v^{S,P,x}_{p}(\{2\},\{\{1\}\})=4. \end{aligned}$$

Hence, the m-core of the reduced game becomes empty.