On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design

• Published in: Operations research 2024-05
• Main Authors: Anunrojwong, Jerry, Balseiro, Santiago R., Besbes, Omar
• Format: Article
• Language: English
• Subjects: minimax regret; Optimization; prior-independent; robust mechanism design; second-price auction with random reserve
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2022.0428

Market designers often only have partial information about the environment and prefer simple mechanisms that are robust to the underlying uncertainty. In “On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design,” Anunrojwong, Balseiro, and Besbes study the fundamental problem of selling an item to n buyers, when only an upper bound on values is known and the seller minimizes worst-case regret. They establish that the same mechanism is robustly optimal across a wide range of environments for distributions of values: i.i.d., mixtures of i.i.d., exchangeable, and affiliated (the last two capturing positive dependence). Moreover, this robust mechanism is a second-price auction with random reserve price depending on n . Without positive dependence, the problem reduces to the one-buyer case. This result supports the wide use of second-price auctions in practice and allows them to quantify the robust value of competition in auctions. Classical Bayesian mechanism design relies on the common prior assumption, but the common prior is often not available in practice. We study the design of prior-independent mechanisms that relax this assumption: The seller is selling an indivisible item to n buyers such that the buyers’ valuations are drawn from a joint distribution that is unknown to both the buyers and the seller, buyers do not need to form beliefs about competitors, and the seller assumes the distribution is adversarially chosen from a specified class. We measure performance through the worst-case regret , or the difference between the expected revenue achievable with perfect knowledge of buyers’ valuations and the actual mechanism revenue. We study a broad set of classes of valuation distributions that capture a wide spectrum of possible dependencies: independent and identically distributed (i.i.d.) distributions, mixtures of i.i.d. distributions, affiliated and exchangeable distributions, exchangeable distributions, and all joint distributions. We derive in quasi closed form the minimax values and the associated optimal mechanism. In particular, we show that the first three classes admit the same minimax regret value, which is decreasing with the number of competitors, whereas the last two have the same minimax regret equal to that of the case n  = 1. Furthermore, we show that the minimax optimal mechanisms have a simple form across all settings: a second-price auction with random reserve prices , which shows its robustness in prior-inde