CS294:  Games and the Internet

First Problem Set    Due:  September 29, in class

Problem 1:   Recall the game with irrational Nash equilibrium due to John Nash, see the lecture notes or go back to Nash's paper in the annals of math, volume 54.

•	Why is this a three-person game?  Give explicitly the strategy space of each player.
•	Prove that Player 1 should never open when her hand is low, and Players 2 and 3 should never call when their hands are low.  (In the draft notes "a zero" should be "a one", corrected now).

Problem 2:  Recall the discussion of correlated equilibria in connection with the Chicken game, from the notes.   Give the two-dimensional region that is set of all payoff combinations that can be achieved by correlated equilibria.  How does it compare with the set of individually rational combinations?

Problem 3:   What are the Nash equilibria of this 3-person game?  (Players choose row, column, and table.)

  4 6 5	  0 0 0 
  0 0 0	  0 0 0

  0 0 0	  6 5 4
  5 4 6	  0 0 0

Problem 4:   Consider the problem of finding a local maximum in the max-cut problem (that is, a cut whose total weight cannot be improved by swapping one node).  Suppose that we know that all local maxima have weights between M and 2M.  

Suppose now that you round the edge weights to the nearest multiple of ceiling(epsilon M/|E|). Show that the local optimum found this way is an epsilon-local optimum.  What is the time complexity of this algorithm?

Suppose now that you don’t know this M.  How can you go about finding an approximate local optimum?  (Hint:  Suppose M is the initial weight, and if you find out that it is not, re-round.) 

Problem 5:  See 
http://www.cs.berkeley.edu/~christos/games03/problem5.ps

Problem 6:  Consider a congestion game with n players, m resources, where all players have m strategies/paths that are single resources (that is, the network is m parallel edges).  Each edge has, of course, a different delay function, a total of mn numbers.  Give a simple algorithm for finding a pure Nash equilibrium.  (Hint:  Sort the mn numbers.)

Problem 7 (No credit will be received without an answer to this one):  Identify two or three topics (you can use the ones on "Tim's list" or any other game-theory related topic of your liking) that you want to explore.  In at least one, mention the angle of your investigation.  When will you be ready to speak on one of them?  (NB:  Seminars late in the semester will be reserved for more ambitious projects.)