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.
3.
Regret:
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