Convex games: equivalence of definitions

Question

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.

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) 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). 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.'.

Answer 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).