Sign In

Communications of the ACM

Contributed articles

Cake Cutting: Not Just Child's Play


View as: Print Mobile App ACM Digital Library In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Cake Cutting: Not Just Child's Play, illustration

Credit: Alicia Kubista / Andrij Borys Associates

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

The full text of this article is premium content


Comments


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


Displaying 1 comment

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.