Nash equilibrium
- Algorithms course
- Expert
- Lesson 33/41
- 4 min
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.
Practice 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]])).
Starter code
def find_nash_equilibria(payoff_a, payoff_b):
# Find pure Nash equilibriaSample 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]]))Expected output
[(1, 1)]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Nash equilibrium concepts
| Term | Meaning |
|---|---|
pure strategy |
Single choice |
equilibrium |
Deviation useless |
player |
Picks strategy |
multiple equilibria |
Several solutions |
2 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 Correct answer
- If nobody plays
Explanation: An equilibrium holds when no player gains by unilateral deviation.
3 equilibrium append
if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
equilibria.____((i, j))if payoff_a[i][j] == best_a and payoff_b[i][j] == best_b:
equilibria.append((i, j))Explanation: append is used to add to a list.