Abstract

We consider the classic problem of revenue maximization in single-item auctions under a robust optimization framework. The celebrated Myerson's mechanism is the format that maximizes the seller's revenue under mutually independent prior distributions. However, the mutual independence of bidders' values is a strong assumption that is extremely hard to verify in practice, as it requires exponentially many samples in the number of bidders. A more practically relevant assumption is pairwise independence that can be verified with only polynomially many samples.

We find that Myerson's mechanism can lose an arbitrarily large fraction of its revenue over mutually independent prior when the prior is changed to pairwise independent distribution with the same set of marginals. I.e., Myerson's mechanism is not pairwise-robust. In contrast, we show that broadly used in practice second-price auctions with anonymous reserve lose at most a constant fraction of its revenue on any pairwise independent prior. These findings give a solid mathematical explanation to why simple suboptimal auctions are employed in practice instead of more complex optimal ones.

Time

2023-07-25  14:00 - 15:00   

Speaker

Zhiqi Wang, ITCS, SUFE

Room

Room 602