Roberto Saitto, Stanford University

Abstract

We propose a measure of strategic complexity for a class of strategy-proof mechanisms, which includes all strategy-proof mechanisms used in practice. Our rankings are consistent with the coarser ones implied by the solution concepts of (strong) obvious strategy-proofness (Li, 2017, Pycia and Troyan, 2023). The added flexibility of our approach allows a designer to balance a mechanism’s simplicity with other objectives. Our 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, we 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. We explain how this extension can be valuable for high-stakes applications such as the FCC incentive auction.