Fairness of Multi-Resource Allocations




example image



Our work focuses on a specific aspect of fairness: defining the fairness of an allocation of resources to different people. Consider, for instance, the following example: suppose you have two people and need to allocate 6 apples and 4 oranges to them. Each user needs both apples and oranges to complete some jobs; neither fruit can replace the other. User 1 requires 2 apples and 3 oranges per job, while user 2 needs 2 apples and 1 orange per job.

Many allocations might be considered "fair" in this example: should users be allocated fruit in proportion to their requirements? Or should they be allocated resources so as to process equal numbers of jobs? For instance, we could allocate 3 jobs to user 2 and 0 to user 1--then a lot of total jobs would be processed, but that's not, obviously, a fair allocation. Or we could allocate 1 job to each user--that's fair, but only 2 jobs total get processed, so it's not very efficient. We develop a mathematical framework that allows one to compare the fairness of different possible allocations and explore the tradeoff between fairness and efficiency.

Mathematically, we define a resource allocation by a vector \(\vec{x}\), where each entry of \(\vec{x}\) represents the amount of resource given to one person, and there are as many entries of \(\vec{x}\) as there are people. If there are multiple resources, then we have several such allocation vectors, which may be combined into an allocation matrix. We begin from a set of four axioms for fairness proposed by Lan and Chiang in 2011 for single-resource fairness; these yield a parameterized family of fairness functions. We then show two ways in which these single-resource fairness functions can be extended to a multiple resource scenario as in the example above.