Stat155 Game Theory - 2022 Fall - Homework 3: Algorithmic Mechanism Design and Revenue Maximizing
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).
