Game Theory: Primal, Dual, and Optimal Strategies

Introduction

In our last session, we reached the theoretical climax of the course by proving von Neumann's Minimax Theorem. We established that for any two-player, zero-sum game, the row player's maximin value is equal to the column player's minimax value. We achieved this by formulating each player's problem as a linear program (LP), showing they form a primal-dual pair, and then invoking the Strong Duality Theorem.

Today, we will build directly on that proof. We know the optimal values of the primal and dual LPs are equal, but what about the optimal solutions—the vectors that achieve those values? This lesson addresses exactly that. Our learning outcome is to interpret the optimal primal and dual solutions of the game's LP formulation as the value of the game and the optimal mixed strategies. We will see how these solutions give us the players' best strategies and form a Nash Equilibrium.

This lesson will solidify your understanding and provide the final piece of the puzzle for your assignment.

1. The Value and Strategies of the Game

Let's quickly recall the primal-dual pair of LPs we developed for a zero-sum game with payoff matrix $A$:

Primal LP (Row Player's Maximin Problem)

Dual LP (Column Player's Minimax Problem)

From the Strong Duality Theorem, we know their optimal values are equal. Let's call this common optimal value $v$.

This value $v$ is formally known as the value of the game. It represents the expected payoff when both players play optimally. It's the most the row player can guarantee for themselves and the least the column player can guarantee they will have to concede.

Now, what about the optimal solutions?

• Let $({\mathbf{x}}^{\ast },u^{\ast })$ be an optimal solution to the primal LP.
• Let $({\mathbf{y}}^{\ast },w^{\ast })$ be an optimal solution to the dual LP.

By the very way we constructed these LPs, the vectors ${\mathbf{x}}^{\ast }$ and ${\mathbf{y}}^{\ast }$ are the mixed strategy probability vectors that achieve the maximin and minimax values, respectively.

Therefore:

• ${\mathbf{x}}^{\ast }$ is the optimal mixed strategy for the row player.
• ${\mathbf{y}}^{\ast }$ is the optimal mixed strategy for the column player.

The triplet $({\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast },v)$ represents the complete solution to the game.

2. The Connection to Nash Equilibrium

We've found the optimal strategies. A key result in game theory is that in a two-player zero-sum game, the set of minimax-optimal strategies coincides with the set of Nash Equilibria. Let's prove that the strategy profile $({\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast })$ we found is indeed a Nash Equilibrium.

Recall that for a zero-sum game, a profile $({\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast })$ is a Nash Equilibrium if:

1. ${\mathbf{x}}^{\ast T}A{\mathbf{y}}^{\ast }\ge {\mathbf{x}}^{T}A{\mathbf{y}}^{\ast }$ for any other strategy $\mathbf{x}$ of the row player (Row player cannot improve by deviating).
2. ${\mathbf{x}}^{\ast T}A{\mathbf{y}}^{\ast }\le {\mathbf{x}}^{\ast T}A\mathbf{y}$ for any other strategy $\mathbf{y}$ of the column player (Column player cannot improve by deviating).

The following reading provides an elegant proof of this property, building directly on the results of the LP formulation.

Let's summarize the logic from the resource:

1. From the optimality of ${\mathbf{x}}^{\ast }$ in the primal LP, we know it achieves the value of the game, $v$, against the column player's best response. So, $v={\min }_y{\mathbf{x}}^{\ast T}A\mathbf{y}$.
2. From the optimality of ${\mathbf{y}}^{\ast }$ in the dual LP, we know it also achieves the value $v$ against the row player's best response. So, $v={\max }_x{\mathbf{x}}^{T}A{\mathbf{y}}^{\ast }$.

Combining these, we get the chain of inequalities:
${\min }_y{\mathbf{x}}^{\ast T}A\mathbf{y}\le {\mathbf{x}}^{\ast T}A{\mathbf{y}}^{\ast }\le {\max }_x{\mathbf{x}}^{T}A{\mathbf{y}}^{\ast }$
Substituting the values we know:
$v\le {\mathbf{x}}^{\ast T}A{\mathbf{y}}^{\ast }\le v$
This forces the conclusion that ${\mathbf{x}}^{\ast T}A{\mathbf{y}}^{\ast }=v$.

Now we can check the Nash Equilibrium conditions:

• Can the row player do better than $v$? No, because ${\max }_x{\mathbf{x}}^{T}A{\mathbf{y}}^{\ast }=v$. Their current strategy already gives them the maximum possible payoff against ${\mathbf{y}}^{\ast }$.
• Can the column player do better than $v$? (Doing "better" means forcing a payoff lower than $v$). No, because ${\min }_y{\mathbf{x}}^{\ast T}A\mathbf{y}=v$. Their current strategy already holds the row player to the minimum possible payoff against ${\mathbf{x}}^{\ast }$.

Thus, the profile $({\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast })$ is a Nash Equilibrium, and the payoff is the value of the game, $v$.

3. A Practical Example: Solving a Game

So far, our discussion has been theoretical. Let's see how this works in practice by solving a game. When solving a game via linear programming, we often use a slightly different (but equivalent) LP formulation that is easier to handle with standard algorithms like the simplex method.

The key idea is to transform the variables. Let's start with the column player's minimax problem:

where $A_i^T$ is the $i$-th row of $A$. Let $v$ be the value of the game. If we assume $v>0$ (which can always be ensured by adding a large constant to all entries in $A$), we can define a new variable $\mathbf{z}$ where $z_j=y_j/v$.

The original condition $\sum y_j=1$ becomes $v\sum z_j=1$, or $\sum z_j=1/v$. Since the column player wants to minimize $v$, this is equivalent to maximizing $\sum z_j$. The constraints $A\mathbf{y}\le v1$ become $A(v\mathbf{z})\le v1$, which simplifies to $A\mathbf{z}\le 1$.

This gives us the following standard-form LP for the column player:

• Maximize $1^T\mathbf{z}$
• Subject to $A\mathbf{z}\le 1$, $\mathbf{z}\ge 0$

Its dual corresponds to the row player's problem:

• Minimize $1^T\mathbf{x}$
• Subject to $A^T\mathbf{x}\ge 1$, $\mathbf{x}\ge 0$

The following resource walks through solving the classic game of Rock-Paper-Scissors using this method. It's a fantastic demonstration of how to interpret the final LP solution.

Let's summarize the key interpretation steps from the resource:

1. Solve the Primal LP: You solve the column player's problem (maximize $1^T\mathbf{z}$) to get an optimal solution ${\mathbf{z}}^{\ast }$ and an optimal value $V_{LP}^{\ast }=1^T{\mathbf{z}}^{\ast }$.
2. Find the Game Value: The value of the game is the reciprocal of the LP's optimal value: $v=1/V_{LP}^{\ast }$.
3. Find the Column Player's Strategy: The column player's optimal strategy ${\mathbf{y}}^{\ast }$ is found by re-scaling ${\mathbf{z}}^{\ast }$: ${\mathbf{y}}^{\ast }=v\cdot {\mathbf{z}}^{\ast }$.
4. Find the Row Player's Strategy: The optimal solution to the dual LP, ${\mathbf{x}}^{\ast }$, can be read directly from the final simplex tableau (as the "shadow prices" in the z-row corresponding to the initial slack variables). The row player's strategy ${\mathbf{p}}^{\ast }$ is found by re-scaling ${\mathbf{x}}^{\ast }$ in the same way: ${\mathbf{p}}^{\ast }=v\cdot {\mathbf{x}}^{\ast }$.

This concrete example perfectly illustrates how the abstract vectors ${\mathbf{x}}^{\ast }$ and ${\mathbf{y}}^{\ast }$ from duality theory translate into actionable optimal strategies for the players.

Conclusion

This lesson, and this course, has brought you from the fundamentals of game theory to a deep, proof-based understanding of the central theorem for two-player zero-sum games. You have not only seen the proof of the Minimax Theorem but have also learned how to use its machinery to find the solution to a game.

Key Takeaways:

• The optimal solution vectors of the primal and dual LPs, ${\mathbf{x}}^{\ast }$ and ${\mathbf{y}}^{\ast }$, are the optimal mixed strategies for the row and column players.
• The shared optimal value of the LPs, $v$, is the value of the game.
• The strategy profile $({\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast })$ constitutes a Nash Equilibrium.
• By transforming variables, we can use standard LP solvers to find the value of a game and the optimal strategies for both players from a single calculation.

This concludes our journey. You now possess the key theoretical tools to analyze zero-sum games, grounded in the powerful framework of linear programming and its duality—precisely the knowledge required for your assignment. Good luck