Published: September 4, 2012
Abstract: [Plain Text Version]
We present the first approximation algorithms for designing revenue-optimal incentive-compatible mechanisms in the following setting: There are multiple (heterogeneous) items, and bidders have arbitrary demand and budget constraints (and additive valuations). Furthermore, the type of a bidder (which specifies her valuations for each item) is private knowledge, and the types of different bidders are drawn from publicly known mutually independent distributions. Our mechanisms are surprisingly simple.
First, we assume that the type of each bidder is drawn from a discrete distribution with polynomially bounded support size. This restriction on the type-distribution, however, allows the random variables corresponding to a bidder's valuations for different items to be arbitrarily correlated. In this model, we describe a sequential all-pay mechanism that is truthful in expectation and Bayesian incentive compatible. The outcome of our all-pay mechanism can be computed in polynomial time, and its revenue is a $4$-approximation to the revenue of the optimal truthful-in-expectation Bayesian incentive-compatible mechanism.
Next, we assume that the valuations of each bidder for different items are drawn from mutually independent discrete distributions satisfying the monotone hazard-rate condition. In this model, we present a sequential posted-price mechanism that is universally truthful and incentive compatible in dominant strategies. The outcome of the mechanism is computable in polynomial time, and its revenue is a $O(1)$-approximation to the revenue of the optimal truthful-in-expectation Bayesian incentive-compatible mechanism. If the monotone hazard-rate condition is removed, then we show a logarithmic approximation, and we complete the picture by proving that no sequential posted-price scheme can achieve a sub-logarithmic approximation. Finally, if the distributions are regular, and if the space of mechanisms is restricted to sequential posted-price schemes, then we show that there is a $O(1)$-approximation within this space. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles.
A preliminary version of this paper appeared in STOC 2010.
Licensed under a Creative Commons Attribution License (CC-BY)