Fair and Efficient Allocations with Limited Demands

Sushirdeep Narayana, Ian A. KashAAAI 2021 · DOI

Introduction

In large-scale computing environments such as data centers, the efficient allocation of heterogeneous resources (CPU, RAM, bandwidth) among multiple users is a critical challenge. Traditional "fair division" theories often operate under the assumption that a user's utility increases indefinitely with more resources. However, real-world computational tasks frequently exhibit limited demands: a job has a finite amount of work to complete and simply aims to finish as quickly as possible to exit the system.

In this context, the standard for fairness, Dominant Resource Fairness (DRF), reveals a significant inefficiency. By focusing on equalizing resource shares, DRF often forces tasks to run slowly in parallel. This results in Pareto inefficiency, where it would be objectively better for one task to finish rapidly and vacate resources for others, yet the algorithm prevents such an optimization.

The Least Cost Product (LCP) Mechanism

To address these inefficiencies, researchers have introduced the Least Cost Product (LCP) mechanism. LCP is a direct adaptation of the "Maximum Nash Welfare" (MNW) approach. While MNW typically maximizes the product of users' utilities, LCP minimizes the product of users' costs, where cost is defined as the time taken to complete a task.

Technical Framework

  • Leontief Preferences: The model assumes tasks require resources in fixed ratios (e.g., a specific amount of RAM per CPU core).
  • Allocation Structure: Optimal solutions under LCP typically involve selecting "extreme points" on the Pareto frontier during the intervals between job completions.
  • LCP-X Algorithm: To overcome the computational complexity of finding exact LCP solutions, the authors developed LCP-X, an algorithm that searches through these extreme points to identify the optimal allocation.
Example of resource allocation (R1) over time for three agents under the LCP mechanism.

Evaluation and Key Results

The mechanism was evaluated using synthetic simulations across 2,000 randomly generated problem instances for groups of 2 to 5 agents. LCP-X was compared against DRF-W, a version of DRF adapted for tasks with finite work.

Efficiency vs. Fairness

LCP serves as a principled middle ground between "Shortest Job First" (efficient but potentially unfair) and "Processor Sharing" (fair but slow).

  • Efficiency Gains: LCP-X significantly outperforms DRF-W in mean completion time. In simulations with 4 or 5 agents, LCP-X achieved a better average completion time in 100% of test cases.
  • Practical Fairness: While LCP can theoretically result in envy when there are at least three agents and two resource types, simulations show this is extremely rare. For 5 agents, envy occurred in only 0.1% of cases.
  • Sharing Incentives: The authors proved that LCP always satisfies "Sharing Incentives," ensuring no user is worse off than they would be under a simple equal split of resources.
Performance comparison between LCP-X and DRF-W across various metrics and agent counts.

Discussion and Future Work

While LCP offers substantial efficiency gains, it has limitations. It is not currently strategy-proof, meaning a user could potentially manipulate their reported work or resource needs to finish faster. Furthermore, the current model is static, assuming all jobs arrive simultaneously.

Future research will explore extending LCP to dynamic settings with continuous job arrivals and departures, as well as investigating its relationship to market-based mechanisms like the Eisenberg-Gale convex program. Additionally, while LCP excels at average completion time, DRF-W remains superior for minimizing makespan (the time until the final job completes).

Summary updated

BibTeX
@inproceedings{narayana2021fair,
  author = {Sushirdeep Narayana and Ian A. Kash},
  title = {{Fair and Efficient Allocations with Limited Demands}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16706},
}
Figure