Corresponding LP problems to zero sum games

Question

Given a zero sum game like this one :

\begin{array}{c|rrrr} & A & B \\\hline X & 10 & 3 \\ Y & 5 & 9 \\ \end{array}

how do you find an equivalent linear program ?

I think the answer is :

minimize $ x+y $ s.t. :

$x \geq 0, y \geq 0$,

$ 10x + 5y \geq 1 $,

$ 3x + 9y \geq 1 $

but I'm not sure about this. How do you find that ? I've asked some PHD student but they didn't know either.

Answer 1

When the game is a zero-sum game, the equilibrium can be found by applying maxmin strategy. (thanks to John von Neumann)
Let $p$ is the payoff. $$\max [ \min [E(p|A), E(p|B)]]$$

To implement this in LP(linear programming)

$\max G$
s.t.
$10 P_X + 5 P_Y \ge G$
$3 P_X + 9 P_Y \ge G$
$P_X+P_Y = 1$
$P_X, P_Y, G \ge 0$

Where $P_X$ : Probability to choose $X$, $P_Y$ : Probability to choose $Y$

Indeed,
$10 P_X + 5 P_Y$ is $E(p|A)$; Expected payoff when the opponent chooses $A$.
$3 P_X + 9 P_Y$ is $E(p|B)$; Expected payoff when the opponent chooses $B$.

---

I can change my formula to similar to yours.

$10 P_X + 5 P_Y \ge G$ divide $G$ both sides
$3 P_X + 9 P_Y \ge G$ divide $G$ both sides

And define $x = \frac{P_X}{G}$ and $y = \frac{P_Y}{G}$, then

$10 x + 5 y \ge 1$
$3 x + 9 y \ge 1$
And since $P_X+P_Y = 1$, $x+y = \frac{1}{G}$

Therefore, $\max G$ is the same as $\min x+y$

It turned into

$\min x+y$
$10 x + 5 y \ge 1$
$ 3x + 9 y \ge 1$
$x,y \ge 0$

If we look from the column player's point of view, the smaller the number in the table, the better (zero-sum).

That's why it will be (the dual fo the previous LP)

$\max a+b$
$10 a +3 b \le 1$
$5 a + 9 b \le 1$
$a,b \ge 0$

where $a = \frac{P_A}{G}$ and $P_A$ : Probability that column player chooses A and so on.

Answer 2

Maximin strategy for zero sum game.

Since it is zero sum, the maximum for me is the minimum for my opponent, maximum for my opponent is minimum for me.

Since both of player are trying to maximize their own payoff, My opponent tries to minimize my payoff.

That’s why I will get the minimum payoff by my opponent. Under the condition, how can I maximize my payoff? I should maximize the minimum payoff.

In LP how to implement $max(min(a,b))$ is
$\max G$
S.t.
$a \ge G$
$b \ge G$

Think about it a while. How can I maximize $G$, while the constraints are satisfied? Only way is to maximize the minimum of $a$ and $b$.

Zero sum game LP formula
G : the minimum of expected payoff between opponent’s choice A and B