Aplicando un teorema de la alternativa en Carroll y Egorov (2019)

Question

En su demostración de la proposición $2$ de Carroll and Egorov (2019), hacen una apelación a un teorema de la alternativa que no entiendo del todo. En particular, no veo a qué versión del teorema están apelando y cómo se aplica. Agradecería algo de ayuda con esto.

Permitidme intentar explicar el problema de una manera que espero elimine cualquier necesidad de mirar el artículo al que he enlazado.

Sea $A=[0,\infty)^n$. Para cada $a\in A$ y $S \subset \{1,\ldots,n\}$, define $a\vert_S$ como el vector que coincide con $a$ a lo largo de las coordenadas dadas en $S$, y es cero en caso contrario. Es decir, $a\vert_S = \hat a$, donde $\hat a_i = a_i$ para $i \in S$, y $\hat a_i = 0$ en caso contrario.

También fijamos una función $V:A\to\mathbb R$ que es débilmente creciente en el orden del producto. Normalizamos $V(0) = 0$. (Abuso de notación al también usar $0$ para referirme al vector cero.) Esto implica que $V(a) \ge 0$ para todo $a \in A$.

En la demostración, afirman que, para cada $a\in A$ con $V(a) > 0$, existen números no negativos $r_1,\ldots,r_n$ tales que $r_1 + \cdots + r_n = V(a)$, y que, para cada subconjunto $S \subset \{1 ,\ldots,n \}$, $$ \sum_{i\in S} r_i \le V \left( a \vert_S \right). $$

Para demostrar esto, argumentan por contradicción. El inicio de su argumento dice

Supongamos que no. Entonces, aplicando un teorema de la alternativa, obtenemos la existencia de números no negativos $\lambda_S$, para cada $S \subset \{1,\ldots,n \}$, tales que $\sum_{S:i\in S}\lambda_S \ge 1$ para cada $i$ y $\sum_S \lambda_S V \left( a \vert_S \right) < V(a)$.

Desafortunadamente, no veo cómo la no existencia de $r_1,\ldots,r_n$ apropiados implica la afirmación dada anteriormente. Tampoco estoy seguro en qué versión del teorema se están basando.

¿Puede alguien ayudar a arrojar algo de luz sobre esto?

Answer 1

Puedes mostrar la existencia de los números $(\lambda_{S})_{S}$ apelando a la siguiente variante del lema de Farkas (ver https://es.wikipedia.org/wiki/Lema_de_Farkas#):
Para $A\in\mathbb{R}^{m \times n}$ y $b\in\mathbb{R}^{m}$, o bien $Ax \leq b$ tiene una solución con $x \geq 0$, o bien $A^{T}y \geq 0$ tiene una solución con $b^{T}y < 0$ y $y \geq 0$.

Sea $\iota = (1, \ldots 1) \in \mathbb{R}^{n}$ el vector de unos. En la notación del paper, las entradas del vector $\iota\vert_{S}$ son iguales a uno solo en las entradas correspondientes a los elementos de $S$.

Enumeremos los subconjuntos adecuados de $\lbrace 1, \ldots, n\rbrace$ como $S_{1}, \ldots, S_{2^{n}-1}$.
Podemos asumir que $V(a) > 0$ (de lo contrario, simplemente se podría elegir $r_{i} = 0$ para todos los $i$).
Ahora sea la matriz $A$:
$$ A= \begin{pmatrix} - \iota^{T} / V(a) \\ \left(\iota \vert_{S_{1}}\right)^{T} \\ \vdots \\ \left(\iota \vert _{S_{2^{n}-1}}\right)^{T} \end{pmatrix}, $$y sea $b$ el vector:
$$ b = \begin{pmatrix} - 1 \\ V\left(a\vert_{S_{1}}\right) \\ \vdots \\ V\left(a\vert_{S_{2^{n}-1}}\right) \end{pmatrix}. $$

Si los números $r_{1}, \ldots r_{n}$ no existen, entonces, en particular, no existe ningún vector $r$ tal que $$ Ar \leq b $$.
Por lo tanto, el lema de Farkas implica la existencia de números no negativos $(\lambda_{0}, \lambda_{1}, \ldots, \lambda_{2^{n}-1})$ tales que $A^{T} \lambda \geq 0$ y $b^{T} \lambda < 0$.
La primera desigualdad afirma que para todo $i \in\lbrace 1, \ldots, n\rbrace$,
$$ - \frac{\lambda_{0}}{V(a)} + \sum_{j \colon i\in S_{j}, j\neq 0} \lambda_{j} \geq 0 $$ es cierto.
La segunda desigualdad no es más que $$ - \lambda_{0} + \sum_{j \neq 0}V\left(a\vert_{S_{j}}\right) \lambda_{j} < 0. $$
Observa que la segunda desigualdad implica que $\lambda_{0} > 0$. Por lo tanto, si normalizamos estableciendo $\lambda_{j}^{\prime} = \lambda_{j} \lambda_{0} / V(a)$ para todos los $j \neq 0$, los números $(\lambda_{j}^{\prime})_{j}$ nos dan lo que buscamos.