A Measure of Complexity for Strategy-Proof Mechanisms
Research Seminars: Virtual Market Design SeminarThe paper presented in this Virtual Market Design Seminar proposes a complete ranking of strategy-proof mechanisms in terms of the contingent reasoning they require agents to engage in to recognize their dominant strategy. The rankings are consistent with the coarser ones implied by the solution concepts of (strong) obvious strategy-proofness (Li, 2017b; Pycia and Troyan, 2023b). The added flexibility of the approach allows a designer to balance a mechanism’s simplicity with other objectives. The measure characterizes the Ausubel (2004) auction as the simplest way to implement the VCG outcome in multi-unit allocation problems with transfers, and provides novel rankings of mechanisms that implement stable outcomes in matching problems. Finally, the authors characterize minimally complex mechanisms for a range of settings, and formalize the intuition that some mechanisms are as simple as if they were (strongly) obviously strategy-proof. The paper explains how this extension can be valuable for high-stakes applications such as the FCC incentive auction.
People
