Week 3 Flashcards

1
Q

What is the best response?

A

For player i with all the opponent strategies fixed, the best response is a strategy which gives the highest payoff to player i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Can there be more than one best response strategy?

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is it always possible to find a best response to a fixed set of opponent strategies?

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Describe a game with no best response

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define a Nash equilibrium

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

For a two player, zero-sum game with perfect information, is the game solved if a Nash Equilibrium can be found?

A

Yes
Each is playing best response to the other

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Find the Nash equilibrium(s) for
(1, -1) (2, -2)
(0, 0) (1, -1)

A

(1,-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Find the Nash equilibrium(s) for
(-1, 1) (1, -1)
(1, -1) (-1, 1)

A

There is no Nash Equilibrium

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the strategy Player 1 (maximising player) picks in a Nash equilibrium

A

For each available strategy identifies the opponent strategy which gives the lowest payoff. Plays the strategy which maximises this.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the strategy Player 2 (minimising player) picks in a Nash equilibrium

A

For each available strategy identifies the opponent strategy which gives the highest payoff. Plays the strategy which minimises this.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Is mini-max a best-case analysis?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

When does a strategy dominate another one?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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?

A

Player 1 strategy 3 (1-indexed)
Player 2 strategy 4 (1-indexed)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

0 (3rd row, 4th column, 1-indexed)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

When may mixed strategies be needed?

A

Extensive form games with hidden information (e.g. poker)

Normal form games always have hidden information (the hidden strategy of the opponent(s).)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a mixed strategy?

A

A strategy for a player in which:
- plays probabilistic combination of pure strategies
- receives a probabilistic combination of payoffs

17
Q

How do you express a mixed strategy in normal form?

A

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

18
Q

How do you express a mixed strategy in extensive form?

A

At each node where the player has a decision, assign a probability function to each of the possible choices

19
Q

What did Von Neumann discover about zero-sum games with perfect information?

A

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.

20
Q

What type of game is guaranteed to have at least 1 type of Nash equilibrium (as discovered by Nash)

(Some will involve mixed strategies)

A

Every game with a finite number of players in which each player has a finite number of pure strategies.

(Some will involve mixed strategies)

21
Q

How can you find pure-strategy Nash equilibria in two-player zero-sum games with no chance?

A
  1. Search over all strategy pairs
  2. Use the mini-max method
  3. Use dominance
22
Q

What is the best response strategy?

A

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

23
Q

What does unilaterally mean in the definition of the Nash Equilibrium?

A

as long as all the other strategies remain fixed

24
Q

Does this game:
(-1, 1), (1, -1)
(1, -1), (-1, 1)

have a mini-max solution? Does it have a Nash Equilibria?

A

No

25
Q

What is a mixed strategy Nash Equilibrium?

A

Probabilistic combinations of pure strategies.

Mixed strategies are needed only for games with hidden information

26
Q

What is the best method to find Nash equilibria in general sum games? What is it’s complexity?

A

The Lemke-Howson algorithm, can be exponential in time

27
Q

What is the best method to find Nash equilibria in zero sum games?

A

Can solved using linear programming

28
Q

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

A

Eric
(-1, 1) (1, -1)
Donald (1, -1) (-1, 1)

29
Q

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)

A

50% of the time

30
Q

Why should the expected payoffs be equal when optimising a decision?

A

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

31
Q

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?

A

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

32
Q

What are the interesting common features of mixed strategy Nash Equilibria?

A

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

33
Q

Write the 2-card tiny poker game in normal form

A

See slides