2023/11/05 by Shiri Ron, Ron, Shiri
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Game Theory and Voting Systems #Economic theories and models
paper · pdf · doi:10.48550/arxiv.2311.02589
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. These results illustrate a stark separation between the power of dominant-strategy and obviously strategy-proof mechanisms. The reason for it is that for both of these classes the dominant-strategy VCG mechanism does not only optimize the welfare exactly, but is also "easy" both from a computation and communication perspective. In addition, we prove tight impossibilities for unknown single-minded bidders in a multi-unit auction and in a combinatorial auction. We show that in these environments as well, a trivial ascending auction on the grand bundle is optimal.