Cake-Division Procedure DEFINITION

A cake-division procedure for players is a procedure that the players can use to allocate a cake among themselves (no outside arbitrators) so that each player has a strategy that will guarantee that player a piece with which he or she is “satisfied,” even in the face of collusion by the others.

The modern era of cake cutting began with the investigations of the Polish mathematician Hugo Steinhaus during World War II. His research, and that of dozens of others since, involved dealing with two fundamental difficulties. First, allocation schemes that work in the context of two or three players often do not generalize easily to the context of four or more players. Second, procedures that yield envy-free allocations are considerably harder to obtain than procedures that yield proportional allocations.

The mathematics inspired by these two difficulties constitutes a rather elegant corner of the large and important area of fair division. Steinhaus’s investigations in the 1940s led to his observation that there is a rather natural extension of divide-and-choose to the case of three players. This is the “lone-divider method” described on page 554. Steinhaus’s method was generalized to an arbitrary number of players by Harold W. Kuhn of Princeton University in 1967.

Unable to extend his procedure from three to four players, Steinhaus proposed the problem to some Polish colleagues. Two of them, Stefan Banach and Brønislaw Knaster, solved this problem in the mid-1940s by producing the “last-diminisher method” described on page 554.

In addition to the procedures devised by Banach, Knaster, and Kuhn, there are other well-known constructive procedures for obtaining a proportional allocation among four or more players. one of these is by A. M. Fink of Iowa State University and appears in Exercise 27 (on page 567).

Another constructive procedure of note, although different in flavor from the others, is the 1961 recasting by Lester E. Dubins and Edwin H. Spanier of the University of California at Berkeley of the last-diminisher method as a “moving-knife method” (illustrated in Exercise 40 on page 569). The trade-off here involves giving up the “discrete” nature of the last-diminisher method in exchange for the conceptual simplicity of the moving knife.

Although the existence of an envy-free allocation (even for four or more players) was known to Steinhaus in the 1940s, the first constructive procedure for producing an envy-free allocation among three players was not found until around 1960. At that time, John L. Selfridge of Northern Illinois University and, later but independently, John H. Conway of Princeton University found the elegant procedure presented on page 556. Although never published by either, the procedure was quickly and widely disseminated by Richard K. Guy of the University of Calgary and others. Eventually it appeared in several treatments of the problem by different authors.

In 1980, a moving-knife procedure for producing an envy-free allocation among three players was found by Walter R. Stromquist of Daniel Wagner Associates. Then another procedure, capable of being recast as a moving- knife solution of the three-player case, was found by a law professor at the University of Virginia, Saul X. Levmore, and a former student of his, Elizabeth Early Cook.

In 1992, Steven J. Brams, a political scientist at New York University, and Alan D. Taylor, a mathematician at Union College, succeeded in finding a constructive procedure for producing an envy-free allocation among four or more players. In 1994, Brams, Taylor, and William S. Zwicker (also from Union College) found a moving- knife solution to the four-person envy-free problem. No moving-knife procedure is known that will produce an envy-free allocation among five or more players.

Proportional Procedure DEFINITION

A cake-division procedure (for players) will be called proportional if each player’s strategy guarantees that player a piece of size or value at least of the whole in his or her own estimation.

EXAMPLE 3 The Steinhaus Proportional Procedure for Three Players (Lone Divider)

Given three players—Bob, Carol, and ted—we have Bob divide the cake into three pieces (call them , , and ), each of which he thinks is a size or value of exactly one- third. Let’s speak of Carol as “approving of a piece” if she thinks it is of a size or value of at least one-third. Similarly, we will speak of ted as “approving of a piece” if the same criterion applies. Notice that both Carol and ted must approve of at least one piece.

If there are distinct pieces—say, and —with Carol approving of and ted approving of , then we give the third piece, , to Bob (and, of course, to Carol and to ted), and we are done. the problem case is where both Carol and ted approve of only one piece and it is the same piece.

Let’s assume that Carol and ted approve of only one piece, , and hence (of more importance to us) both disapprove of piece . Let denote the result of putting piece and piece back together to form a single piece. Notice that both Carol and ted think thaf is at least two-thirds of the cake because both disapprove of . thus, we can give to Bob and let Carol and ted use divide-and-choose on . Because half of two-thirds is one-third, both Carol and ted are guaranteed a proportional share (as is Bob, who approved of all three pieces).

Explain why it is impossible to have a proportional procedure for Bob, Carol, and Ted in which Bob begins by dividing the cake into three pieces , , and , as in Example 3, and in which the final allocation always gives one of those pieces to Carol and another of those pieces to Ted (i.e., without any additional cutting).

EXAMPLE 4 The Banach-Knaster Proportional Procedure for Four or More Players (Last Diminisher)

Bob cuts from the cake a piece that he thinks is of size one-fourth and hands it to Carol. If Carol thinks the piece handed her is larger than one-fourth, she trims it to size one- fourth in her estimation, places the trimmings back on the cake, and passes the diminished piece to ted. If Carol thinks the piece handed her is of size at most one-fourth, she passes it unaltered to ted.

Ted now proceeds exactly as did Carol, trimming the piece to size one-fourth if he thinks it is larger than this and passing it (diminished or unaltered) on to Alice. Alice does the same, but being the last player, she simply holds onto the piece momentarily instead of passing it to anyone.

Notice that everyone now thinks the piece is of size at most one-fourth, and the last person to trim it (or Bob, if no one trimmed it) thinks the piece is of size exactly one- fourth. thus, the procedure now allocates this piece to the last person who trimmed it (and to Bob, if no one trimmed it).

Assume for the moment that it was ted who trimmed the piece last, so he takes this piece and exits the game. Bob, Carol, and Alice all think that at least three-fourths of the cake is left, so they can start the process over with (say) Bob beginning by cutting a piece from what remains that he thinks is one-fourth of the original cake. Carol and Alice are both given a chance to trim it to size one-fourth in their estimation, and again, the last one to trim it takes that piece and exits the game. the two remaining players both think that at least half the cake is left, so they can use divide-and-choose to divide it between themselves and thus be assured of a piece that is of size at least one-fourth in their estimation.

Describe how Example 4 needs to be modified for the case where there are five players instead of four.