Computational Game Theory


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