Cake-Cutting Algorithms: Be Fair if You Can

by Robertson ,Jack

• ISBN13: 9781568810768
• ISBN10: 1568810768
• Format: Hardcover
• Copyright: 1998-07-15
• Publisher: A. K. Peters

Summary

The challenge of dividing an asset fairly, from cakes to more important properties, is of great practical importance in many situations. Since the famous Polish school of mathematicians (Steinhaus, Banch, and Knaster) introduced and described algorithms for the fair division problem in the 1940s, the concept has been widely popularized. This book gathers into one readable and inclusive source a comprehensive discussion of the state of the art in cake-cutting problems for both the novice and the professional. It offers a complete treatment of all cake-cutting algorithms under all the considered definitions of "fair" and presents them in a coherent, reader-friendly manner. Robertson and Webb have brought this elegant problem to life for both the bright high school student and the professional researcher.

Table of Contents

Preface	ix
1 Fairly Dividing a Cake	1	(16)
1.1 First Things	1	(4)
1.2 On to Three Persons -- A False Start	5	(2)
1.3 On to Three Persons -- Successfully	7	(4)
1.4 Envy Rears Its Ugly Head	11	(3)
1.5 EXERCISES	14	(3)
2 Pieces or Crumbs -- How Many Cuts Are Needed?	17	(18)
2.1 First Things -- Some Agreements on Assumptions and Notation	17	(5)
2.2 One Cut Suffices	22	(1)
2.3 On to the Count	23	(2)
2.4 Using Fewer Cuts with the Divide and Conquer Algorithm	25	(3)
2.5 Two Cuts Are Never Enough	28	(1)
2.6 What is the Best We Can Do for Four Players?	29	(2)
2.7 Other Information on the Number of Cuts	31	(1)
2.8 EXERCISES	32	(3)
3 Unequal Shares	35	(14)
3.1 First Things	35	(1)
3.2 A Better Solution Leading to Ramsey Partitions	36	(6)
3.3 Cut Near-Halves Algorithm for Unequal Shares	42	(3)
3.4 More Than Two Players with Unequal Shares	45	(1)
3.5 Unequal Shares in an Irrational Ratio	46	(2)
3.6 EXERCISES	48	(1)
4 The Serendipity of Disagreement	49	(12)
4.1 First Things	49	(1)
4.2 Some Other Examples	50	(7)
4.3 EXERCISES	57	(4)
5 Some Variations on the Theme of "Fair" Division	61	(22)
5.1 Other Interpretations of "Fair"	61	(1)
5.2 Strong Fair Division	62	(3)
5.3 Envy-Free Division	65	(3)
5.4 Exact Division	68	(5)
5.5 Less is More -- The Dirty Work Problem	73	(2)
5.6 Existence Theorems	75	(1)
5.7 Classes of Algorithms	76	(1)
5.8 EXERCISES	77	(6)
6 Some Combinatorial Observations	83	(10)
6.1 Applying Graph Theory to Fair Division	83	(5)
6.2 What Can Be Done with n Arbitrary Pieces?	88	(3)
6.3 EXERCISES	91	(2)
7 Interlude: An Inventory of Results	93	(6)
7.1 Algorithms for Fair Division	93	(2)
7.2 Number of Cuts for Fair Division	95	(4)
8 Impossibility Theorems	99	(8)
8.1 Resetting the Stage	99	(3)
8.2 More Than n - 1 Cuts Are Required for n Players, n > (-) 3	102	(1)
8.3 No Finite Algorithm Can Accomplish Exact Division	103	(2)
8.4 PROJECTS	105	(2)
9 Attempting Fair Division with a Limited Number of Cuts	107	(18)
9.1 The Problem	107	(1)
9.2 Simple Fair Division for a Small Number of Players	108	(6)
9.3 What Can Be Done with k Cuts?	114	(6)
9.4 Divide and Conquer Revisited	120	(2)
9.5 EXERCISES	122	(1)
9.6 PROJECTS	123	(2)
10 Exact and Envy-Free Algorithms	125	(16)
10.1 Resetting the Stage	125	(1)
10.2 Near-Exact Division	126	(2)
10.3 Envy-Free Division	128	(8)
10.4 Super Envy-Free Division	136	(2)
10.5 EXERCISES	138	(1)
10.6 PROJECTS	138	(3)
11 A Return to Division for Unequal Shares	141	(14)
11.1 Resetting the Stage	141	(1)
11.2 Ramsey Partitions and Fair Division	141	(4)
11.3 Cut and Choose for Unequal Shares	145	(4)
11.4 Envy-Free Division for Three Players with Unequal Shares	149	(5)
11.5 EXERCISES	154	(1)
11.6 PROJECT	154	(1)
Solutions	155	(18)
References	173	(6)
Index	179