Research Repository

Almost Envy-Freeness in Group Resource Allocation

Kyropoulou, Maria and Suksompong, Warut and Voudouris, Alexandros A (2019) Almost Envy-Freeness in Group Resource Allocation. In: Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019-08-10 - 2019-08-16, Macao.

[img]
Preview
Text
group-EF.arxiv.pdf - Accepted Version

Download (252kB) | Preview

Abstract

We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 26 Jun 2019 15:14
Last Modified: 04 Sep 2020 14:15
URI: http://repository.essex.ac.uk/id/eprint/24577

Actions (login required)

View Item View Item