Von Neumann's minimax theorem and Carathéodory's theorem

556 Views Asked by At

In J.F. Mertens(1986)(Paywall), there's a neat proof of a version of Von Neumann's minimax theorem. But I can't understand how Carathéodory's theorem is invoked.

Suppose, in a two-person zero sum game, player I's strategy space is a compact set $S$, while player II' strategy space is a finite set $T = \{t_i\}_{1 \leq i \leq n}$. $f : S \times T \to \Bbb R \cup \{-\infty, + \infty\}$ is player I's payoff function, which is uppersemicontinuous and bounded either from above or below. To show the mixed extension of this game has a value:

enter image description here

I guess Carathéodory's theorem here is referred to:

For $S ⊂ \Bbb R^d$, if $x ∈ \operatorname{conv}(S)$ then $x ∈ \operatorname{conv}(R)$ for some $R ⊂ S$,$|R| ≤ d + 1$.

I can't see how this imply that we only need to consider player I's mixed strategies with a finite support no more than $n$.

1

There are 1 best solutions below

6
On BEST ANSWER

Let $\sigma$ be a strategy for the first player (that is, $\sigma$ is a probability distribution on $S$). Define vector $u(s) = (f(s,t_1),\dots,f(s,t_n))$ for every $s\in S$ and vector $v(\sigma) = (v_1(\sigma), \dots, v_n(\sigma))$ by $v_i(\sigma) = \int_S f(s,t_i) d\sigma(s)$. We have, $$v(\sigma) = \int_S u(s) d\sigma(s).$$ Suppose that player II uses strategy $\tau$. Then the value of the game (when I uses $\sigma$ and II uses $\tau$) equals $$\sum_{i=1}^n \left(\int_S f(s,t_i) d\sigma(s) \cdot \tau(t_i)\right) = \sum_{i=1}^n v_i(\sigma) \tau(t_i).$$ Observe that if $v(\sigma_1) = v(\sigma_2)$ for two strategies $\sigma_1$ and $\sigma_2$ then for every strategy $\tau$ of II, the the game has the same value when I uses strategy $\sigma_1$ and when I uses strategy $\sigma_2$. That is, $\sigma_1$ and $\sigma_2$ are equivalent.

We show that for every strategy $\sigma$, there is an equivalent strategy $\sigma'$ with support of size at most $n+1$. Since
$$v(\sigma) = \int_S u(s) d\sigma(s) = \mathbb{E}_{s\sim \sigma}[u(s)],$$ vector $v(\sigma)$ lies in the convex hull of vectors $\{u(s):s\in S\}$ (see Mathematical expectation is inside convex hull of support for an explanation why this is the case). By Carathéodory's theorem, we have that $v(\sigma)$ is a convex combination of at most $n+1$ vectors $u(s_1),\dots, u(s_{n+1})$ for some $s_1,\dots,s_{n+1}\in S$. That is, there is a distribution $\sigma'$ on $s_1,\dots, s_{n+1}$ equivalent to $\sigma$. In other words, $$v(\sigma) = \sum_{i=1}^{n+1} \sigma'(s_i) u(s_i).$$