Abstract:

We distinguish between two ways a mechanism can fail to be strategyproof (SP). A mechanism may have profi table manipulations that persist with market size; and, a mechanism may have profi table manipulations that vanish with market size. We say that a mechanism is strategyproof in the large (SP-L) if all of its profi table manipulations vanish with market size. Our main result is as follows. Suppose we are given some mechanism that has Bayes-Nash equilibria but is not SP-L. Suppose that the given mechanism is (semi-)anonymous, that agents have private values, and that a mild continuity condition is satisfi ed. Then, we show by construction that there exists another mechanism that is SP-L, and that implements approximately the same outcomes as the original mechanism, with the approximation error vanishing in the large-market limit. Thus, while SP often severely limits what kinds of mechanisms are possible, SP-L is often approximately costless, and hence may be a useful second-best. We illustrate with examples from assignment, matching and auctions.

Joint work with Eduardo Azevedo.

Paper: http://faculty.chicagobooth.edu/eric.budish/research/Azevedo-Budish-SPL.pdf