Price of Anarchy for Auction Revenue

Revenue approximation results for auctions have been limited to settings in which analytically solving for equilibrium is feasible: in particular, truthful auctions or symmetric settings of non-truthful auctions. We use a price of anarchy style approach similar to the smooth mechanisms framework of Syrkganis and Tardos [2013] to derive revenue approximation bounds in Bayes-Nash equilibrium without needing to analytically characterize equilibrium. Our central result is that the first-price auction with monopoly reserves in asymmetric settings is a 3.16-approximation to the revenue of the optimal auction; with duplicates instead of reserves, it is a 4.75-approximation. In addition, we present a framework for reducing revenue approximation in many other settings to this simple single-item, first-price auction setting. This allows the generalization of our approximations to matroid feasibility constraints, all-pay auctions, position auctions, and the simultaneous composition of auctions with unit-demand, single-valued agents. Joint work with Jason Hartline and Sam Taggart.