Proof of separating hyperplane theorem using minimax theorem for zero sum games

Question

Let $x_1,\ldots,x_M\in\mathbb{R}^N$. Let $P \equiv conv \{x_1,\ldots,x_M\}$ denote the convex hull of these points. Using the Minimax Theorem prove that for all $y\in\mathbb{R}^N \setminus P$ there exists a vector $v\in[-1,1]^N$ such that $v\cdot(x-y)>0$ for all $x\in{}P$.

(Hint: Find a way of identifying $v$ and $x$ with mixed strategies in a zero-sum game.)

My attempt: I have been able to prove the other direction (that too with help from online lecture notes) - i.e. how to use the separating hyperplane theorem to prove the minmax theorem. But I'm unable to find a way to proceed with the direction required in the problem. Any help is appreciated.

Answer 1

Hint: $v^T(x-y)> 0$ for all $x \in P$ is the same as $\min_{x \in P} v^T(x-y) > 0$, and 'there exists a $v$' can turn this into "$\min_x \max_v$" or "$\max_v \min_x$" (one of the two, try to figure out which one). Then you can apply the minimax theorem and use that $x \neq y$.

---

prove that for all $y\in\mathbb{R}^N \setminus P$ there exists a vector $v\in[-1,1]^N$ such that $v\cdot(x-y)>0$ for all $x\in{}P$.

For any $x \in P$ we have $\max_{v \in [-1,1]^N} v^T(x-y) = \sum_{i=1}^N |x-y|_i >0$ since $x\neq y$. Therefore $ \min_{x \in P} \max_{v \in [-1,1]^N} v^T(x-y) > 0$. By the minimax theorem: $$\min_{x \in P} \max_{v \in [-1,1]^N} v^T(x-y) = \max_{v \in [-1,1]^N} \min_{x \in P} v^T(x-y)$$ so $\max_{v \in [-1,1]^N} \min_{x \in P} v^T(x-y)>0$, which means there exists a $v\in[-1,1]^N$ such that $\min_{x \in P} v^T(x-y)>0$, which means $v^T(x-y)>0$ for all $x \in P$.

Answer 2

Using LinAlg's hint, here is my attempt:

Consider the two-player zero-sum game where player 1 (the maximizer) chooses $g\in\{-1,1\}^N$ and player 2 (the minimizer) chooses one of the points $j\in\{1,\ldots,M\}$, and player 1's payoff is $\sum_{k=1}^Ng_k\cdot(p^j_k-q_k)$. By the Minimax Theorem, this game has a value $v$. Note that we can identify mixed strategies of player 1 with elements of $[-1,1]^N$, and mixed strategies of player 2 can be identified with elements of $P$ (by taking expectations). So the expected utility of player 1 from a mixed strategy profile $(\gamma,p)$ is $\sum_{k=1}^N\gamma_k(p_k-q_k)$.

Let $\gamma^*\in[-1,1]^N$ be a maxminimizer and let $p^*\in P$ be a minmaximizer. Then $v=\sum_{k=1}^N\gamma^*_k\cdot(p^*_k-q_k)$. Note that $\gamma=p^*/\lVert p^*\rVert\in[-1,1]^N$, so $v\geq\sum_{k=1}^{N}\gamma_k\cdot(p^*_k-q_k)=\lVert p^*-q\rVert>0$ (since $q\notin P$, and hence $q\neq p^*$). Thus, the value is positive, and so for any mixed strategy $p$, we have $\sum_{k=1}^{N}\gamma^*_k(p_k-q_k)>0$, as desired.