• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Complexity of Manipulating Sequential Allocation

Thumbnail
Date
2017
Link to item file
http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14623
Dewey
Recherche opérationnelle
Sujet
social choice; resource allocation; sequential allocation; manipulation; game theory
Conference name
31st AAAI Conference on Artificial Intelligence (AAAI 2017)
Conference date
02-2017
Conference city
San Francisco, California
Conference country
United States
Book title
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017)
Author
Singh, Satinder; Markovitch, Shaul
Publisher
AAAI Press
Publisher city
Palo Alto (USA)
Year
2017
Pages number
5106
URI
https://basepub.dauphine.fr/handle/123456789/16485
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Aziz, Haris
134757 University of South Wales
Bouveret, Sylvain
5032 Institut national Polytechnique de Grenoble [INP GRENOBLE]
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mackenzie, Simon
87723 Computer Science Department - Carnegie Mellon University
Type
Communication / Conférence
Item number of pages
328-334
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.