# Applying Linear Programming to Game Theory

## Introduction

A central problem in algorithmic game theory involves finding the Nash equilibria of a game quickly. It turns out that this task is very hard in general – finding Nash equilibria is, in fact, PPAD-complete, even for two-player games. There are, however, classes of games for which finding Nash equilibria is computable in worst-case polynomial time, using linear programming. In this blog post, we’ll explore three of these examples: proving the minmax theorem, finding Nash equilibria given the supports of the equilibrium strategies, and finding correlated equilibria.

## Simultaneous-Move Games

A simultaneous-move game $(N,A,u)$ is defined as a set of agents, actions, and payoffs. More formally, we have

• $N = \{1,...n\}$ agents, indexed by $i$
• $A = A_1 \times ... \times A_n$, where $A_i$ is a set of actions available to agent $i$ and where $a = (a_1,...,a_n) \in A$ denotes an action profile
• $u = (u_1,...u_n)$, where $u_i: A \rightarrow \mathbb{R}$ is the payoff function for agent $i$.

## Nash Equilibrium

A Nash equilibrium is an action profile where nobody has an incentive to deviate from his prescribed action when fixing the others’ actions. A Nash equilibrium can be of pure-strategies or mixed strategies.

#### Pure-Strategy Nash Equilibrium

In a pure strategy Nash equilibrium, each player plays one action in equilibrium.

More formally, an action profile $a^* = (a_1^*,...,a_n^*)$ is a pure-strategy Nash equilibrium of the simultaneous-move game (N,A,u) if for all i,

$u_i(a_i^*,a_{-i}^*) \geq u_i(a_i,a_{-i}^*) \text{ for all strategies } a_i \in A_i.$

#### Mixed-Strategy Nash Equilibrium

In a mixed-strategy Nash equilibrium, a player can play a subset of his available actions according to a certain probability distribution. We say that the strategies $a_i \in A_i$ played with positive probability in a mixed-strategy is in the support of that strategy profile.

Formally, a strategy profile $\sigma^* = (\sigma_1^*,...,\sigma_n^*)$ is a mixed-strategy Nash equilibrium in game $(N,A,u)$ if for all $i$,
$u_i(\sigma_i^*,\sigma_{-i}^*) \geq u_i(a_i,\sigma_{-i}^*) \text{ for all strategies } a_i \in A_i.$

## Chicken

One example of a two-player, simultaneous move game is the game of chicken. The story for the game is as follows:

Two teenagers are driving towards each other at a high velocity. If one swerves before the other, the “chicken” loses prestige among his peers, while the other gains prestige. If both of them swerve together, they both retain their honor. If neither of them swerve, both suffer serious injuries, which is much worse than losing their prestige.

This game can be represented in normal form as follows:

The rows represent the strategies available to player 1 while the columns represent the strategies available to player 2. The left number within a matrix entry represents the payoff to player 1 when the respective actions are played, while the right number represents the payoff to player 2. It is easy to see that there is no pure-strategy Nash equilibrium to this game. A mixed-strategy equilibrium does exist, however, where both players swerve with probability $\frac{2}{3}$ and go straight with probability $\frac{1}{3}$. In fact, there is a theorem, which we will not prove, that every finite-strategy, finite-player game has a mixed-strategy Nash equilibrium.

## Two-player, Zero-sum Games

A zero-sum game is a game in which the total payoffs to the players sum to 0 for every action profile in the game. (In fact, these games could also be called constant-sum games, since the payoffs need only sum to the same constant value).

#### Maximin Strategy

A maximin strategy for player 1 is a strategy which maximizes player 1’s payoff given that player 2 tries to minimize player 1’s payoff for any given strategy $a_1 \in A_1$. Namely,
$\overline{s_1} \in arg max_{s_1} \left[min_{a_2\in A_2} u_1(s_1,a_2)\right]$

#### Minimax Strategy

A minimax strategy for player 1 is a strategy which minimizes player 2’s expected utility, given that player 2 tries to maximize his own payoff given any strategy of player 1.
$\underline{s_1} \in arg min_{s_1} \left[max_{a_2\in A_2} u_2(s_1,a_2)\right]$

#### Minmax Theorem

The minmax theorem states that for any two-player, zero-sum game, the set of each player’s maximin strategies will be identical to the set of minimax strategies, that any combination of these minimax/maximin strategies will be a Nash equilibrium of the game, and that each player’s maximin value will equal its minimax value. We can prove this theorem using strong duality.

To solve the maximin value for Player 1, we can solve the LP

Maximize v
Subject to:

$v - u_1(a_1,a_2)p_1(a_1) \leq 0$
$\sum_{a_1 \in A_1} p_1(a_1) = 1$
$p_1(a_1) \geq 0, \forall a_1 \in A_1$
where $p_1(a_1)$ is the probability with which player 1 plays the action $a_1 \in A_1$.

The dual to this problem is

Minimize u
Subject to:

$u - u_2(a_1,a_2)p_2(a_2) \geq 0$
$\sum_{a_2 \in A_2} p_2(a_2) = 1$
$p_2(a_2) \geq 0, \forall a_2 \in A_1$
where $p_2(a_2)$ is the probability with which player 2 plays the action $a_2 \in A_2$.

This is exactly the same as the LP for Player 2’s optimal strategy, and thus strong duality gives us the minmax theorem. We can solve for the minimax/maximin strategies using an algorithm like the simplex algorithm.

## Finding a Nash equilibrium when given the supports in a general two-player game

Although it is difficult to find mixed-strategy Nash equilibria for finite-games in general, it is simpler to find Nash equilibria given the strategies that are in the support of each player’s mixed-strategy in equilibrium. Indeed, given candidate supports $(\sigma_1,\sigma_2)$, we may find Nash equilibria, if feasible, by solving the following LP for any objective function:

Maximize  Any objective function
Subject to:

$\sum_{a_2\in A_2} u_1(a_1,a_2)p_2(a_2) = v_1, \forall a_1 \in \sigma_1$
$\sum_{a_2\in A_2} u_1(a_1,a_2)p_2(a_2) \leq v_1, \forall a_1 \notin \sigma_1$
$\sum_{a_1 \in A_1} p_1(a_1) = 1$
$p_1(a_1) \geq 0, \forall a_1 \in \sigma_1$
$p_1(a_1) = 0, \forall a_1 \notin \sigma_1$
$\sum_{a_1\in A_1} u_1(a_1,a_2)p_1(a_1) = v_1, \forall a_2 \in \sigma_1$
$\sum_{a_1\in A_1} u_1(a_1,a_2)p_1(a_1) \leq v_1, \forall a_2 \notin \sigma_1$
$\sum_{a_1 \in A_1} p_2(a_2) = 1$
$p_1(a_2) \geq 0, \forall a_2 \in \sigma_1$
$p_1(a_2) = 0, \forall a_2 \notin \sigma_1$

We note that all strategies in a given support must be used in the mixed-strategy Nash equilibrium. The feasibility of this problem in comparison with the difficulty of finding Nash equilibria suggests that the main difficulty in finding Nash equilibria comes from the difficulty of searching through all possible combinations of supports for the action profiles in a game.

## Correlated Equilibrium

A correlated equilibrium is another type of equilibrium which is a superset of Nash equilibria. In addition to the strategies available to players, there can be a signal which allows players to coordinate their actions. A natural example of a correlated equilibirum is at a traffic junction. When the traffic light is red, drivers stop at an intersection, whereas if the light is green, they go on – this insures that there are no (or relatively few) traffic accidents. If there aren’t traffic signals, drivers must play a mixed strategy of going on and stopping in equilibrium, which would guarantee a non-trivial amount of accidents, given that people do drive with some probability.

More generally, a correlated equilibrium can be defined as follows:

A joint probability distribution $p^*$ on action profiles in A is a correlated equilibrium of a simultaneous-move game $(N,A,u)$ if for all agents $i$, and for actions $a_i \in A_i$ with $p^*(a_i) >0$

$\sum_{a_{-i}\in A_{\-i}} p^*(a_{-i} | a_i)u_i(a_i,a_{-i}) \geq \sum_{a_{-i}\in A_{-i}} p^*(a_{-i} | a_i) u_i (a_i',a_{-i})$

A Nash equilibrium is a special case of the correlated equilibrium, when $(p^*a_{-i}|a_i) = p^*(a_{-i})$. Interestingly, the generalization of Nash equilibrium to correlated equilibrium allows us to solve for equilibrium using an LP.

Maximize  Any objective function
Subject to:

$\sum_{a_{-i}\in A_{\-i}} p^*(a_{-i} | a_i)u_i(a_i,a_{-i}) \geq \sum_{a_{-i}\in A_{-i}} p^*(a_{-i} | a_i) u_i (a_i',a_{-i})$
$\forall i \in N, \forall a_i \in A_i, \forall a_i' \in A_i$
$\sum_{a\in A} p(a) = 1$
$p(a) \geq 0, \forall a \in A$.

It is interesting to note that the independence of each player’s action in a Nash equilibrium breaks the linearity of the first constraint in the LP above. Hence, it is the representation of all players’ strategies as a joint distribution which allows us to compute correlated equilibrium quickly.

## Sources

This blog post draws heavily from the forthcoming book Economics and Computation by David C. Parkes and Sven Seuken.