A Measure of Complexity for Strategy-Proof Mechanisms

Abstract

We propose a complete ranking of strategy-proof mechanisms in terms of the contingent reasoning they require agents to engage in to recognize their dom- inant strategy. Our 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 our approach allows a designer to bal- ance 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 formal- ize 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.