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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.