Complexity of Manipulating Sequential Allocation

Authors

  • Haris Aziz Data61, Commonwealth Scientific and Industrial Research Organisation, and University of New South Wales
  • Sylvain Bouveret Université Grenoble-Alpes
  • Jérôme Lang Université Paris-Dauphine and PSL Research University
  • Simon Mackenzie Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v31i1.10586

Keywords:

social choice, resource allocation, sequential allocation, manipulation, game theory

Abstract

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

Downloads

Published

2017-02-10

How to Cite

Aziz, H., Bouveret, S., Lang, J., & Mackenzie, S. (2017). Complexity of Manipulating Sequential Allocation. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10586

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms