Not logged in.
Quick Search - Contribution
Contribution Details
Type | Conference or Workshop Paper |
Scope | Discipline-based scholarship |
Published in Proceedings | Yes |
Title | The Power of Local Manipulation Strategies in Assignment Mechanisms |
Organization Unit | |
Authors |
|
Presentation Type | paper |
Item Subtype | Original Work |
Refereed | Yes |
Status | Published in final form |
Language |
|
ISBN | 978-1-57735-738-4 |
Page Range | 82 - 89 |
Event Title | Twenty-Fourth International Joint Conference on Artificial Intelligence |
Event Type | conference |
Event Location | Buenos Aires, Argentina |
Event Start Date | July 25 - 2015 |
Event End Date | July 31 - 2015 |
Series Name | Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence |
Number | 24 |
Place of Publication | Palo Alto, California, USA |
Publisher | AAAI Press / International Joint Conferences on Artificial Intelligence |
Abstract Text | 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, i.e., a report that maximizes the agent’s expected utility. In particular, we consider local manipulation strategies, which are simple heuristics based on local, greedy search. We make three 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 prove that local manipulation strategies may fail to solve the manipulation problem optimally. Third, we show via large-scale simulations that despite this nonoptimality, these strategies 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. |
Export |
BibTeX
EP3 XML (ZORA) |