Complexity of Manipulating Sequential Allocation
Aziz, Haris; Bouveret, Sylvain; Lang, Jérôme; Mackenzie, Simon (2017), Complexity of Manipulating Sequential Allocation, in Singh, Satinder; Markovitch, Shaul, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017), AAAI Press : Palo Alto (USA), p. 328-334
Type
Communication / ConférenceExternal document link
http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14623Date
2017Conference title
31st AAAI Conference on Artificial Intelligence (AAAI 2017)Conference date
2017-02Conference city
San Francisco, CaliforniaConference country
United StatesBook title
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017)Book author
Singh, Satinder; Markovitch, ShaulPublisher
AAAI Press
Published in
Palo Alto (USA)
Number of pages
5106Pages
328-334
Metadata
Show full item recordAuthor(s)
Aziz, HarisUniversity of South Wales
Bouveret, Sylvain

Institut national Polytechnique de Grenoble [INP GRENOBLE]
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mackenzie, Simon
Computer Science Department - Carnegie Mellon University
Abstract (EN)
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.Subjects / Keywords
social choice; resource allocation; sequential allocation; manipulation; game theoryRelated items
Showing items related by title and author.
-
Aziz, Haris; Bouveret, Sylvain; Caragiannis, Ioannis; Giagkousi, Ira; Lang, Jérôme (2018) Communication / Conférence
-
Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg (2014) Communication / Conférence
-
Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Trung Thanh; Rothe, Jörg; Saffidine, Abdallah (2017) Article accepté pour publication ou publié
-
Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010) Communication / Conférence
-
Bouveret, Sylvain; Lang, Jérôme (2014) Communication / Conférence