**Exercise 4.2** Continuing the previous exercise, restrict now to feasible sets X that contain only 0-1 vectors—that is, each bidder either wins or loses. We can identify each feasible outcome with a “feasible set” of bidders (the winners). Assume that for every bidder i, there is an outcome in which i does not win. Myerson’s payment formula (3.5) dictates that a winning bidder pays her “critical bid”—the infimum of the bids at which she would continue to win.

Prove that, when S∗ is the set of winning bidders under the allocation rule (4.2) and i ∈ S∗, i’s critical bid equals the difference between (1) the maximum social welfare of a feasible set that excludes i; and (2) the social welfare j∈S∗\{i} vj of the bidders other than i in the chosen outcome S∗.

[In this sense, each winning bidder pays her “externality”—the welfare loss she imposes on others.]

**Exercise 4.5** Prove that the three-step greedy knapsack auction allocation rule in Section 4.2.2 is monotone. Does it remain monotone with the two optimizations discussed in the footnotes?

**Problem 4.1** Consider a variant of a knapsack auction in which both the valuation vi and the size wi of each bidder i are private. A mechanism now receives both bids b and reported sizes a from the bidders. An allocation rule x(b,a) now specifies the amount of capacity allocated to each bidder, as a function of the bids and reported sizes. Feasibility dictates that i=1 xi(b, a) ≤ W for every b and a, where W is the total capacity of the shared resource. We define the utility of a bidder i as vi − pi(b, a) if she gets her required capacity (i.e., xi(b, a) ≥ wi) and as −pi(b, a) otherwise. This is not a single-parameter environment.

Consider the following mechanism. Given bids b and reported sizes a, the mechanism runs the greedy knapsack auction of Section 4.2.2, taking the reported sizes a at face value, to obtain a subset of winning bidders and prices p. The mechanism concludes by awarding each winning bidder capacity equal to her reported size ai, at a price of pi; losing bidders receive and pay nothing. Is this mechanism DSIC? Prove it or give an explicit counterexample.

**Exercise 5.2** Compute the virtual valuation function of the following distributions.

(a) The uniform distribution on [0, a] with a > 0.

(b) The exponential distribution with rate λ > 0 (on [0, ∞)).

(c) The distribution given by F (v) = 1 − 1 / (v+1) on [0,∞), where (v+1) c > 0 is some constant.

**Exercise 5.5** Prove that for every single-parameter environment and regular valuation distributions F1,...,Fn, the virtual-welfare- maximizing allocation rule is monotone in the sense of Definition 3.6. Assume that ties are broken lexicographically with respect to some fixed total ordering over the feasible outcomes.

**Problem 5.1** This problem derives an interesting interpretation of a virtual valuation φ(v) = v −

Consider a strictly increasing distribution function F with a strictly positive density function f on the interval [0,vmax], with vmax < +∞

For a single bidder with valuation drawn from F, for q ∈ [0,1], define V (q) = F −1(1 − q) as the (unique) posted price that yields a probability q of a sale. Define R(q) = q·V (q) as the expected revenue obtained from a single bidder when the probability of a sale is q. The function R(q), for q ∈ [0,1], is the revenue curve of F. Note that R(0) = R(1) = 0.

1. (a) What is the revenue curve for the uniform distribution on [0, 1]?

2. (b) Prove that the slope of the revenue curve at q (i.e., R′(q)) is precisely φ(V (q)), where φ is the virtual valuation function for F.

3. (c) Prove that a distribution is regular if and only if its revenue curve is concave.

**Exercise 5.8** Repeat the previous exercise for sponsored search auctions (Example 3.3).