Zero Sum Games

Goal:

Develop a strategy to maximize your own score while minimizing your opponents, using an immediate payoff matrix and assumming both players play optimally.

	0	1
0	A	B
1	C	D

Solving with Linear Programming:

• Let x_i denote the probability that the row player plays strategy i and y_j denote the probability the the column player plays strategy j.
• If the column player uses strategy j₀, then the row player’s payoff will be Ax₀ + Cx₁
• If the column player uses strategy j₁, then the row player’s payoff will be Bx₀ + Dx₁
• So the column player’s optimal strategy becomes: min(Ax₀ + Cx₁, Bx₀ + Dx₁)
• As a result, the row player’s optimal strategy also becomes max(min(Ax₀ + Cx₁, Bx₀ + Dx₁))

Linear Program Solution for Row Player:

• max P
  • p <= Ax₀ + Cx₁
  • p <= Bx₀ + Dx₁
  • x_i >= 0
• x₀ + x₁ = 1

Note: The LP for the Row Player and the LP for the Column Player are Dual to each other despite which player announces their strategy first.