Research
Multi-resource fairness
People have been arguing about fairness for thousands of years, including academics working in economics, politics, philosophy, and engineering. Though fairness can consequently mean many different things, we focus on a specific aspect of fairness: defining the fairness of an allocation of resources to different people. We use a mathematical theory of fairness that is based on four fairness axioms, which yield a unique family of functions that quantify the fairness of a given resource allocation. These functions unify several previously proposed fairness measures.
The Multi-Resource Allocation (MRA) project focuses on the case of allocating multiple non-substitutable resources, e.g., allocating apples and oranges to people with different resource needs. We adapt the family of single-resource fairness functions to this case, and investigate the consequences. In particular, we explore the fairness-efficiency tradeoff that arises when multiple resources are present and users have heterogeneous resource requirements. We also conduct surveys of real users.
To illustrate the complexity of even simple MRA scenarios, consider 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.
Please see the MRA project's website for more information on our work. Our results have been published in IEEE INFOCOM 2012 (paper and slides available online), where we received the best paper award, and will appear in IEEE/ACM Transactions on Networking (online preprint).