Strategyproofness in the Large as a Desideratum for Market Design

摘要

We propose a criterion of approximate strategyproofness (SP), called strategyproof in the large (SP-L). A mechanism is SP-L if, for any agent, any probability distribution of the other agents' reports, and any ∈ > 0 , in a large enough market the agent maximizes his expected payoff to within ∈ by reporting his preferences truthfully. Conceptually, SP-L distinguishes between two kinds of non-SP mechanisms: those where profitable misreports vanish as the market grows large in our sense, and those where profitable misreports persist even as the market grows large. Our main result shows that, under some assumptions, SP-L is approximately costless to satisfy in large markets relative to Bayes-Nash or Nash implementability. The assumptions include anonymity, private values, and a continuity condition. We interpret the result as justifying SP-L as a second-best desideratum, especially for problems for which the benefits of SP design are compelling (e.g., prior free) yet it is known that mechanisms that are exactly SP are unattractive. We illustrate with examples from assignment, matching, and auctions.