Econ 106D: Final Exam

Problem 1: Third-Price Auction, Revisited (50 points)

Consider a third-price auction with N ≥ 3 bidders. This is a sealed-bid auction in which the highest bidder wins and pays the third-highest bid. There is no reserve price. Assume that bidders’ values are independently and uniformly distributed on [0, 20] (i.e., ˜vi ∼iid U[0, 20] for all bidders i = 1, . . . , N).

In Problem Set 4, we saw that this auction is not strategy-proof; in particular, it is not a dominant strategy for each bidder to bid his/her own value. In this problem, we explore this phenomenon in more detail.

Please answer the following questions. (If you find it necessary, you may make the additional assumption that N = 3 and still receive most of the credit for this problem.)

(a) (10 points) Provide a concrete example illustrating that truthful bidding is not a dominant strategy for bidder 1.

(Hint: It may be useful to consider the argument that we used in class to show that the second-price auction is strategy-proof, and to see where that argument breaks down for the third-price auction. In particular, find a value v1 for bidder 1, a bid b1 ≠ v1, and a profile of bids (b2, . . . , bN ) for the other bidders such that bidder 1 does better by bidding b1 than by bidding v1.)

(b) (20 points) Find a Nash equilibrium in which all bidders bid more than their true values.

(Hint 1: Consider symmetric equilibria in which all bidders use strategies of the form. b(v) = βv, where β ≥ 0 is a constant you need to solve for. The overall approach to solving for this equilibrium is similar to that from class for the first-price auction.)

(Hint 2: In the third-price auction—unlike in the first-price auction—bidder i does not know exactly how much he/she will pay conditional on winning. To compute bidder i’s expected payment conditional on winning, it may be useful to think about the second-order statistic among the remaining N − 1 bidders, i.e., the second highest value among all the bidders aside from i. It may also be helpful to recall that if x˜ ∼ U[0, b], then x˜ | [˜x ≤ c] ∼ U[0, c] for any c ≤ b. That is, for a uniform. random variable x˜, conditioning on the event that x˜ lies below a number c results in a new uniform. random variable on the “truncated support.”)

(c) (10 points) Provide intuition for why bidders bid more than their true values in the above equilibrium.

(Hint: It may be useful to recall the intuition for why bidders bid less than their true values in the first-price auction.)

(d) (10 points) In class, we saw that the second-price auction admits a “bidding ring equilibrium” in which bidder 1 bids some number b1 ≥ 20 regardless of his/her true value, while the other bidders i = 2, . . . , N all bid bi = 0 regardless of their true values. Is this strategy profile also a Nash equilibrium of the third-price auction?

Problem 2: First-Price Auction with Many Bidders (35 points)

Consider a first-price auction with N ≥ 2 bidders. Assume that bidders’ values are independently and uniformly distributed on [0, 173] (i.e., ˜vi ∼iid U[0, 173] for all bidders i = 1, . . . , N).

Please answer the following questions:

(a) (15 points) Find the bidding strategies in a symmetric, linear Nash equilibrium. (That is, a Nash equilibrium in which all bidders use the same strategy b(v) = βv, where β > 0 is a constant you need to solve for.)

(Hint: Mimic the two-bidder examples from class and Problem Set 4. Only one step of that derivation— determining how to write the probability that a given bid wins—requires real modification.)

(b) (10 points) Describe how the bidding strategies you found in part (a) change as N, the number of bidders, (i) increases and (ii) tends to infinity (N → ∞)? Provide economic intuition for your answers.

(c) (10 points) For fixed N, what is (i) the seller’s expected revenue and (ii) the expected bidder surplus? What happens to these objects as N → ∞? Provide economic intuition for your answers.

Problem 3: SPA with Uncertain Number of Bidders (25 points, 10 bonus)

In many real-world auction markets, neither the auctioneer nor the bidders know exactly how many bidders are participating in the auction. We can model this as follows. Let the number of bidders, N˜, be a random variable, and let pn = Pr(N˜ = n) denote the probability that there are n bidders. No one—neither the bidders nor the seller—knows the value of N˜. Each bidder i has a random value ˜vi ∼ U[0, 20] for the good. All of the bidders’ values, as well as the number of bidders, are independently distributed.

Consider a second-price auction (with no reserve price) in this setting. Please answer the following questions:

(a) (10 points) Find the bidding strategies in a symmetric, linear Nash equilibrium. (That is, a Nash equilibrium in which all bidders use the same strategy b(v) = βv, where β > 0 is a constant you need to solve for.)

(Hint: Do not attempt to do this mechanically. Think carefully about which β is likely to work—the answer does not depend on the distribution of N˜, and can be determined with little calculation.)

(b) (10 points) Consider two possible scenarios. In scenario (i), there is an equal chance of having 3 bidders and having 5 bidders (i.e., p3 = p5 = 1/2), so that the expected number of bidders is 4. In scenario (ii), there are 4 bidders for certain (i.e., p4 = 1). Does scenario (i) or scenario (ii) generate a higher expected revenue for the seller?

(c) (5 points) Discuss implications of your answer to part (b) for the design of real-world auctions.

(d) (Bonus: 10 points) Consider the following generalization of the setup from part (b). In scenario (i), N˜ has an arbitrary distribution with mean E[N˜] = µ, which is an integer. In scenario (ii), there are µ bidders for certain (i.e., pµ = 1). Does scenario (i) or scenario (ii) generate a higher expected revenue for the seller?

Problem 4: School Choice (40 points)

Consider a school choice market with four students {s1, ..., s4} and four schools {A, B, C, D}.

Students’ preferences are as follows:

s1 : A B C D

s2 : C B D A

s3 : B C D

s4 : C B D A

Schools’ priorities (which you can think of as having been set by the school district) are as follows:

A : s1 > s2 > s3 > s4

B : s2 > s1 > s3 > s4

C : s3 > s1 > s2 > s4

D : s4 > s1 > s2 > s3

Each school has a single slot (“unit capacity”).

Please answer the following questions:

(a) (4 points) Consider the allocation {(s1, A),(s2, B),(s3, D),(s4, C)}. Is it Pareto efficient? Is it stable? How should we interpret stability here? Justify your answers.

(b) (12 points) Suppose that the school seats are allocated via Serial Dictatorship in which students move in the order s3, s1, s4, s2. For each of the following, justify your answer:

(i) What is the resulting assignment? (Assume truthful reporting for this part.)

(ii) Is the assignment Pareto efficient? Is it stable?

(iii) Find a Nash equilibrium of the preference-reporting game between students.

(c) (12 points) Suppose now that school seats are allocated to students via the student-proposing DA algorithm. For each of the following, justify your answer:

(i) What is the resulting assignment of school seats to students? (Assume truthful reporting for this part.)

(ii) Is the assignment Pareto efficient? Is it stable?

(iii) Find a Nash equilibrium of the preference-reporting game between students.

(d) (12 points) Finally, suppose that school seats are allocated via the Boston Mechanism. For each of the following, justify your answer:

(i) What is the resulting assignment? Describe the run of the algorithm. (Assume truthful reporting for this part.)

(ii) Is the assignment Pareto efficient? Is it stable?

(iii) Find two different Nash equilibria of the preference-reporting game between students that lead to different assignments (and provide an argument for why they are Nash equilibria).