Manipulating picking sequences
Bouveret, Sylvain; Lang, Jérôme (2014), Manipulating picking sequences, in Schaub, Torsten; Friedrich, Gerhard; O'Sullivan, Barry, ECAI'14 Proceedings of the Twenty-first European Conference on Artificial Intelligence, Ios Press : Amsterdam, p. 141-146. 10.3233/978-1-61499-419-0-141
TypeCommunication / Conférence
Conference title21st European Conference on Artificial Intelligence (ECAI'14)
Conference countryCzech Republic
Book titleECAI'14 Proceedings of the Twenty-first European Conference on Artificial Intelligence
Book authorSchaub, Torsten; Friedrich, Gerhard; O'Sullivan, Barry
Number of pages1232
MetadataShow full item record
Institut national Polytechnique de Grenoble [INP GRENOBLE]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.
Subjects / Keywordssocial choice
Showing items related by title and author.