CPS 296.2 - Computational Game Theory and Mechanism DesignHomework 1 (due 9/14)Note the rules for assignments on the course web page. Show all your work,but circle your final answer. Contact Vince ([email protected]) with anyquestions.1. (Risk attitudes.) Bob is making plans for Spring Break. He most prefersto go to Cancun, a trip that would cost him $2000. Another good option isto go to Miami, which would cost him only $1000. Bob is really excited aboutSpring Break and cares about nothing else in the world right now. As a result,Bob’s utility u as a function of his budget b is given by:• u(b) = 0 for b < $1000;• u(b) = 1 for $1000 ≤ b < $2000;• u(b) = 2 for b ≥ $2000.Bob’s budget right now is $1500 (which would give him a utility of 1, for goingto Miami).Bob’s wealthy friend Alice is aware of Bob’s predicament and wants to offerhim a “fair gamble.” Define a fair gamble to be a random variable with expectedvalue $0. An example fair gamble (with two outcomes) is the following: $-150with probability 2/5, and $100 with probability 3/5. If Bob were to accept thisgamble, he would end up with $1350 with probability 2/5, and with $1600 withprobability 3/5. In either case, Bob’s utility is still 1, so Bob’s expected utilityfor accepting this gamble is (2/5) · (1) + (3/5) · (1) = 1.a (5 points). Find a fair gamble with two outcomes that would strictlyincrease Bob’s expected utility.b (5 points). Find a fair gamble with two outcomes that would strictlydecrease Bob’s expected utility.2. (Normal-form games.)a (15 points). The following game has a unique Nash equilibrium. Findit, and prove that it is unique. (Hint: look for strict dominance.)3, 1 1, 2 4, 00, 4 0, 4 3, 51, 2 2, 1 4, 01b (15 points). Construct a single 2 × 2 normal-form game that simultane-ously has all four of the following properties.1. The game is not solvable by weak dominance (at least one player does nothave a weakly dominant strategy).2. The game is solvable by iterated weak dominance (so that one pure strat-egy per player remains).3. In addition to the iterated weak dominance solution (which is a Nashequilibrium), there is a second pure-strategy Nash equilibrium.4. Both players strictly prefer the second equilibrium to the first.(Hints: the second pure-strategy equilibrium should not be strict; the pure-strategy equilibria should be in opposite corners of the matrix.) If you cannotget all four properties, construct an example with as many of the properties asyou can.c (15 points). Consider the following game:3, 3 1, 44, 1 0, 0Find a correlated equilibrium that places positive probability on all entries ofthe matrix, except the lower-right hand entry. Try to maximize the probabilityin the upper-left hand entry.3. (Extensive-form games.) Consider the game below.4, 3 3, 4 3, 4 4, 3 5, 2 1, 1Player 1Player 2Player 2LMRL R RL L RFigure 1: An extensive-form game with imperfect information.a (15 points). Give the normal-form representation of this game.b (15 points). Give a Nash equilibrium where player 1 sometimes plays left.(Remember that you must specify each player’s strategy at every informationset.)c (15 points). Characterize the subgame perfect equilibria of the game.(Remember that you must specify each player’s strategy at every
View Full Document
Unlocking...