CS7642_Week9

Question 1

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)

Answer 1

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.

Question 2

What is tit-for-tat strategy?

Answer 2

1. Co-operate on first round

2. Copy opponents previous move for every move after.

Question 3

What is the “Folk Theorem” idea in the context of repeated games?

Answer 3

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!”

Question 4

What is an “Implausible threat”?

Answer 4

Think of trying to rob someone with a stick of dynamite in an elevator.

Question 5

What is “subgame perfect”?

Answer 5

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.

Question 6

Pavlov is not subgame perfect? (True/False)

Answer 6

False, it is subgame perfect.

Question 7

Pavlov vs. Pavlov will never fall into mutual cooperation? (True/False)

Answer 7

False. It is subgame perfect. We’re essentially looking at whether we agree/disagree with what the other player did, and then acting accordingly.

Question 8

It is not known whether zero-sum stochastic games can be solved in polynomial time? (True/False)

Answer 8

True

Question 9

Zero-sum stochastic games and general-sum stochastic games can be treated as equivalent in terms of solving them? (True/False)

Answer 9

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.

Question 10

Correlated equilibria cannot be found in polynomial time? (True/False). What is the important feature that makes CE work?

Answer 10

False, they can be. It works because of a shared source of randomization.

Question 11

All mixed Nash are correlated so correlated equilibrium exist? (True/False)

Answer 11

True

Question 12

All convex combinations of mixed Nash are correlated? (True/False)

Answer 12

True

Question 13

COCO works well for more than two players? (True/False)

Answer 13

False, it really only works for two players.