• 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

Positional scoring-based allocation of indivisible goods

Thumbnail
View/Open
BBLNNRS17.pdf (243.5Kb)
Date
2017
Dewey
Probabilités et mathématiques appliquées
Sujet
Computational social choice; Resource allocation; Fair division; Indivisible goods; Preferences
Journal issue
Autonomous Agents and Multi-Agent Systems
Volume
31
Number
3
Publication date
05-2017
Article pages
628-655
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10458-016-9340-x
URI
https://basepub.dauphine.fr/handle/123456789/19153
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Baumeister, Dorothea
84577 Institut für Informatik [Düsseldorf]
Bouveret, Sylvain
24471 Laboratoire d'Informatique de Grenoble [LIG]
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nguyen, Trung Thanh
115536 autre
Rothe, Jörg
84577 Institut für Informatik [Düsseldorf]
Saffidine, Abdallah
95959 Computer Science and Engineering [Sydney] [CSE]
Type
Article accepté pour publication ou publié
Abstract (EN)
We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents’ preferences over sets of goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vector s=(s1,…,sm) consists of m nonincreasing, nonnegative weights, where si is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function ⋆ such as, typically, + or min. The rule associated with s and ⋆ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.

  • 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.