On Robustness to $k$-Wise Independence of Optimal Bayesian Mechanisms

This paper reexamines the classic problem of revenue maximization in single-item auctions with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> buyers under the lens of the robust optimization framework. The celebrated Myerson's mechanism is the format that maximizes the seller's revenue under the prior distribution, which is mutually independent across all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> buyers. As argued in a recent line of work (Caragiannis et al. 22), (Dughmi et al. 24), mutual independence is a strong assumption that is extremely hard to verify statistically, thus it is important to relax the assumption. While optimal under mutual independent prior, we find that Myerson's mechanism may lose almost all of its revenue when the independence assumption is relaxed to pairwise independence, i.e., Myerson's mechanism is not pairwise-robust. The mechanism regains robustness when the prior is assumed to be 3-wise independent. In contrast, we show that second-price auctions with anonymous reserve, including optimal auctions under i.i.d. priors, lose at most a constant fraction of their revenues on any regular pairwise independent prior. Our findings draw a comprehensive picture of robustness to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-wise independence in single-item auction settings.