Fairness of Multi-Resource Allocations

homeimgDefinitionlinkDifferentviewslinkMultiresourcelinkInpracticelinkParticipatelinkFurtherinfolink

 

Properties

PropertieslinkEfficiencylinks

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.

Pareto-efficiency:

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\).

Envy-Freeness:

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