Algorithms
Nash equilibrium
Concept of Nash equilibrium.
Nash equilibrium
A Nash equilibrium is a strategy profile where no player can improve by unilaterally changing their strategy. Each player is content with their strategy given the others' strategies.
A game may have multiple Nash equilibria. In pure-strategy equilibria, each player picks a single strategy.
This concept is central to game theory and is used from economics to biology.
Finding pure equilibria
To find pure Nash equilibria in a two-player game, we scan each cell. A cell (i,j) is an equilibrium if:
A's payoff is the maximum in column j; B's payoff is the maximum in row i. If both conditions hold, (i,j) is an equilibrium.
In two-player zero-sum games, this equilibrium coincides with the minimax value.
Exercise find_nash_equilibria function
Write find_nash_equilibria(payoff_a, payoff_b). Return the list of pure equilibrium cells. Print [(1, 1)] with print(find_nash_equilibria([[3, 0], [5, 1]], [[3, 5], [0, 1]])).
Show example solution
def find_nash_equilibria(payoff_a, payoff_b):
# Find pure Nash equilibria
n = len(payoff_a)
equilibria = []
for i in range(n):
for j in range(n):
best_a = max(payoff_a[r][j] for r in range(n))
best_b = max(payoff_b[i][c] for c in range(n))
if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
equilibria.append((i, j))
return equilibria
print(find_nash_equilibria([[3, 0], [5, 1]], [[3, 5], [0, 1]]))
Test yourself
-
Nash equilibrium concepts
- pure strategy
- Single choice
- equilibrium
- Deviation useless
- player
- Picks strategy
- multiple equilibria
- Several solutions
-
When is a Nash equilibrium valid?
if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
- If only A plays their best
- If only B plays their best
- If both players play their best
- If nobody plays
Show answer
If both players play their best — An equilibrium holds when no player gains by unilateral deviation.
-
equilibrium append
if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
equilibria.____((i, j))
Show answer
if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
equilibria.append((i, j))
Next lesson: Parallel algorithms
