Details for Talk on: 20.7.2015

  • Speaker: Timo Mennle
  • 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.