• 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

On regular and approximately fair allocations of indivisible goods

Ferraioli, Diodato; Gourvès, Laurent; Monnot, Jérôme (2014), On regular and approximately fair allocations of indivisible goods, AAMAS '14 Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, International Foundation for Autonomous Agents and Multiagent Systems : Richland, p. 997-1004

View/Open
p997.pdf (575.5Kb)
Type
Communication / Conférence
Date
2014
Conference title
2014 international conference on Autonomous agents and multi-agent systems (AAMAS '14 )
Conference date
2014-05
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
Published in
Richland
ISBN
978-1-4503-2738-1
Number of pages
997-1004
Pages
997-1004
Metadata
Show full item record
Author(s)
Ferraioli, Diodato

Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.
Subjects / Keywords
Computational social choice; fairness; approximation

Related items

Showing items related by title and author.

  • Thumbnail
    A matroid approach to the worst case allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    Worst case compromises in matroids with applications to the allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
  • Thumbnail
    On Fairness via Picking Sequences in Allocation of Indivisible Goods 
    Gourvès, Laurent; Lesca, Julien; Wilczynski, Anaëlle (2021) Communication / Conférence
  • 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
    Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity 
    Bouveret, Sylvain; Lang, Jérôme (2005) 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