Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Problem Set 5

COMP3352 Algorithmic Game Theory (2022 Spring)

1.  (30 points)  Recall the games “Battle of the Sexes” and “Chicken Game” from our second lecture “Game Theory Basics”.

(a)  (15 points) For each game, find a mixed Nash equilibrium that is not a pure Nash. (b)  (15 points) For each game, find a correlated equilibrium that is not a mixed Nash.

2.  (30 points)  Consider selling m items through simultaneous first-price auctions. Recall that we have shown that the PoA of mixed Nash equilibria is at most 2.  Modify the analysis appropriately to show the same PoA bound for coarse correlated equilibria.

3.  (40 points)  Consider the following two-player game, where d > 1 > ,.

(a)  (10 points) List all pure Nash equilibria.

(b)  (15 points) Find a mixed Nash equilibrium that is NOT a pure one.

(c)  (15 points) Find a correlated equilibrium that is NOT a mixed Nash equilibrium.

(d)  (optional, 0 points) Find a coarse correlated equilibrium that is NOT a correlated equilibrium.