
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
Type
Communication / ConférenceDate
2014Conference title
2014 international conference on Autonomous agents and multi-agent systems (AAMAS '14 )Conference date
2014-05Conference city
ParisConference country
FranceBook title
AAMAS '14 Proceedings of the 2014 international conference on Autonomous agents and multi-agent systemsPublisher
International Foundation for Autonomous Agents and Multiagent Systems
Published in
Richland
ISBN
978-1-4503-2738-1
Number of pages
997-1004Pages
997-1004
Metadata
Show full item recordAuthor(s)
Ferraioli, DiodatoGourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

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; approximationRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lesca, Julien; Wilczynski, Anaëlle (2021) Communication / Conférence
-
Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010) Communication / Conférence
-
Bouveret, Sylvain; Lang, Jérôme (2005) Communication / Conférence