The Price of Fairness of Scheduling a Scarce Resource

• 成果类型: Article; Early Access
• 署名作者: Vardi, Shai; Haskell, William
• 署名单位: Purdue University System; Purdue University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0568
• 发表日期: 2024
• 关键词: allocation; time

摘要

Scarce resources are often shared between different stakeholders and need to be scheduled fairly among them. In this paper, we study the utility loss resulting from requiring the schedule to be fair, using the price of fairness-the ratio of the utility attainable with and without fairness restrictions. We focus on envy-freeness, an intuitive and well-studied fairness notion. We derive tight bounds on the price of fairness as a function of the problem parameters: the number of agents, the time horizon, the discount factor, the switching cost (the time it takes to transfer possession of the resource), and the concavity and heterogeneity of the agents' utility functions. We analyze the effect of the different parameters on the utility loss to obtain actionable strategic insights. At the macrolevel, the price of fairness is increasing in the number of agents, the switching cost, and the heterogeneity of the utility functions, and it is decreasing in the time horizon and the degree of concavity. At the microlevel, however, the price of fairness is not monotone in any of these parameters except the heterogeneity. This implies that, counterintuitively, a scheduler may be able to reduce the loss of utility by increasing the number of agents or decreasing the time horizon. Furthermore, we find that the dependence of the loss of utility on the number of agents obeys a threshold rule. These insights can help guide decision makers in scheduling problems in which fairness is a factor.