Game Theory Flashcards
In repeated games, the possibility of retaliation opens the door for _____?
Cooperation
What is the “Folk Theorem” in the context of game theory?
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
What is subgame perfect Nash equilibrium?
Always best response independent of history.
What is game theory?
Mathematics of conflicts of interest when trying to make choices.
Takes decision making from single agent to multi agent
What is the method for determining a strategy in a 2 person competitive game?
Minimax - i.e. consider the best response to the worst case
What is the fundamental result in game theory?
In a 2 player zero-sum deterministic game of perfect information…
Minimax === Maximin and there always exists an optimal pure strategy for each player
What is Von Neumann’s theory in game theory?
In a 2 player zero-sum NON-deterministic game of perfect information…
The fundamental theorem still holds and there is an optimal pure strategy
What is the difference between a pure strategy and a mixed strategy?
A mixed strategy is a distribution over all strategies (as opposed to choosing only one strategy)
How do we solve for a mixed strategy in a 2 player zero sum non-deterministic game of hidden information?
Set up (and solve) a system of equations for the probabilities of the strategies (find where the lines intersect)
What is a Nash equilibrium?
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
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.
True and it is the unique NE
True/False - A Nash Equilibrium will not necessarily survive elimination of strictly dominated strategies.
False
True/False - If n is finite and for all players the set of strategies is finite there must exist a pure strategy Nash Equilibrium.
False - But there does exists a mixed strategy NE
What does the tit-for-tat strategy imply about cooperation based on the time scale considered (i.e. gamma)?
In general that cooperation only makes sense on a long time scale and with low gamma we re still better off always defecting
How do you construct a best response for a finite state strategy?
We construct an MDP to represent it and then solve the MDP
True/False - An implausible threat can result in a subgame perfect NE
False
Construct a subgame perfect strategy for the repeated prisoners dilemma.
This is referred to as the Pavlov strategy:
Cooperate if agree, defect if disagree
Describe the computational folk theorem
For any 2-player bimatrix repeated game you can construct a subgame perfect NE in polynomial time.
What are the “nice” properties of zero-sum stochastic games?
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
What are the features of general-sum stochastic games?
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
What is a solution concept?
A rule for predicting how a game will be played.
e.g. Nash, subgame perfect, CoCo, correlated
What is a real life example of correlated equilibrium?
Traffic lights. We agree to follow what they say because it is better than alternative equilibria
What are the features of correlated equilibria?
- They can be found in poly time
- All mixed Nash are correlated
- All convex combinations of mixed Nash are correlated
Describe CoCo strategy
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.
What are the properties of coco?
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
What is the difference between mechanism design and “normal” game theory?
Mechanism design is how to design a game based on a given desired behavior.
