The Trivial Obviously Strategy-Proof Mechanism Is Optimal

Abstract: In this talk, we explore the approximation power of obviously strategy-proof auctions. Obvious strategy-proofness, introduced by Li [AER '17], strengthens the concept of dominant-strategy mechanisms. Intuitively, it ensures that even agents who struggle with contingent reasoning can identify their dominant strategy. For m items and n bidders, an ascending auction on the grand bundle is obviously strategy-proof and provides a min{m,n} approximation. We show that this simple mechanism is optimal: no obviously strategy-proof mechanism can achieve a better approximation than min⁡{m,n}, even for simple valuation classes such as additive and unit-demand.