Prior-Independent Optimal Auctions

ABSTRACT

Auctions are widely used in practice. While also extensively studied in the literature, most of the developments rely on significant assumptions about common knowledge on the seller and buyers' sides. In this work, we study the design of optimal prior-independent selling mechanisms. In particular, the seller faces buyers whose values are drawn from an unknown distribution, and only knows that the distribution belongs to a particular class. We analyze a competitive ratio objective, in which the seller attempts to optimize the worst-case fraction of revenues garnered compared to those of an oracle with knowledge of the distribution. Our results are along two dimensions. We first characterize the structure of optimal mechanisms. Leveraging such structure, we then establish tight lower and upper bounds on performance, leading to a crisp characterization of optimal performance for a spectrum of families of distributions. In particular, our results imply that a second price auction is an optimal mechanism when the seller only knows that the distribution of buyers has a monotone increasing hazard rate, and guarantees at least 71.53% of the optimal revenue against any distribution within this class. Furthermore, a second price auction is near-optimal when the class of admissible distributions is that of those with increasing virtual values (aka regular). Under this class, it guarantees a fraction of 50% of optimal revenues and no mechanism can guarantee more than 55.6%.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic mechanism design