Dynamic fair division problem with general valuations

Bo Li, Wenyang Li, Yingkai Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We first design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations. Then by constructing the adversary instances such that all dynamic algorithms must be at least Ω(1)-proportional and Ω(lognn)-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce a setting where the players' valuations are uniform on the resource but with different demands, which generalizes the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.

Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
PublisherInternational Joint Conferences on Artificial Intelligence
Pages375-381
Number of pages7
ISBN (Electronic)9780999241127
DOIs
Publication statusPublished - 2018
Externally publishedYes
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2018-July
ISSN (Print)1045-0823

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Country/TerritorySweden
CityStockholm
Period13/07/1819/07/18

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this