CS 700 Computational Mechanism DesignHomework 1: Game Theory and Intro Mechanism DesignFall 2008Prof. David ParkesHarvard University and EPFLSeptember 23, 2008Due: Tuesday September 30, 2008, at the beginning of class. You may use any sources thatyou want, but you must cite the sources that you use. You can also work in pairs– just list the person youwork with. If you already have advanced level economics please come chat with me about analternative homework. Work hard on making the proofs clear, concise, and easy to read.Total points: 1401. (10 pts) (a) In the following strategic-form game, what strategies survive iterated elimination of strictly-dominated strategies?(b) What are the pure strategy Nash eq.?(c) Find a non-trivial (support > 1) mixed-strategy NE.L C RT 2,0 1,1 4,2M 3,4 1,2 2,3B 1,3 0,2 3,02. (10 pts) Two agents are bargaining over how to split a dollar. Each simultaneously names the share itwould like to have, s1and s2, where 0 ≤ s1, s2≤ 1. If s1+ s2≤ 1, then the agents receive the sharesthey named; if s1+ s2> 1, then the agents receive zero. What are the pure strategy Nash eq.?3. (5 pts) Show that there are no (non-trivial) mixed-strategy Nash eq. (i.e. with support greater thanone) in the Prisoners’ Dilemma game.C DC 1,1 -1,2D 2,-1 0,04. (15 pts) Battle of the Sexes. Pat and Chris must choose to go for dinner or go to the movies. Bothplayers would rather spend the evening together than apart, but Pat would rather the go for dinner,and Chris would rather they go to the movies.ChrisDinner MoviePat Dinner 2,1 0,0Movie 0,0 1,2(a) Find three Nash equilibria of this game.(b) Let (q, 1 − q) be the mixed strategy in which Pat plays Dinner with prob. q, and let (r, 1 − r) bethe mixed strategy in which Chris plays Dinner with prob. r. By first determining the best-responsecorrespondences q∗(r) and r∗(q), or otherwise, find the mixed-strategy Nash equilibrium.15. (20 pts) Iterated elimination of strictly dominated strategies.(a) (10 pts) Prove that if strategies, s∗= (s∗1, . . . , s∗n), are a Nash eq. in a strategic-form gameG =< N, (Si), (ui) >, then they survive iterated elimination of strictly dominated strategies. (hint)By contradiction, assume that one of the strategies in the Nash eq. is eliminated by iterated eliminationof strictly dominated strategies.(b) (10 pts) Prove that if the process of iterated elimination of strictly dominated strategies in gameG =< N, (Si), (ui) > results in a unique strategy profile, s∗= (s∗1, . . . , s∗n), that this is a Nash eq. ofthe game. (hint) By contradiction, suppose there exists some agent i for which si6= s∗iis preferredover s∗i, and show a contradiction with the fact that siwas eliminated.6. (20 pts) Consider a problem in which the outcome space, O ⊂ R, and each agent i, with type θi,has single-peaked preferences, ui(θi, o) over outcomes. In particular, each agent, i, with type θi, hasa peak, pi(θi) ∈ O, such that for any d0, d ∈ R for which d0< d ≤ p(θi) or p(θi) ≤ d < d0, thenui(θi, d) > ui(θi, d0) (see p.10–11, M.Jackson “Mechanism Theory” reading).(a) (10 pts) Show that the “median selection” mechanism, in which each agent declares its peak and themechanism selects the median (with a tie break in the case of an even number of agents) is strategyproof,and implements a Pareto Optimal outcome.(b) (5 pts) Let n denote the number of agents. Suppose, in addition, that the mechanism designer canposition n − 1 “phantom peaks” before the peaks from the agents are received. Why does the medianselection mechanism combined with 2n − 1 peaks remain strategyproof?(c) (5 pts) In combination with the phantom peaks, the median selection mechanism can implement arich variety of outcomes. Describe a method to position the peaks to implement the kth order statisticof the peaks announced by agents, for any 1 ≤ k ≤ n. (i.e. implement the outcome at the kth largestpeak)7. (10 pts) [Quite easy.] Show that if f : V → O is truthfully implementable in dominant strategieswhen the set of possible types is Vifor i = 1, . . . , N [i.e. the direct revelation mechanism, M = (V, f ),is strategyproof], then when each agent i’s set of possible types isˆVi⊂ Vi(for i = 1, . . . , N ) the socialchoice functionˆf :ˆV → O satisfyingˆf(v) = f(v) for all v ∈ˆV is truthfully implementable in dominantstrategies.8. (15 pts) Consider the design of a mechanism for a simple double auction with one seller (agent 1), witha single item, and one buyer (agent 2). The outcome of the mechanism defines an allocation, (x1, x2),where xi∈ {0, 1} and xi= 1 if agent i receives the item in the allocation, and payments (p1, p2) by theagents. Let videnote the value of agent i for the item, and suppose quasilinear preferences, so thatui(xi, pi) = xivi− piis the utility of agent i for outcome (x1, x2, p1, p2).(a) (10 pts) Specify the Vickrey-Clarke-Groves mechanism for the problem; i.e. define the strategyspace, the rule to select the allocation based on agent strategies, and the rule to select the paymentsbased on agent strategies. [Don’t just give the general formula: write a succinct description for thisapplication.](b) (5 pts) Provide a simple example to show that the VCG mechanism for a double auction runs ata deficit.9. (25 pts) Consider a problem with three advertising slots (slots 1, 2 and 3) and N bidders. Theprobability of a click is p1, γp1, γ2p1in slots 1, 2 and 3 for γ ∈ (0, 1) (for all advertisers). Biddersi ∈ N have value vi> 0 for a click, independent of the slot from which a click is received. Derive adescription of the VCG mechanism for this problem (i.e., do not just the generic equations.) You canassume that |N | > 3. Specifically,(a) Describe a (simple!) algorithm for determining how to allocate adverts to slots.(b) Provide an equation for determining the per-click price for an advertiser in slot 1, slot 2 and slot 3.2[Hint: think about the problem as one of allocating a slot not a click, working with expected values.Finally, to determine the per-click price derive a price that is equal, in expectation, to the VCG paymentfor receiving a slot.](c) Compare the per-click price to that in a “Generalized second price auction” in which advertisersare allocated to slots in order of bid price and the price charged is the smallest bid amount for whichan advertiser would retain the same slot. What do you notice?10. (10 pts) Consider a problem with alternatives A and |A|