Min-max theorem

From Theory

Jump to: navigation, search

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

We have a two-person zero-sum normal-form game G = (N=2,A = \times_{i=1}^N A_i, u: A \rightarrow \reals^N) with action sets A1,A2 and payoffs u_1(=-u_2):A_1 \times A_2 \rightarrow \reals.

The intention of such a game, as we have defined, is for both players to announce their actions simultaneously. However, it would seem to be much easier to analyze the game if one player had to move first. Suppose, for example, that player 1 had to move first and announce an action a_1 \in A_1, which player 2 could then see. Whatever a1 player 1 chose, it would make sense for player 2 to choose a best response, in which case player 1 would get \min_{a_2 \in A_2} u_1(a_1,a_2). Hence, the best player 1 could guarantee going first in this setting is,

pure-strategy max-min is \max_{a_1}\min_{a_2} u_1(a_1,a_2).

Conversely, if player 1 went second, the best she could guarantee would be,

pure-strategy min-max is \min_{a_2}\max_{a_1} u_1(a_1,a_2).

However, the above discussion is for pure strategies, i.e., we have not considered mixed strategies. Let us work through the example of match pennies. In this game, player 1 would get − 1 if going first and 1 if going second.

More interesting to consider are mixed strategies. Let us define,

mixed-strategy max-min v_i=\max_{\sigma_i\in \Delta_i}\min_{\sigma_{-i}\in \Delta_{-i}} u_i(\sigma_i,\sigma_{-i}), what player i would get if she went first.

Similarly, consider,

mixed-strategy min-max \bar{v}_i=\min_{\sigma_{-i}\in \Delta_{-i}}\max_{\sigma_i\in \Delta_i} u_i(\sigma_i,\sigma_{-i}), what player i would get if she went second.

Note that two things are relatively easy to see:

v_i \leq \bar{v}_i = -v_{-i}.

The inequality states that it is an advantage to go second -- you have only more information. The equality states that what player 1 would get if she went first is the opposite of what player 2 would get if she went first (and player 1 went second). This follows directly from the fact that it is a zero-sum game. Formally,

\bar{v}_i=\max_{\sigma_i}\min_{\sigma_{-i}} u_i(\sigma_i,\sigma_{-i}) = \max_{\sigma_i}\min_{\sigma_{-i}} -u_{-i}(\sigma_i,\sigma_{-i}) = -\min_{\sigma_i}\max_{\sigma_{-i}} u_{-i}(\sigma_i,\sigma_{-i})=-v_{-i}.

In the above we have used the fact that max − f(x) = − minf(x) and min − f(x) = − maxf(x).

Min-max Theorem: [von Neumann, 1928]

For any finite, two-person zero-sum game,

\max_{\sigma_i \in \Delta_i} \min_{\sigma_{-i} \in \Delta_{-i}} u_i(\sigma_i,\sigma_{-i})=\min_{\sigma_{-i} \in \Delta_{-i}} \max_{\sigma_i \in \Delta_i} u_i(\sigma_i,\sigma_{-i})\,

Using our previous notation, this can be written as v_i = \bar{v}_i or as,

v1 + v2 = 0

So if player 1 can guarantee v1, and player 2 can guarantee v2, and v1 + v2 = 0, and it's a zero-sum game, we have a pretty compelling way to play.

We give a proof of the min-max theorem, by giving a strategy for repeated-games that guarantees each player its min-max value, on average.


[edit]

Max-min strategy

Note that the mixed-strategy max-min value vi for player i is a notion that applies to an arbitrary game (general-sum, arbitrary number of players). Its definition is the same,

v_i=\max_{\sigma_i\in \Delta_i}\min_{\sigma_{-i}\in \Delta_{-i}} u_i(\sigma_i,\sigma_{-i}), what player i would get if she went first.

A max-min strategy for player i is a strategy that guarantees at least vi for player i.

\mathrm{MAXMIN}_i = \{ \sigma_i \in \Delta_i ~|~ \min_{\sigma_{-i} \in \Delta_{-i}} u_i(\sigma_i,\sigma_{-i})=v_i\}.\,

In zero-sum games, the min-max theorem shows that max-min strategies are arguably optimal.



The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Min-max_theorem"
Personal tools