Linear Programming for Zero-Sum Games

1. The Player's Goal: A Guaranteed Payoff

Let's consider a two-player, zero-sum game defined by a payoff matrix $A$. Alice, the row player, wants to choose a mixed strategy, which is a probability vector $\mathbf{x}=(x_1,\dots ,x_m)$ where $x_i\ge 0$ and $\sum x_i=1$. Bob, the column player, similarly chooses a mixed strategy $\mathbf{y}=(y_1,\dots ,y_n)$. The expected payoff to Alice is ${\mathbf{x}}^{T}A\mathbf{y}$.

Alice's challenge is that she must choose her strategy $\mathbf{x}$ without knowing Bob's strategy $\mathbf{y}$. A conservative, risk-averse approach for Alice is to choose a strategy that does as well as possible in the worst-case scenario. This is called a maximin strategy.

She wants to choose the $\mathbf{x}$ that maximizes her guaranteed payoff. For any given $\mathbf{x}$ she chooses, her guaranteed payoff is the minimum possible payoff she could receive, assuming Bob will play his best response to minimize it.
So, for a fixed $\mathbf{x}$, her guaranteed payoff is:

where the minimum is taken over all of Bob's possible mixed strategies $\mathbf{y}$. Alice's overall goal is to choose $\mathbf{x}$ to make this guaranteed value as large as possible.

2. Simplifying the Worst Case

Calculating the minimum over all of Bob's possible mixed strategies $\mathbf{y}$ seems complicated. However, a key insight simplifies this significantly. To minimize his expected loss (which is Alice's gain ${\mathbf{x}}^{T}A\mathbf{y}$), Bob only needs to consider his pure strategies.

The following reading explains and proves this crucial simplification.

The logic is straightforward: the expected payoff ${\mathbf{x}}^{T}A\mathbf{y}$ is a weighted average of the payoffs against Bob's pure strategies. An average can never be smaller than the smallest value being averaged. Therefore, to find the minimum payoff, Bob simply needs to identify which of his pure strategies (columns) yields the lowest payoff against Alice's chosen $\mathbf{x}$ and play that one.

This means we can simplify Alice's guaranteed payoff for a strategy $\mathbf{x}$ to:

The expected payoff if Bob plays column $j$ is ${\sum }_{i=1}^m{x}_i{A}_{ij}$, which is the $j$-th component of the vector ${\mathbf{x}}^{T}A$.

3. From Maximin Problem to a Linear Program

With this simplification, we can state Alice's maximin problem more formally:

Alice's Problem: Find a probability vector $\mathbf{x}$ that solves:

This is an optimization problem, but it's not a linear program because the objective function involves a min operation. However, we can convert it into one using a standard technique.

The trick is to introduce a new variable, let's call it $u$, which will represent the value of the objective function (the minimum payoff).

1. New Objective: Instead of maximizing the minimum of several values, we simply **maximize $u$
   **.
2. New Constraints: We add constraints to force $u$ to be less than or equal to each of the expressions inside the original min function. If we maximize $u$, the optimal solution will push $u$ upwards until it is equal to the smallest of these expressions.

This transforms the problem into:

Alice's LP (preliminary form):

The decision variables here are $u$ and $x_1,\dots ,x_m$. The objective function is linear, and all the constraints are linear inequalities. We have successfully formulated the problem as a linear program.

4. The Final LP Formulation

To make this compatible with the duality theory we studied, it's best to write it in standard matrix/vector notation. The following reading does exactly this.

Let's consolidate the formulation. Let $1$ be a column vector of ones of the appropriate dimension.

The set of constraints $u\le {\sum }_{i=1}^m{x}_i{A}_{ij}$ for $j=1,\dots ,n$ can be rewritten. The sums ${\sum }_{i=1}^m{x}_i{A}_{ij}$ are the components of the row vector ${\mathbf{x}}^{T}A$. So the constraints are equivalent to $u\cdot 1^T\le {\mathbf{x}}^{T}A$, where $1$ is $n\times 1$. It's more common to write this using column vectors, by transposing both sides: $A^T\mathbf{x}\ge u\cdot 1$.

This gives us the final LP for the row player (Alice):

Row Player's (Primal) LP

Here, the variables are the vector $\mathbf{x}\in {\mathbb{R}}^m$ and the scalar $u\in \mathbb{R}$. This is the linear program that, when solved, gives Alice her optimal mixed strategy ${\mathbf{x}}^{\ast }$ and the value of the game $u^{\ast }$, which is her guaranteed security level.

To make this concrete, let's consider the 3x3 game from the MIT lecture notes (resource_id=[LINK](https://dspace.mit.edu/bitstream/handle/1721.1/84610/15-053-spring-2007/contents/lecture-notes/lec11.pdf)) with payoff matrix:

Alice's problem is to find $\mathbf{x}=(x_1,x_2,x_3)$ and $u$. The LP would be:

This LP directly corresponds to the abstract formulation and is ready to be solved.

Conclusion

In this lesson, we successfully bridged the gap between game theory and linear programming. You learned how to take a player's strategic objective—maximizing their worst-case outcome—and systematically convert it into a solvable linear program.

Key Takeaways:

• A maximin strategy for the row player is a mixed strategy $\mathbf{x}$ that maximizes the guaranteed payoff, assuming the column player will choose a response to minimize it.
• The worst-case scenario for a fixed mixed strategy $\mathbf{x}$ always occurs when the opponent plays one of their pure strategies.
• This leads to a max-min optimization problem, which is not linear.
• By introducing an auxiliary variable $u$ to represent the minimum payoff, we can transform the max-min problem into a standard linear program.
• The resulting LP's optimal solution provides both the player's optimal mixed strategy ${\mathbf{x}}^{\ast }$ and the maximin value of the game $u^{\ast }$.

Preview of the next lesson:

We have just formulated the row player's (Alice's) problem as a primal linear program. What do you think will happen if we construct the dual of this LP? In the next lesson, we will do exactly that. You will see that the dual LP is precisely the column player's (Bob's) problem of finding his optimal strategy. This remarkable symmetry, combined with the Strong Duality Theorem, will provide us with a direct and elegant proof of the Minimax Theorem.