**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

**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__