Communications of the ACM

How to fairly allocate divisible resources, and why computer scientists should take notice.

CACM Administrator

The following letter was published in the Letters to the Editor of the December 2013 CACM (http://cacm.acm.org/magazines/2013/12/169937).
-- CACM Administrator

Although Ariel D. Procaccia's article "Cake Cutting: Not Just Child's Play" (July 2013) offered an interesting overview of recent research on cake division in computer science, it emphasized envy-free solutions that are not sufficiently fair.

Envy-freeness is a property that violates the axiom of monotony, or the requirement of Pareto-efficiency, in which a solution that improves the outcome of an agent by any amount is preferable in terms of fairness to a solution in which all agents have equal smaller outcomes. However, such a solution cannot be envy-free.

Envy-free solutions for distribution of multiple goods involve a subtler theoretical shortcoming. Consider allocating food to animals in a zoo. Though the animals have utilities that can be expressed in terms of the calories they consume, they can consume only certain foods. One might eat only eggs. Another might eat eggs but also other foods. A non-envy solution might therefore be to give the egg eater insufficient eggs for its survival. This theoretical weakness is alleviated through the concept of maxmin fairness.

Procaccia mentioned utilitarian and egalitarian fairness but none of the important theoretical advances in the definition of distributional fairness. For example, Ogryczak et al.2 formulated "equitable optimality," generalizing both utilitarian and egalitarian approaches by imposing three axioms on the preferences of fair solutions: impartiality (the permutation of outcomes from another solution should be indifferent); monotony; and the Pigou-Dalton principle of transfers (a small amount from a better-off agent to a worse-off agent should be preferred). It can be shown that finding equitably optimal solutions does not increase computational complexity by more than a polynomial factor. Such solutions can be found as Pareto-optimal solutions to a problem involving criteria obtained first from the Lorenz curve of the original distribution problem. Moreover, optimal solutions can be selected with consideration for the trade-off between equality and efficiency, increasing the likelihood of their acceptance by stakeholders.

The concept of envy-free solutions is useful only if agents are fully autonomous and selfish in a non-cooperative setting. However, Procaccia's example of CPU and RAM allocations to computing jobs does not require such a model. In most practical cases, there is a single administration of the computing resources, either cloud or grid, that can and should impose a better solution than the envy-free solution to the cake-cutting problem. It also illustrates that equitably optimal solutions requiring a cooperative setting can be obtained in practice.

A body of literature has aimed to find equitably optimal solutions in various settings, of which we recommend Luss1 and Wierzbicki.3

Adam Wierzbicki
Warsaw, Poland

Wodzimierz Ogryczak
Warsaw, Poland

--------------------------------------------------
REFERENCES

1. Luss, H. Equitable Resource Allocation: Models, Algorithms and Applications. Wiley, Hoboken, NJ, 2012.

2. Ogryczak, W. et al. Equitable aggregations and multiple criteria analysis. European Journal of Operational Research 158, 2 (Oct. 2004), 362377.

3. Wierzbicki, A. Trust and Fairness in Open, Distributed Systems. Springer, Berlin, Heidelberg, 2010.

--------------------------------------------------

AUTHOR'S RESPONSE

I welcome these points and am happy to respond. First, many of the solutions I discussed in my article are both envy-free and Pareto-efficient. Second, in most fair-division settings envy-freeness implies proportional shares of the resources; in the zoo example, assuming eggs are allocated, the poor egg eaters would be envious. Third, I interpret the letter's penultimate paragraph primarily as a criticism of strategy-proofness rather than of envy-freeness. However, it is not the jobs that are autonomous but rather the users running them; the scheduler can impose a solution based only on the available information, which can be manipulated.

Ariel D. Procaccia
Pittsburgh, PA