CS7642_Week9 Flashcards
(13 cards)
Iterated games (e.g. iterated prisoner’s dilemma), what the players did in the last round matters (when we know how many rounds are going to be played)? (True/False)
False. Since the only thing that is rational in any round is to defect, then it follows that each round is independent - the players should always choose to defect.
What is tit-for-tat strategy?
- Co-operate on first round
2. Copy opponents previous move for every move after.
What is the “Folk Theorem” idea in the context of repeated games?
General Idea - in repeated games the possibility of retaliation opens door for cooperation
Formal defininition: Any feasible payoff profile that strictly dominates the minimax/security level profile can be realized as a Nash equilibrium payoff profile, with a sufficiently large discount factor.
Proof: if it strictly dominates the minmax profile, can use it as a threat. Better off doing what you are told!”
What is an “Implausible threat”?
Think of trying to rob someone with a stick of dynamite in an elevator.
What is “subgame perfect”?
If I could look back at history of a set of actions I took when playing a game, and realize that by changing any portion of the sequence I could do better, then I’m not subgame perfect. It IS a Nash Equilibrium.
Pavlov is not subgame perfect? (True/False)
False, it is subgame perfect.
Pavlov vs. Pavlov will never fall into mutual cooperation? (True/False)
False. It is subgame perfect. We’re essentially looking at whether we agree/disagree with what the other player did, and then acting accordingly.
It is not known whether zero-sum stochastic games can be solved in polynomial time? (True/False)
True
Zero-sum stochastic games and general-sum stochastic games can be treated as equivalent in terms of solving them? (True/False)
False. Everything that worked for the zero-sum case breaks down in the general-sum case, e.g. value iteration doesn’t work, Nash-Q doesn’t converge, etc.
Correlated equilibria cannot be found in polynomial time? (True/False). What is the important feature that makes CE work?
False, they can be. It works because of a shared source of randomization.
All mixed Nash are correlated so correlated equilibrium exist? (True/False)
True
All convex combinations of mixed Nash are correlated? (True/False)
True
COCO works well for more than two players? (True/False)
False, it really only works for two players.
