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

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. History: This manuscript has been accepted for the Special Issue on Market Design. Funding: This research was supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 [Grant RG98/23] and by the National Natural Science Foundation of China [Grant 12301412].