Dynamic Fair Resource Division

• 成果类型: Article
• 署名作者: Vardi, Shai; Psomas, Alexandros; Friedman, Eric
• 署名单位: Purdue University System; Purdue University; Purdue University System; Purdue University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1155
• 发表日期: 2022
• 页码: 945-968
• 关键词: allocation; efficient

摘要

A single homogeneous resource needs to be fairly shared between users that dynamically arrive and depart over time. Although good allocations exist for any fixed number of users, implementing these allocations dynamically is impractical: it typically entails adjustments in the allocation of every user in the system whenever a new user arrives. We introduce a dynamic fair resource division problem in which there is a limit on the number of users that can be disrupted when a new user arrives and study the trade-off between fairness and the number of allowed disruptions, using a fairness metric: the fairness ratio. We almost completely characterize this trade-off and give an algorithm for obtaining the optimal fairness for any number of allowed disruptions.