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).)
What is a mixed strategy?
A strategy for a player in which:
- plays probabilistic combination of pure strategies
- receives a probabilistic combination of payoffs
How do you express a mixed strategy in normal form?
Assign probability qi to the pure strategy i
which 0<=q<=1 and the sum of qi for all i is 1
Choose strategy i with probability qi
Get the appropriate payoff with probability qi
How do you express a mixed strategy in extensive form?
At each node where the player has a decision, assign a probability function to each of the possible choices
What did Von Neumann discover about zero-sum games with perfect information?
They all have solutions which minimise the maximum losses for the players, but mixed strategies may be required
Von Neumann discovered game theory as a discipline.
What type of game is guaranteed to have at least 1 type of Nash equilibrium (as discovered by Nash)
(Some will involve mixed strategies)
Every game with a finite number of players in which each player has a finite number of pure strategies.
(Some will involve mixed strategies)
How can you find pure-strategy Nash equilibria in two-player zero-sum games with no chance?
- Search over all strategy pairs
- Use the mini-max method
- Use dominance
What is the best response strategy?
A best response strategy is the strategy for a given player which yields the highest payoff to that player with the strategies of all the other players held fixed
What does unilaterally mean in the definition of the Nash Equilibrium?
as long as all the other strategies remain fixed
Does this game:
(-1, 1), (1, -1)
(1, -1), (-1, 1)
have a mini-max solution? Does it have a Nash Equilibria?
No
What is a mixed strategy Nash Equilibrium?
Probabilistic combinations of pure strategies.
Mixed strategies are needed only for games with hidden information
What is the best method to find Nash equilibria in general sum games? What is it’s complexity?
The Lemke-Howson algorithm, can be exponential in time
What is the best method to find Nash equilibria in zero sum games?
Can solved using linear programming
Two brothers, Daniel (older) and Eric (younger) go to the same school
There are two cafes Red and Blue
Donald wants to be in a different cafe from Eric
Eric wants to be in the same cafe as Donald
Write the normal form for this game
Eric
(-1, 1) (1, -1)
Donald (1, -1) (-1, 1)
Two brothers, Daniel (older) and Eric (younger) go to the same school
There are two cafes Red and Blue
Donald wants to be in a different cafe from Eric
Eric wants to be in the same cafe as Donald
(same game as previous cards)
Optimise Donald’s decision, with what probability should he choose strategy 1 (Red)
50% of the time
Why should the expected payoffs be equal when optimising a decision?
If they are not equal:
- Eric will have a pure strategy best response which will be higher
If they are equal:
- Eric will get the same payoff, no matter what strategy he uses
- Eric will have no incentive to unilaterally deviate from whatever he does
Two brothers, Daniel (older) and Eric (younger) go to the same school
There are two cafes Red and Blue
Donald wants to be in a different cafe from Eric
Eric wants to be in the same cafe as Donald
(same game as previous cards)
What is the Nash equilibrium?
Donald and Eric both choose their lunch cafe independently with a probability of 0.5.
Neither has an incentive to unilaterally deviate since their payoff will not change
What are the interesting common features of mixed strategy Nash Equilibria?
If one player plays its component of the mixed Nash equilibrium, the payoff is indifferent to what the other player does
The other player must also play its component of the Nash equilibrium to force the first player to play its component and not take advantage
Write the 2-card tiny poker game in normal form
See slides
