CPS 296.2 - Computational Game Theory and Mechanism DesignHomework 3 (due 11/21)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. (Stochastic games.)Consider the following two-state zero-sum stochastic game with discountfactor .9 (i.e. you care about the next period only 90% as much as you careabout the current period). (Each of the matrices corresponds to a state.)30, -30 0, 0.4 .40, 0 20, -20.4 .4-1, 1 -1, 1.8 0-2, 2 0, 0.9 0Each entry of each matrix gives the utilities for the players, as well as theprobability of transitioning to the other state given that this entry was played.For example, if in state 1, (U, L) is played, then the next period the game willbe in state 2 with probability .4 (and in state 1 with probability .6).(30 points.) Find an equilibrium of this game in stationary strategies. Youshould give each player’s strategy for each state, as well as the value of eachstate to player 1. You are allowed to solve this game by computer (e.g. bycoding up Shapley’s algorithm), but it should be possible to solve it by hand, ifyou think about the game carefully.2. (Coalitional games.)Consider again the archaic Babylonian Talmud game from class. Again, thewives have claims of 100, 200, and 300, respectively. Now suppose that theestate that the husband leaves behind is 250.2a. (10 points.) Write down the characteristic function of the game. Thatis, for every nonempty subset of wives, write down the value of that subset.Remember that each coalition can choose to get 0, or to pay off everyone outsidethe coalition in full and divide the remainder of the estate. (Be careful – therest of the question depends on this!)2b. (10 points.) How much does the Shapley value give to each wife?2c. (10 points.) Is the Shapley value outcome in the core? Why?2d. (10 points.) How much does the nucleolus give to each wife? Writedown the list of excesses for the nucleolus in decreasing order, and argue why itis impossible to better. (This question will probably require you to play aroundwith the payoffs a little to find the nucleolus.)12e. (0 points.) Do you believe that the Talmud would have recommendedthe nucleolus for this example? Why (not)?3. (Using false names in a combinatorial auction.)Consider a combinatorial auction with free disposal that uses the GVA mech-anism. In this auction, all but one of the bidders are well-behaved—they onlyuse one account. The false-name bidder can use an unlimited number of falsenames, and knows the bids of the well-behaved bidders.(30 points.) Prove the following result: the false-name bidder can obtainall items for free if and only if no item receives a (positive) singleton bid froma well-behaved bidder. Be precise and
View Full Document
Unlocking...