• 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

On regular and approximately fair allocations of indivisible goods

Thumbnail
View/Open
p997.pdf (575.5Kb)
Date
2014
Sujet
Computational social choice; fairness; approximation
Conference name
2014 international conference on Autonomous agents and multi-agent systems (AAMAS '14 )
Conference date
05-2014
Conference city
Paris
Conference country
France
Book title
AAMAS '14 Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Publisher city
Richland
Year
2014
Pages number
997-1004
ISBN
978-1-4503-2738-1
URI
https://basepub.dauphine.fr/handle/123456789/15393
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Ferraioli, Diodato
status unknown
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
997-1004
Abstract (EN)
An active stream of research is devoted to the design of polynomial approximation algorithms for the fair allocation of indivisible goods. Central to this field is the MaxMin Allocation problem, for which there is a significant gap between known approximation and inapproximability results. Closing this gap is a stimulating challenge.To this end, we consider a regular version of MaxMin Allocation where each agent must receive exactly k goods, for a given integer k. We call this problem k-division. The analysis of this problem allows us to highlight two interesting features of the classical MaxMin Allocation problem. First, we show a close connection of the problem with matroid theory. This connection provides us an exact algorithm for a special case of k-division and a 1/k-approximation algorithm for general inputs. Moreover, we show that the difficulty of the MaxMin Allocation may be caught by an apparently simpler problem, namely the k-division problem in which an agent's utility for a single good can only take one value out of three.

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