Fairness of Multi-Resource Allocations





We consider three desirable fairness properties: Pareto-efficiency, sharing incentive, and envy-freeness. For each of these properties, we derive certain parameter combinations for which these properties always hold, and some for which they do not hold for certain combinations of resource requirements.


A function \(f\) is called Pareto-efficient if, whenever an allocation \(\vec{x}\) Pareto-dominates an allocation \(\vec{y}\), \(f(\vec{x}) > f(\vec{y})\). A vector \(\vec{x}\) is said to Pareto-dominate a vector \(\vec{y}\) if eahc user is at least as well off under allocation \(\vec{x}\) as under allocation \(\vec{y}\), and at least one user is strictly better off: mathematically, if there are \(n\) users, \(x_i \geq y_i\) for each \(i = 1,2,\ldots,n\), with strict inequality for at least entry \(i\).

As for single-resource fairness, if \(\beta > 0\) and \(\lambda \geq (1 - \beta)/\beta\), then Pareto-efficiency holds for any combination of resource requirements. Conversely, if \(\lambda < (1 - \beta)/\beta\), then Pareto-efficiency does not hold for all combinations of resource requirements.

Sharing Incentive:

An allocation \(\vec{x}\) is said to satisfy the sharing incentive property if all users prefer \(\vec{x}\) to allocating an equal amount of each resource to each user; mathematically, each user's dominant share \(\mu_j x_j\) should exceed \(1/n\), where \(n\) is the number of users. We can then derive conditions under which sharing incentive does and does not hold:

Consider FDS fairness, and suppose \(\beta > 0\). Then we can prove the following:

  1. Sharing incentive is satisfied by the FDS-optimal allocation when \(\lambda = \frac{1 - \beta}{\beta}\) and \(\beta > 1\).
  2. For \(0 < \beta < 1\) and \(\lambda = \frac{1 - \beta}{\beta}\), there exists a user-resource system such that the FDS-optimal allocation for this system does not satisfy the sharing incentive property.
  3. For any \(\beta > 0\), there exists \(\lambda\) with \(|\lambda|\) sufficiently large so that for some user-resource system, the FDS-optimal allocation need not satisfy the sharing incentive property.
  4. If \(\lambda = 0\), then the FDS-optimal allocation always satisfies the sharing incentive property.

If we instead consider GFJ, we again suppose that \(\beta > 0\). Then under the conditions enumerated below, there exists a user-resource system whose GFJ-optimal allocation does not satisfy the sharing incentive property:

  1. \(\left|\lambda\right| = \left|(1 - \beta)/\beta\right|\),
  2. \(\left|\lambda\right| > \left|(1 - \beta)/\beta\right|\) and \(0 < \beta < 1\),
  3. \(\left|\lambda\right| < \left|(1 - \beta)/\beta\right|\) and \(\beta > 1\),
  4. \(\left|\lambda\right|\) sufficiently large,
  5. \(\lambda = 0\).


We define an allocation to be envy-free if no user envies another's resource allocation, i.e., if two users switch resource allocations, neither will be able to process more jobs with the switched allocations. Though envy-freeness and sharing incentive are not, in general, equivalent, the above results for sharing incentive also hold for envy-freeness. The figure below summarizes these parameter conditions on \(\beta\) and \(\lambda\).

propertyfdsproperties gfJ img