Juegos convexos: equivalencia de las definiciones

Question

Deje que $N \subset \mathbb N$ denotan el conjunto de jugadores y $v : 2^N \to \mathbb R$ , $v( \emptyset ) = 0$ la función característica. Llamamos $(N,v)$ una utilidad transferible cooperativa (TU) juego .

Definición 1. Un juego $(N,v)$ se llama convexo, si para todos $S,T \subseteq N$ sostiene que \begin {alinear} v(S) \cup T) + v(S) \cap T) \geq v(S) + v(T) \tag {C.1}. \end {alinear} En Hafalir (2007, pág. 255) dice que Def. (1) es equivalente a la siguiente declaración.

Definición 2.
Un juego $(N,v)$ se llama convexo, si para todos $S,T \subseteq N$ con $|S \setminus T| = |T \setminus S| \leq 1$ sostiene que \begin {alinear} v(S) \cup T) + v(S) \cap T) \geq v(S) + v(T) \tag {C.2}. \end {alinear}

No hay pruebas de la declaración, pero el autor se refiere a Moulin (1988, p. 112) . Pero aquí sólo da un equivalente para la Definición 1.

Definición 1'.
Un juego $(N,v)$ se llama convexo, si para todos $i \in N$ y $S \subset T \subset N \setminus \{i\}$ sostiene que \begin {alinear} v(S) \cup \ ~ - v(S) \leq v(T) \cup \ ~ - v(T) \tag {C.3}. \end {alinear}

Las definiciones 1. y 1'. son estándar. Aunque nunca he oído hablar de la 2. Tengo un problema, sin embargo, en el que puedo demostrar que la definición 2. está satisfecha. Y ahora me pregunto cómo mostrar la equivalencia de la definición 2 con la 1 o la 1.

Answer 1

Definir la contribución marginal de $i \in N$ a cualquier $C \subseteq N \setminus \{i\}$ por \begin{align} m_i(C) = v(C \cup \{i\}) - v(C). \end{align}

Vamos a mostrar C.1 $\Rightarrow$ C.2 $\Rightarrow$ C.3 $\Rightarrow$ C.1. Obsérvese que C.1 $\Rightarrow$ C.2 es trivial. Si C.1 se cumple para todo $S,T \subseteq N$ entonces C.2 debe cumplirse para todos los $S,T \subseteq N$ con la restricción $|S \setminus T| = |T \setminus S| = 1$ . Para demostrar C.2 $\Rightarrow$ C.3 considerar cualquier $S \subseteq T \subseteq N \setminus \{i\}$ . Sea $T \setminus S = \{j_1, \ldots, j_k\}$ y definir $S_\ell := T_{\ell-1} \cup \{i\}$ y $T_\ell := T_{\ell-1} \cup \{j_\ell\}$ para $\ell \in \{1,\ldots,k\}$ con $T_0 = S$ . Tenga en cuenta que \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} Desde $|S_\ell \setminus T_\ell| = |T_\ell \setminus S_\ell| = 1$ podemos aplicar C.2, es decir \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} |eq:pvex} |align} La línea inferior corresponde a C.3. El último paso C.3 $\Rightarrow$ C.1 se encuentra en Moulin (1988, p. 113).