Homework number 3
1. Potential games
a. Build a potential function for the Prisoner Dilemma game.
b. Show that there is no potential function for the matching pennies game. (Do a direct proof for the potential function, not by arguing there is no deterministic Nash!)
2. Repeated Game: Consider playing matching pennies in a repeated game of T stages.
a. When the opponent is a deterministic automata with N states. Show that there is a strategy that always wins, and can be implemented using N states.
b. Show that you can implement the minmax strategy by using a stochastic policy that selects between deterministic automata, each of size T.
a. Show that the swap regret is at most N times the internal regret for an sequence of losses. (Recall that the internal regret limits the functions F(.) to change only a single action.)
b. Show an example where the swap regret is unbounded with respect to the external regret. (There is an example that uses only 3 actions, has zero external regret and swap regret linear in T.)
The homework is due June 1