Tolerable Manipulability in Dynamic Assignment without Money
Access StatusFull text of the requested work is not available in DASH at this time ("dark deposit"). For more information on dark deposits, see our FAQ.
MetadataShow full item record
CitationZou, James Yang, Sujit Gujar, and David C. Parkes. 2010. Tolerable manipulability in dynamic assignment without money. In proceedings of the 24th AAAI Conference on Articial Intelligence (AAAI '10), Atlanta, GA, July 11-15, 2010, 947-952.
AbstractWe study a problem of dynamic allocation without money. Agents have arrivals and departures and strict preferences over items. Strategyproofness requires the use of an arrival-priority serial-dictatorship (APSD) mechanism, which is ex post Pareto efficient but has poor ex ante efficiency as measured through average rank efficiency. We introduce the scoring-rule (SR) mechanism, which biases in favor of allocating items that an agent values above the population consensus. The SR mechanism is not strategyproof but has tolerable manipulability in the sense that: (i) if every agent optimally manipulates, it reduces to APSD, and (ii) it significantly outperforms APSD for rank efficiency when only a fraction of agents are strategic. The performance of SR is also robust to mistakes by agents that manipulate on the basis of inaccurate information about the popularity of items.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:10058924
- FAS Scholarly Articles