Cake-Cutting Algorithms: Be Fair if You Can 1st Edition
Use the Amazon App to scan ISBNs and compare prices.
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
-- Francis Edward Su, American Mathematical Monthly , March 2000
- Publisher : A K Peters/CRC Press; 1st edition (July 15, 1998)
- Language : English
- Hardcover : 177 pages
- ISBN-10 : 1568810768
- ISBN-13 : 978-1568810768
- Item Weight : 1.1 pounds
- Dimensions : 6.26 x 0.75 x 9.3 inches
- Best Sellers Rank: #3,150,067 in Books (See Top 100 in Books)
- Customer Reviews:
Top reviews from the United States
There was a problem filtering reviews right now. Please try again later.
But it was only in this century that people started thinking about how a fair split could be achieved when a third brother Harry comes on the scene. The fair split between three is one of the first exercises in a curious book _Cake Cutting Algorithms: Be Fair If You Can_ by Jack Robertson and William Webb. It won't work to have Tom cut the cake and Dick and Harry choose, nor will it work to have Tom cut the one third out and Dick cut the larger piece into two one third pieces. The book shows how the participants can't be guaranteed fairness by these methods. But there are methods that work.
One method would, I suppose, require a referee, who would be equipped with a knife. He holds the knife over the leftmost edge of the cake (it is perhaps better to imagine a rectangular sheet cake rather than a circular one) and begins a sweep toward the right edge. Whenever Tom, Dick, or Harry think the descent of the knife would cut off a fair slice, he yells "Stop!", the knife descends, and the caller takes his piece away. The algorithm continues with the referee again moving the knife until a second player calls for a cut. The third player gets the remains, and can't be dissatisfied with what is left over; he could have called out sooner if he had wanted.
But that sweeping knife algorithm, as useful as it might be, is subject to the whim of the referee and to the lapse of time between call and cut. (I am making a practical objection here, although this is a mathematical book, and not subject to such real-life trivialities.) Can a fair three way spit be achieved by something like Cut and Choose? Yes, indeed, but mathematicians only came up with the algorithm fifty years ago. Tom cuts what he thinks is one third of the cake and passes that third to Dick. Dick considers if it is more than a third, and if so, he trims away anything he thinks an excess (and puts the trimmings back in the larger section of cake). He then passes the piece, trimmed or untrimmed, to Harry. If Harry agrees that the piece is fair, he takes it. If not, he gives it to Dick, who has to take it if he trimmed it, but if he did not trim it, he passes it on to Tom, who has to take it. With the smaller piece now belonging to one of the brothers, the others play Cut and Choose with the remains. It is fun to play a bit with this algorithm and put oneself into the position of any of the brothers and try to jimmy a big portion of the cake. It won't work; just as in simple Cut and Chose, it is in the best interest of the players to be as fair as they can, and they have simply to accept the consequences of their decisions.
It is interesting that this subject has become the domain of serious mathematicians, and that much work continues to be done in it, although Cut and Choose was the only tool available until recent decades. As the introduction to the book makes clear, it is an expansion of mathematics into the social sciences. Math has done very well for the physical sciences, but with cake cutting for fairness, and such things as game theory, math comes into human behavior.
Cake cutting is not simply an academic exercise, however. Tom, Dick, and Harry may be of the opinion that getting their fair share of cake is the most important thing in the world, but what about when their parents leave them an estate? Getting a fair share of the estate is at least as important, and could be a real-world focus for procedures outlined in this book. For instance, it is possible, if the participants put different values onto different items in the estate, that each of them can come away with the feeling that he got more than a third of the estate value. Oddly, if the cake is not homogeneous (if it has icing roses in one corner, say, and Dick is an icing freak), it is actually easier to come up with means of dividing it fairly.
Similarly, dividing rent between people who share unequal rooms in the same house, dividing chores, and other splits requiring fairness could all be modeled mathematically and all involved could walk away with a feeling of satisfaction.
There are plenty of other problems that can be derived from these ideas. What if a fair split is determined not to be thirds, but the participants agree (perhaps because one got a whole cake the day before) that one should settle for a smaller share? What if the cake has already been divided into many smaller pieces and these have to be apportioned out? What is the smallest number of cuts that have to be made? It is really surprising how rich this odd corner of mathematical endeavor has proved to be.
_Cake Cutting Algorithms_ is not a breezy collection of essays. It is, indeed, a mathematical text, and could be used for a college course on the subject. (There are even exercises at the end of each chapter, and answers to them at the back of the book.) The final chapters are technical proofs and would be interesting to the specialist, but the first chapters of the book avoid complexities from other areas of mathematics and require no special math experience. They are entertaining, and provide a good view of a small mathematical world that has beauty and real-world applications.