Show simple item record

Positional scoring-based allocation of indivisible goods

hal.structure.identifierInstitut für Informatik [Düsseldorf]
dc.contributor.authorBaumeister, Dorothea
hal.structure.identifierLaboratoire d'Informatique de Grenoble [LIG]
dc.contributor.authorBouveret, Sylvain
HAL ID: 976
ORCID: 0000-0002-1570-5244
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLang, Jérôme
hal.structure.identifierautre
dc.contributor.authorNguyen, Trung Thanh
hal.structure.identifierInstitut für Informatik [Düsseldorf]
dc.contributor.authorRothe, Jörg
hal.structure.identifierComputer Science and Engineering [Sydney] [CSE]
dc.contributor.authorSaffidine, Abdallah
dc.date.accessioned2019-07-04T08:22:17Z
dc.date.available2019-07-04T08:22:17Z
dc.date.issued2017
dc.identifier.issn1387-2532
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19153
dc.language.isoenen
dc.subjectComputational social choiceen
dc.subjectResource allocationen
dc.subjectFair divisionen
dc.subjectIndivisible goodsen
dc.subjectPreferencesen
dc.subject.ddc519en
dc.titlePositional scoring-based allocation of indivisible goodsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameAutonomous Agents and Multi-Agent Systems
dc.relation.isversionofjnlvol31en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2017-05
dc.relation.isversionofjnlpages628-655en
dc.relation.isversionofdoi10.1007/s10458-016-9340-xen
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-28T11:28:27Z
hal.identifierhal-01399842*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
BBLNNRS17.pdf
Size:
243.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record