Fair and Efficient Multi-resource Allocation for Cloud Computing: Beyond Dominant Resource Fairness

• 成果类型: Article; Early Access
• 署名作者: Bei, Xiaohui; Li, Zihao; Luo, Junjie
• 署名单位: Nanyang Technological University; National University of Singapore; Beijing Jiaotong University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0714
• 发表日期: 2026-02-11
• 关键词: fair division; mechanism design; Leontief preference; cloud computing

摘要

We study the problem of allocating multiple types of resources to agents with Leontief preferences. The classic Dominant Resource Fairness (DRF) mechanism satisfies several desired fairness and incentive properties, but is known to have poor performance in terms of social welfare approximation ratio. In this work, we propose a new approximation ratio measure, called fair-ratio, which is defined as the worst-case ratio between the optimal social welfare (resp. utilization) among all fair allocations and that achieved by the mechanism, allowing us to break the lower bound barrier under the classic approximation ratio. We then generalize DRF and introduce several new mechanisms for two, as well as more than two, types of resources that satisfy the same set of properties as DRF but offer improved guarantees for social welfare and utilization under the new benchmark. We also demonstrate the effectiveness of these mechanisms through experiments on both synthetic and real-world data sets.