Title: The Power of Local Manipulation Strategies in Assignment Mechanisms
Abstract: We consider three important, non-strategyproof assignment mechanisms:
Probabilistic Serial and two variants of the Boston mechanism. Under
each of these mechanisms, we study the agent's manipulation problem of
determining a best response. In particular, we consider local
manipulation strategies, which are simple heuristics based on local
search. We make two main contributions. First, we present results from a
behavioral experiment (conducted on Amazon Mechanical Turk) which
demonstrate that human manipulation strategies can largely be explained
by local manipulation strategies. Second, we show via large-scale
simulations that while local manipulation strategies may fail to solve
the manipulation problem optimally, they are very effective on average.
Our results demonstrate that while the manipulation problem may be hard
in general, even cognitively or computationally bounded (human) agents
can find near-optimal solutions almost all the time via simple local
search strategies.
