Game Theory

Question 1

In repeated games, the possibility of retaliation opens the door for _____?

Answer 1

Cooperation

Question 2

What is the “Folk Theorem” in the context of game theory?

Answer 2

Describes the set of payoffs that can result from Nash Strategies in REPEATED games.
Any feasible payoff profile that strictly dominates the minmax/security level profile can be realized as a Nash equilibrium payoff profile, with sufficiently large discount factor

Question 3

What is subgame perfect Nash equilibrium?

Answer 3

Always best response independent of history.

Question 4

What is game theory?

Answer 4

Mathematics of conflicts of interest when trying to make choices.
Takes decision making from single agent to multi agent

Question 5

What is the method for determining a strategy in a 2 person competitive game?

Answer 5

Minimax - i.e. consider the best response to the worst case

Question 6

What is the fundamental result in game theory?

In a 2 player zero-sum deterministic game of perfect information…

Answer 6

Minimax === Maximin and there always exists an optimal pure strategy for each player

Question 7

What is Von Neumann’s theory in game theory?

In a 2 player zero-sum NON-deterministic game of perfect information…

Answer 7

The fundamental theorem still holds and there is an optimal pure strategy

Question 8

What is the difference between a pure strategy and a mixed strategy?

Answer 8

A mixed strategy is a distribution over all strategies (as opposed to choosing only one strategy)

Question 9

How do we solve for a mixed strategy in a 2 player zero sum non-deterministic game of hidden information?

Answer 9

Set up (and solve) a system of equations for the probabilities of the strategies (find where the lines intersect)

Question 10

What is a Nash equilibrium?

Answer 10

A set of strategies, such that given the option to switch strategies no player would choose to deviate from the strategy.
This applies for both pure and mixed strategies

Question 11

True/False - In the n-player pure strategy game, if elimination of strictly dominated strategies eliminates all but one combination, that combination is a Nash Equilibrium.

Answer 11

True and it is the unique NE

Question 12

True/False - A Nash Equilibrium will not necessarily survive elimination of strictly dominated strategies.

Answer 12

False

Question 13

True/False - If n is finite and for all players the set of strategies is finite there must exist a pure strategy Nash Equilibrium.

Answer 13

False - But there does exists a mixed strategy NE

Question 14

What does the tit-for-tat strategy imply about cooperation based on the time scale considered (i.e. gamma)?

Answer 14

In general that cooperation only makes sense on a long time scale and with low gamma we re still better off always defecting

Question 15

How do you construct a best response for a finite state strategy?

Answer 15

We construct an MDP to represent it and then solve the MDP

Question 16

True/False - An implausible threat can result in a subgame perfect NE

Answer 16

False

Question 17

Construct a subgame perfect strategy for the repeated prisoners dilemma.

Answer 17

This is referred to as the Pavlov strategy:

Cooperate if agree, defect if disagree

Question 18

Describe the computational folk theorem

Answer 18

For any 2-player bimatrix repeated game you can construct a subgame perfect NE in polynomial time.

Question 19

What are the “nice” properties of zero-sum stochastic games?

Answer 19

Value iteration works
Minimax-Q converges
There exists a unique solution to Q*
Policies can be computed independently 
Update efficient
Q functions are sufficient to specify policy

Question 20

What are the features of general-sum stochastic games?

Answer 20

Value iteration doesn’t work
Nash-Q doesn’t converge
No unique solutions to Q*
Policies cannot be computed independently
Update is not efficient (PPAD difficult)
Q functions are not sufficient to specify policy

Question 21

What is a solution concept?

Answer 21

A rule for predicting how a game will be played.

e.g. Nash, subgame perfect, CoCo, correlated

Question 22

What is a real life example of correlated equilibrium?

Answer 22

Traffic lights. We agree to follow what they say because it is better than alternative equilibria

Question 23

What are the features of correlated equilibria?

Answer 23

1. They can be found in poly time
2. All mixed Nash are correlated
3. All convex combinations of mixed Nash are correlated

Question 24

Describe CoCo strategy

Answer 24

Making side payments from excess reward to encourage better outcomes.

Compute maximax and minimax for the game and share the excess reward from the difference.

Question 25

What are the properties of coco?

Answer 25

Efficiently computable
Utility maximizing
Decompose game into sum of two games
UniqueCan be extended to stochastic games (coco-Q, non-expansion but still converges)
Not necessarily equilibrium (needs to be binding)
Doesn’t generalize to more than 2 players

Question 26

What is the difference between mechanism design and “normal” game theory?

Answer 26

Mechanism design is how to design a game based on a given desired behavior.