Fairness Towards Groups of Agents in the Allocation of Indivisible Items

Nawal Benabbou 1 Mithun Chakraborty 2 Edith Elkind 3 Yair Zick 2
1 DECISION
LIP6
2 NUS - School of computing [Singapore]
3 University of Oxford [Oxford]
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/efficiency. We extend multiple desirable properties of indivisible goods allocation 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 computa-tionally intractable. We also define a new concept of waste for this setting, 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download
https://hal.sorbonne-universite.fr/hal-02155024
Contributor : Nawal Benabbou <>
Submitted on : Thursday, June 13, 2019 - 12:00:16 PM
Last modification on : Friday, July 5, 2019 - 3:26:03 PM

File

ijcai19.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02155024, version 1

Collections

CNRS | SORBONNE-UNIVERSITE | LIP6 | SU-SCIENCES

Citation

Nawal Benabbou, Mithun Chakraborty, Edith Elkind, Yair Zick. Fairness Towards Groups of Agents in the Allocation of Indivisible Items. The 28th International Joint Conference on Artificial Intelligence (IJCAI'19), Aug 2019, MACAO, China. ⟨hal-02155024⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

68

Files downloads

165

Contact

Informations

CCSD