<p>Define the marginal contribution of <span class="math-container">$i \in N$</span> to any <span class="math-container">$C \subseteq N \setminus \{i\}$</span> by
<span class="math-container">\begin{align}
m_i(C) = v(C \cup \{i\}) - v(C). 
\end{align}</span></p>

<p>We are going to show C.1 <span class="math-container">$\Rightarrow$</span> C.2 <span class="math-container">$\Rightarrow$</span> C.3 <span class="math-container">$\Rightarrow$</span> C.1.
Note that C.1 <span class="math-container">$\Rightarrow$</span> C.2 is trivially true.
If C.1 holds for all <span class="math-container">$S,T \subseteq N$</span>, then C.2 must hold for all <span class="math-container">$S,T \subseteq N$</span> with the restriction <span class="math-container">$|S \setminus T| = |T \setminus S| = 1$</span>.
In order to show C.2 <span class="math-container">$\Rightarrow$</span> C.3 consider any <span class="math-container">$S \subseteq T \subseteq N \setminus \{i\}$</span>.
Let <span class="math-container">$T \setminus S = \{j_1, \ldots, j_k\}$</span> and define <span class="math-container">$S_\ell := T_{\ell-1} \cup \{i\}$</span> and <span class="math-container">$T_\ell := T_{\ell-1} \cup \{j_\ell\}$</span> for <span class="math-container">$\ell \in \{1,\ldots,k\}$</span> with <span class="math-container">$T_0 = S$</span>.
Note that 
<span class="math-container">\begin{align}
\begin{split}
T_{k-1} &amp;~= T_{k-2} \cup \{j_{k-1}\} \\
&amp;~= T_{k-3} \cup \{j_{k-2}\} \cup \{j_{k-1}\} = T_{k-3} \cup \{j_{k-2},j_{k-1}\}\\
&amp; ~ \vdots\\
&amp;~ =  T_0 \cup \{j_1,\ldots,j_{k-1}\}\\
&amp;~ = S \cup \{j_1,\ldots,j_{k-1}\}\\
&amp;~ = T \setminus \{j_k\}
\end{split}
\end{align}</span>
Since <span class="math-container">$|S_\ell \setminus T_\ell| = |T_\ell \setminus S_\ell| = 1$</span> we can apply C.2, i.e.
<span class="math-container">\begin{align}
\begin{split}
&amp;v(S_\ell \cup T_\ell) + v(S_\ell \cap T_\ell) \geq v(S_\ell) + v(T_\ell)\\
\Longleftrightarrow \quad &amp;v(T_{\ell-1} \cup\{i, j_\ell\}) + v(T_{\ell-1}) \geq v(T_{\ell-1} \cup \{i\}) + v(T_{\ell-1} \cup \{j_\ell\})\\
\Longleftrightarrow \quad &amp;v(T_{\ell-1} \cup\{i, j_\ell\}) - v(T_{\ell-1} \cup \{j_\ell\}) \geq v(T_{\ell-1} \cup \{i\}) - v(T_{\ell-1})\\
\Longleftrightarrow \quad &amp;m_i(T_{\ell-1} \cup\{j_\ell\}) \geq m_i(T_{\ell-1})\\
\Longleftrightarrow \quad &amp;\sum_{\ell=1}^k{m_i(T_{\ell-1} \cup\{j_\ell\})} \geq \sum_{\ell=1}^k{m_i(T_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &amp;\sum_{\ell=1}^{k-1}{m_i(T_{\ell-1} \cup\{j_\ell\})} + m_i(T_{k-1} \cup\{j_k\}) \geq m_i(T_0) + \sum_{\ell=2}^k{m_i(T_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &amp;\sum_{\tau=2}^{k}{m_i(T_{\tau-2} \cup\{j_{\tau-1}\})} + m_i((T \setminus \{j_k\}) \cup\{j_k\}) \geq m_i(S) + \sum_{\ell=2}^k{m_i(T_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &amp;\sum_{\tau=2}^{k}{m_i(T_{\tau-1})} + m_i(T) \geq m_i(S) + \sum_{\ell=2}^k{m_i(T_{\ell-1})}\\
\Longleftrightarrow \quad &amp; m_i(T) \geq m_i(S)
\end{split}
\label{eq:pvex}
\end{align}</span>
The bottom line corresponds to C.3.
The final step C.3 <span class="math-container">$\Rightarrow$</span> C.1 is provided in Moulin (1988, p. 113). </p>

CC BY-SA 4.0
2019-03-19T18:04:17.640Z
2019-03-19T18:04:17.640Z
clueless
<p>Let <span class="math-container">$N \subset \mathbb N$</span> denote the set of players and <span class="math-container">$v : 2^N \to \mathbb R$</span> , <span class="math-container">$v(\emptyset) = 0$</span>, the characteristic function.
We call <span class="math-container">$(N,v)$</span> a cooperative transferable utility (TU) <a href="https://en.wikipedia.org/wiki/Cooperative_game_theory" rel="nofollow noreferrer">game</a>.</p>

<p><strong>Definition 1.</strong> 
A game <span class="math-container">$(N,v)$</span> is called convex, if for all <span class="math-container">$S,T \subseteq N$</span> it holds that
<span class="math-container">\begin{align}
v(S \cup T) + v(S \cap T) \geq v(S) + v(T) \tag{C.1}.
\end{align}</span>
In <a href="https://www.sciencedirect.com/science/article/pii/S0899825607000164" rel="nofollow noreferrer">Hafalir (2007, p. 255)</a> it says that Def. (1) is equivalent to the following statement.</p>

<p><strong>Definition 2.</strong><br>
A game <span class="math-container">$(N,v)$</span> is called convex, if for all <span class="math-container">$S,T \subseteq N$</span> with <span class="math-container">$|S \setminus T| = |T \setminus S| \leq 1$</span> it holds that
<span class="math-container">\begin{align}
v(S \cup T) + v(S \cap T) \geq v(S) + v(T) \tag{C.2}.
\end{align}</span></p>

<p>There is no proof of the statement, but the author refers to <a href="https://www.cambridge.org/core/books/axioms-of-cooperative-decision-making/481FCBCDD15F3CCEE2FE381E7BF17B3D" rel="nofollow noreferrer">Moulin (1988, p. 112)</a>. But here it only gives an equivalent for Definition 1. </p>

<p><strong>Definition 1'.</strong><br>
A game <span class="math-container">$(N,v)$</span> is called convex, if for all <span class="math-container">$i \in N$</span> and <span class="math-container">$S \subset T \subset N \setminus \{i\}$</span> it holds that
<span class="math-container">\begin{align}
v(S \cup \{i\}) - v(S) \leq v(T \cup \{i\}) - v(T) \tag{C.3}.
\end{align}</span></p>

<p>Definitions 1. and 1'. are standard. I never heard of 2. though. I have a problem, however, where I can show that Def. 2. is satisfied. And now I'm wondering how to show the equivalence of Def. 2. with either 1. or 1.'.</p>

<mathematical-economics><cooperative-game-theory>
Convex games: equivalence of definitions
clueless
# Convex games: equivalence of definitions

(Asked by: username_0 on 2019-03-18)

Let $N \subset \mathbb N$ denote the set of players and $v : 2^N \to \mathbb R$ , $v(\emptyset) = 0$, the characteristic function.
We call $(N,v)$ a cooperative transferable utility (TU) [game](https://en.wikipedia.org/wiki/Cooperative_game_theory).

**Definition 1.**
A game $(N,v)$ is called convex, if for all $S,T \subseteq N$ it holds that
\begin{align}
v(S \cup T) + v(S \cap T) \geq v(S) + v(T) \tag{C.1}.
\end{align}
In [Hafalir (2007, p. 255)](https://www.sciencedirect.com/science/article/pii/S0899825607000164) it says that Def. (1) is equivalent to the following statement.

**Definition 2.**  
A game $(N,v)$ is called convex, if for all $S,T \subseteq N$ with $|S \setminus T| = |T \setminus S| \leq 1$ it holds that
\begin{align}
v(S \cup T) + v(S \cap T) \geq v(S) + v(T) \tag{C.2}.
\end{align}

There is no proof of the statement, but the author refers to [Moulin (1988, p. 112)](https://www.cambridge.org/core/books/axioms-of-cooperative-decision-making/481FCBCDD15F3CCEE2FE381E7BF17B3D). But here it only gives an equivalent for Definition 1.

**Definition 1'.**  
A game $(N,v)$ is called convex, if for all $i \in N$ and $S \subset T \subset N \setminus \{i\}$ it holds that
\begin{align}
v(S \cup \{i\}) - v(S) \leq v(T \cup \{i\}) - v(T) \tag{C.3}.
\end{align}

Definitions 1. and 1'. are standard. I never heard of 2. though. I have a problem, however, where I can show that Def. 2. is satisfied. And now I'm wondering how to show the equivalence of Def. 2. with either 1. or 1.'.

**Tags:** mathematical-economics, cooperative-game-theory


---

## 1 answers

### Answer by username_0 on 2019-03-19. Score: 1

Define the marginal contribution of $i \in N$ to any $C \subseteq N \setminus \{i\}$ by
\begin{align}
m\_i(C) = v(C \cup \{i\}) - v(C).
\end{align}

We are going to show C.1 $\Rightarrow$ C.2 $\Rightarrow$ C.3 $\Rightarrow$ C.1.
Note that C.1 $\Rightarrow$ C.2 is trivially true.
If C.1 holds for all $S,T \subseteq N$, then C.2 must hold for all $S,T \subseteq N$ with the restriction $|S \setminus T| = |T \setminus S| = 1$.
In order to show C.2 $\Rightarrow$ C.3 consider any $S \subseteq T \subseteq N \setminus \{i\}$.
Let $T \setminus S = \{j\_1, \ldots, j\_k\}$ and define $S\_\ell := T\_{\ell-1} \cup \{i\}$ and $T\_\ell := T\_{\ell-1} \cup \{j\_\ell\}$ for $\ell \in \{1,\ldots,k\}$ with $T\_0 = S$.
Note that
\begin{align}
\begin{split}
T\_{k-1} &~= T\_{k-2} \cup \{j\_{k-1}\} \\
&~= T\_{k-3} \cup \{j\_{k-2}\} \cup \{j\_{k-1}\} = T\_{k-3} \cup \{j\_{k-2},j\_{k-1}\}\\
& ~ \vdots\\
&~ = T\_0 \cup \{j\_1,\ldots,j\_{k-1}\}\\
&~ = S \cup \{j\_1,\ldots,j\_{k-1}\}\\
&~ = T \setminus \{j\_k\}
\end{split}
\end{align}
Since $|S\_\ell \setminus T\_\ell| = |T\_\ell \setminus S\_\ell| = 1$ we can apply C.2, i.e.
\begin{align}
\begin{split}
&v(S\_\ell \cup T\_\ell) + v(S\_\ell \cap T\_\ell) \geq v(S\_\ell) + v(T\_\ell)\\
\Longleftrightarrow \quad &v(T\_{\ell-1} \cup\{i, j\_\ell\}) + v(T\_{\ell-1}) \geq v(T\_{\ell-1} \cup \{i\}) + v(T\_{\ell-1} \cup \{j\_\ell\})\\
\Longleftrightarrow \quad &v(T\_{\ell-1} \cup\{i, j\_\ell\}) - v(T\_{\ell-1} \cup \{j\_\ell\}) \geq v(T\_{\ell-1} \cup \{i\}) - v(T\_{\ell-1})\\
\Longleftrightarrow \quad &m\_i(T\_{\ell-1} \cup\{j\_\ell\}) \geq m\_i(T\_{\ell-1})\\
\Longleftrightarrow \quad &\sum\_{\ell=1}^k{m\_i(T\_{\ell-1} \cup\{j\_\ell\})} \geq \sum\_{\ell=1}^k{m\_i(T\_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &\sum\_{\ell=1}^{k-1}{m\_i(T\_{\ell-1} \cup\{j\_\ell\})} + m\_i(T\_{k-1} \cup\{j\_k\}) \geq m\_i(T\_0) + \sum\_{\ell=2}^k{m\_i(T\_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &\sum\_{\tau=2}^{k}{m\_i(T\_{\tau-2} \cup\{j\_{\tau-1}\})} + m\_i((T \setminus \{j\_k\}) \cup\{j\_k\}) \geq m\_i(S) + \sum\_{\ell=2}^k{m\_i(T\_{\ell-1})}\\[2mm]
\Longleftrightarrow \quad &\sum\_{\tau=2}^{k}{m\_i(T\_{\tau-1})} + m\_i(T) \geq m\_i(S) + \sum\_{\ell=2}^k{m\_i(T\_{\ell-1})}\\
\Longleftrightarrow \quad & m\_i(T) \geq m\_i(S)
\end{split}
\label{eq:pvex}
\end{align}
The bottom line corresponds to C.3.
The final step C.3 $\Rightarrow$ C.1 is provided in Moulin (1988, p. 113).


---

