Fairness towards groups of agents in the allocation of indivisible items

Nawal Benabbou; Mithun Chakraborty; Edith Elkind; Yair Zick

doi:10.24963/ijcai.2019/14

Fairness towards groups of agents in the allocation of indivisible items

Nawal Benabbou, Mithun Chakraborty, Edith Elkind, Yair Zick

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

28 Scopus citations

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 computationally 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.

Original language	English (US)
Title of host publication	Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
Editors	Sarit Kraus
Publisher	International Joint Conferences on Artificial Intelligence
Pages	95-101
Number of pages	7
ISBN (Electronic)	9780999241141
DOIs	https://doi.org/10.24963/ijcai.2019/14
State	Published - 2019
Event	28th International Joint Conference on Artificial Intelligence, IJCAI 2019 - Macao, China Duration: Aug 10 2019 → Aug 16 2019

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
Volume	2019-August
ISSN (Print)	1045-0823

Conference

Conference	28th International Joint Conference on Artificial Intelligence, IJCAI 2019
Country/Territory	China
City	Macao
Period	8/10/19 → 8/16/19

Funding

Chakraborty and Zick were supported by the Singapore MOE grant R-252-000-625-133 and the Singapore NRF Research Fellowship R-252-000-750-733, Benabbou by the ANR project 14-CE24-0007-01-Cocorico-CoDec, and Elkind by the ERC grant 639945 (ACCORD). The authors would like to thank the anonymous reviewers of IJCAI 2019 and the reviewers and attendees of FAMAS 2019 for their feedback.

ASJC Scopus subject areas

Artificial Intelligence

Access to Document

10.24963/ijcai.2019/14

Cite this

Benabbou, N., Chakraborty, M., Elkind, E., & Zick, Y. (2019). Fairness towards groups of agents in the allocation of indivisible items. In S. Kraus (Ed.), Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 (pp. 95-101). (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2019-August). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2019/14

Benabbou, Nawal ; Chakraborty, Mithun ; Elkind, Edith et al. / Fairness towards groups of agents in the allocation of indivisible items. Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. editor / Sarit Kraus. International Joint Conferences on Artificial Intelligence, 2019. pp. 95-101 (IJCAI International Joint Conference on Artificial Intelligence).

@inproceedings{4c91cc3b2d3843d9aa884d92e3761d44,

title = "Fairness towards groups of agents in the allocation of indivisible items",

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 computationally 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.",

author = "Nawal Benabbou and Mithun Chakraborty and Edith Elkind and Yair Zick",

note = "Publisher Copyright: {\textcopyright} 2019 International Joint Conferences on Artificial Intelligence. All rights reserved.; 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 ; Conference date: 10-08-2019 Through 16-08-2019",

year = "2019",

doi = "10.24963/ijcai.2019/14",

language = "English (US)",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "International Joint Conferences on Artificial Intelligence",

pages = "95--101",

editor = "Sarit Kraus",

booktitle = "Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019",

}

Benabbou, N, Chakraborty, M, Elkind, E & Zick, Y 2019, Fairness towards groups of agents in the allocation of indivisible items. in S Kraus (ed.), Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. IJCAI International Joint Conference on Artificial Intelligence, vol. 2019-August, International Joint Conferences on Artificial Intelligence, pp. 95-101, 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 8/10/19. https://doi.org/10.24963/ijcai.2019/14

Fairness towards groups of agents in the allocation of indivisible items. / Benabbou, Nawal; Chakraborty, Mithun; Elkind, Edith et al.
Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. ed. / Sarit Kraus. International Joint Conferences on Artificial Intelligence, 2019. p. 95-101 (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2019-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fairness towards groups of agents in the allocation of indivisible items

AU - Benabbou, Nawal

AU - Chakraborty, Mithun

AU - Elkind, Edith

AU - Zick, Yair

PY - 2019

Y1 - 2019

N2 - 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 computationally 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.

AB - 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 computationally 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.

UR - http://www.scopus.com/inward/record.url?scp=85071832830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071832830&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2019/14

DO - 10.24963/ijcai.2019/14

M3 - Conference contribution

AN - SCOPUS:85071832830

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 95

EP - 101

BT - Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019

A2 - Kraus, Sarit

PB - International Joint Conferences on Artificial Intelligence

T2 - 28th International Joint Conference on Artificial Intelligence, IJCAI 2019

Y2 - 10 August 2019 through 16 August 2019

ER -

Benabbou N, Chakraborty M, Elkind E, Zick Y. Fairness towards groups of agents in the allocation of indivisible items. In Kraus S, editor, Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. International Joint Conferences on Artificial Intelligence. 2019. p. 95-101. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2019/14

Fairness towards groups of agents in the allocation of indivisible items

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this