Finding Fair and Efficient Allocations When Valuations Don't Add Up - Sorbonne Université
Communication Dans Un Congrès Année : 2020

Finding Fair and Efficient Allocations When Valuations Don't Add Up

Nawal Benabbou
Mithun Chakraborty
  • Fonction : Auteur
Ayumi Igarashi
  • Fonction : Auteur
  • PersonId : 1078481
Yair Zick
  • Fonction : Auteur
  • PersonId : 1078482

Résumé

In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to matroid rank functions. This is a versatile valuation class with several desirable properties (monotonicity, submodularity) which naturally models a number of real-world domains. We use these properties to our advantage; first, we show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) allocation that achieves envy-freeness up to one item (EF1) exists and is computationally tractable. We also prove that the Nash welfare-maximizing and the leximin allocations both exhibit this fair-ness/efficiency combination, by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. Moreover, for a subclass of these valuation functions based on maximum (unweighted) bipartite matching, we show that a leximin allocation can be computed in polynomial time.
Fichier principal
Vignette du fichier
SAGT2020_Paper22.pdf (307.54 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02955635 , version 1 (02-10-2020)

Identifiants

Citer

Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick. Finding Fair and Efficient Allocations When Valuations Don't Add Up. The 13th Symposium on Algorithmic Game Theory (SAGT 2020), Sep 2020, Augsburg (Virtual Conference), Germany. pp.32-46, ⟨10.1007/978-3-030-57980-7_3⟩. ⟨hal-02955635⟩
79 Consultations
66 Téléchargements

Altmetric

Partager

More