Strategyproofness for “Price Takers” as a Desideratum for Market Design

We distinguish between two ways a mechanism can fail to be strategyproof. A mechanism may have manipulations that

persist with market size

(first-order manipulations); and, a mechanism may have manipulations that

vanish with market size

(second-order manipulations). We say that a non-strategyproof mechanism is

strategyproof in the large

(SP-L) if all of its manipulations vanish with market size; that is, if it is strategyproof for “price takers”. We put “price takers” in quotes because our notion is not limited to mechanisms that explicitly use prices. Our main result is that, given a mechanism with Bayes-Nash or complete information Nash equilibria, there exists a prior free mechanism that is SP-L and that coincides exactly with the original mechanism in the limit. It coincides approximately in large finite markets, with exponential rate of convergence. Thus, while strategyproofness often severely limits what kinds of mechanisms are possible, for our class of problems SP-L does not, and hence may be a useful second-best. We illustrate our concepts with examples from single-unit assignment, multi-unit assignment, matching and auctions.