Shiri Ron, Weizmann Institute of Science

Abstract

We explore the approximation power of deterministic obviously strategy-proof mechanisms in auctions, where the objective is welfare maximization. A trivial ascending auction on the grand bundle guarantees an approximation of min{m,n} for all valuation classes, where m is the number of items and n is the number of bidders. We focus on two classes of valuations considered “simple”: additive valuations and unit-demand valuations. For additive valuations, Bade and Gonczarowski [EC'17] have shown that exact welfare maximization is impossible. No impossibilities are known for unit-demand valuations.

We show that if bidders' valuations are additive or unit-demand, then no obviously strategy-proof mechanism gives an approximation better than min{m,n}. Thus, the aforementioned trivial ascending auction on the grand bundle is the optimal obviously strategy-proof mechanism. This illustrates a stark separation between the power of dominant-strategy and obviously strategy-proof mechanisms because for both of these classes, the dominant-strategy VCG mechanism not only optimizes the welfare exactly but is also "easy" from both a computation and communication perspective. We provide additional tight impossibility results for single-minded bidders in multi-unit auctions and combinatorial auctions.