Your Half’s Bigger Than My Half!
Your Halfs Bigger Than My Half!, Ian Stewart. Scientific American 279:6 (December 1998) 112, 114. Division without Envy, Ian Stewart. Scientific American 280:1 (January 1999) 110-111.
These two articles survey an ancient problem and its modern extensions: How does one cut a cake fairly? A number of surprising facts are revealed, and reference is made to recent work of S. J. Brains and A. D. Taylor, “An Envy-Free Cake Division Protocol,” Amer. Math. Monthly 102:1 (January 1995) 9-18 and of J. Robertson and W. Webb, Cake Cutting Algorithms, A. K. Peters, 1998. The simplest version of the problem and its equally simple resolution date from antiquity: Two people wish to share a cake in such a manner that each feels that he or she has received at least half of it. Such a division is called “fair,” and Stewart notes that “the solution `Alice cuts, Bob chooses’ has been traced back 2,800 years!” However, it was not until 1944 that a solution to the next most simple generalization-three people seeking a fair division of a cake-was found, by Hugo Steinhaus. Stewart describes that method and two more recent approaches, one of which uses a moving knife. Then he discusses the extension of these methods, adding a fourth method as well, to the problem of fairly dividing a cake among n people. All but one are “fixed-knife” methods. Of particular interest is the number of cuts that each method requires. This could serve as a useful example of elementary algorithmic analysis for an introductory combinatorics class.
In the second article, Stewart moves beyond “fairness” (n people receiving what each regards as at least 1/n th of the cake) to the more stringent requirement of “absence of envy,” which means that nobody regards anyone else as having received a greater share than his or her own. For three people, Stewart includes the envy-free algorithm found by John Selfridge and John H. Conway in the early 1960’s. The problem of n people remained open until 1995, when Steve Brams and Alan Taylor published their solution in the article cited above. Stewart calls their method “remarkable” and “distinctly complicated.” The article ends with a discussion of the somewhat counterintuitive observation that a fair solution is less easily achieved when all participants agree on the value of each part of the cake, whereas disagreement facilitates fair division! A lovely, simple example for the case of two people is explained, and Stewart observes that “disagreement about values” need not entail “disagreement about what constitutes fair division.” The article concludes with a very apt example of fair division of beachfront property among several people, where each draws parallel lines so as to divide the plot into what each regards as n subplots of equal area.
Copyright Mathematical Association Of America Sep 1999
Provided by ProQuest Information and Learning Company. All rights Reserved