Fairness Towards Groups of Agents in the Allocation of Indivisible Items - Sorbonne Université Access content directly
Conference Papers Year : 2020

Fairness Towards Groups of Agents in the Allocation of Indivisible Items

Nawal Benabbou

Abstract

In this paper, we study the problem of matching a set of items to a set of agents partitioned into types so as to balance fairness towards the types against overall utility. We extend multiple desirable properties of an allocation of indivisible goods to our model and investigate the possibility and hardness of achieving combinations of these properties, e.g. we prove that maximizing utilitarian social welfare under constraints of typewise envy-freeness up to one item (TEF1) is compu-tationally intractable. In particular, we define a new concept of waste for this setting; we show experimentally that augmenting an existing algorithm with a marginal utility maximization heuristic can produce a TEF1 solution with reduced waste, and also provide a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities.
Fichier principal
Vignette du fichier
TEF1_FAMAS.pdf (380.24 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02494043 , version 1 (28-02-2020)

Identifiers

  • HAL Id : hal-02494043 , version 1

Cite

Nawal Benabbou, Mithun Chakraborty, Edith Elkind, Yair Zick. Fairness Towards Groups of Agents in the Allocation of Indivisible Items. The Fair Allocation in Multiagent Systems, May 2020, Montréal, Canada. ⟨hal-02494043⟩
72 View
60 Download

Share

Gmail Mastodon Facebook X LinkedIn More