Week 3 Flashcards
What is the best response?
For player i with all the opponent strategies fixed, the best response is a strategy which gives the highest payoff to player i
Can there be more than one best response strategy?
Yes
Is it always possible to find a best response to a fixed set of opponent strategies?
Finite space, yes.
Check all strategies play (one of) the best ones
Infinite space, no.
A game with no best response:
1. Player 1 chooses a positive real number X1
2. Player 2 chooses a positive real number X2
3. If X2 > X1 Player 1 wins
4. If X2 < X1 Player 2 wins
Optimal strategies: Each player needs to player the smallest real number greater than 0. No such number exists!
Describe a game with no best response
A game with no best response:
1. Player 1 chooses a positive real number X1
2. Player 2 chooses a positive real number X2
3. If X2 > X1 Player 1 wins
4. If X2 < X1 Player 2 wins
Optimal strategies: Each player needs to player the smallest real number greater than 0. No such number exists!
Define a Nash equilibrium
A strategy profile (s1, s2, s3, …, sk) for a game with k players, is a Nash equilibrium if each strategy is a best response to all of the others.
It is not a strategy; it is a choice of strategy for all players in the game
If the players are playing Nash, no player has any incentive to change it’s strategy unilaterally
For a two player, zero-sum game with perfect information, is the game solved if a Nash Equilibrium can be found?
Yes
Each is playing best response to the other
Find the Nash equilibrium(s) for
(1, -1) (2, -2)
(0, 0) (1, -1)
(1,-1)
Find the Nash equilibrium(s) for
(-1, 1) (1, -1)
(1, -1) (-1, 1)
There is no Nash Equilibrium
What is the strategy Player 1 (maximising player) picks in a Nash equilibrium
For each available strategy identifies the opponent strategy which gives the lowest payoff. Plays the strategy which maximises this.
What is the strategy Player 2 (minimising player) picks in a Nash equilibrium
For each available strategy identifies the opponent strategy which gives the highest payoff. Plays the strategy which minimises this.
Is mini-max a best-case analysis?
No it’s a worst-case analysis
The goal is to minimize the harm your opponent does to you
(rather than maximising your own benefit)
When does a strategy dominate another one?
A strategy s dominates a strategy s’ if the payoff of s against any opponent strategy is not less than that of s’ against the same opponent strategy, for all opponent strategies
For this game in normal form:
4 3 1 1
3 2 2 1
4 4 3 2
3 3 2 1
Where rows are player 1 and columns are player 2, which strategies dominate all others?
Player 1 strategy 3 (1-indexed)
Player 2 strategy 4 (1-indexed)
For this game in normal form:
2 -2 1 -1
0 0 1 0
1 2 1 0
Express the game after eliminating dominated strategies
0 (3rd row, 4th column, 1-indexed)
When may mixed strategies be needed?
Extensive form games with hidden information (e.g. poker)
Normal form games always have hidden information (the hidden strategy of the opponent(s).)