Prior-Independent Auctions for Heterogeneous Bidders

• Published in: arXiv.org 2023-11
• Main Authors: Guru Guruganesh, Mehta, Aranyak, Wang, Di, Wang, Kangning
• Format: Article
• Language: English
• Subjects: Approximation; Auctions; Lower bounds; Mathematical analysis; Revenue; Tradeoffs
• ISSN: 2331-8422

We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to \(n\) bidders whose values are drawn from \(n\) independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders' value distributions and must design a mechanism that is prior-independent. While there have been many strong results on prior-independent auction design in the i.i.d. setting, not much is known for the heterogeneous setting, even though the latter is of significant practical importance. Unfortunately, no prior-independent mechanism can hope to always guarantee any approximation to Myerson's revenue in the heterogeneous setting; similarly, no prior-independent mechanism can consistently do better than the second-price auction. In light of this, we design a family of (parametrized) randomized auctions which approximates at least one of these benchmarks: For heterogeneous bidders with regular value distributions, our mechanisms either achieve a good approximation of the expected revenue of an optimal mechanism (which knows the bidders' distributions) or exceeds that of the second-price auction by a certain multiplicative factor. The factor in the latter case naturally trades off with the approximation ratio of the former case. We show that our mechanism is optimal for such a trade-off between the two cases by establishing a matching lower bound. Our result extends to selling \(k\) identical items to heterogeneous bidders with an additional \(O\big(\ln^2 k\big)\)-factor in our trade-off between the two cases.