TY - GEN
T1 - Dynamic fair division problem with general valuations
AU - Li, Bo
AU - Li, Wenyang
AU - Li, Yingkai
N1 - Funding Information:
This work has been partially supported by NSF CAREER Award No. 1553385. The first and the last author thank Jing Chen for introducing them to the area of algorithmic game theory. Finally, the authors would like to acknowledge several wonderful anonymous referees for many helpful comments.
Publisher Copyright:
© 2018 International Joint Conferences on Artificial Intelligence. All right reserved.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85055679835&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2018/52
DO - 10.24963/ijcai.2018/52
M3 - Conference article published in proceeding or book
AN - SCOPUS:85055679835
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 375
EP - 381
BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
A2 - Lang, Jerome
PB - International Joint Conferences on Artificial Intelligence
T2 - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Y2 - 13 July 2018 through 19 July 2018
ER -