• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14623
Date
2017
Conference title
31st AAAI Conference on Artificial Intelligence (AAAI 2017)
Conference date
2017-02
Conference city
San Francisco, California
Conference country
United States
Book title
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017)
Book author
Singh, Satinder; Markovitch, Shaul
Publisher
AAAI Press
Published in
Palo Alto (USA)
Number of pages
5106
Pages
328-334
Metadata
Show full item record
Author(s)
Aziz, Haris
University of South Wales
Bouveret, Sylvain cc
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 theory

Related items

Showing items related by title and author.

  • Thumbnail
    Knowledge, Fairness, and Social Constraints 
    Aziz, Haris; Bouveret, Sylvain; Caragiannis, Ioannis; Giagkousi, Ira; Lang, Jérôme (2018) Communication / Conférence
  • Thumbnail
    Scoring Rules for the Allocation of Indivisible Goods 
    Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg (2014) Communication / Conférence
  • Thumbnail
    Positional scoring-based allocation of indivisible goods 
    Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Trung Thanh; Rothe, Jörg; Saffidine, Abdallah (2017) Article accepté pour publication ou publié
  • Thumbnail
    Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods 
    Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010) Communication / Conférence
  • Thumbnail
    Manipulating picking sequences 
    Bouveret, Sylvain; Lang, Jérôme (2014) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo