# Convex games: equivalence of definitions

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

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