Are fair divisions possible ?...

# The Cake-Cutting Problem

## An introductory crime story

Jimmy "The Collectory" emptied the contents of the bag on the table. Mary "The Winker", Jane "Pinky" and Joe "Twitch" stared with their mouths wide open as the table was filled with banknotes, coins, jewels and gold bars. Now they had to divide the spoil. Knowing each other quite well, nobody is ready to trust anybody. It is easy enough to divide the money into four equal shares, but less easy with the non-equal bars (and their number not being a multiple of 4) and jewellery. Besides, each one of them has his or hers own idea on the worth of each of them.

What is the problem? To divide a number of goods into four parts in such a way that (a) each person considers his or her part worth at least 1/4 of the overall worth of the spoil and (b) nobody considers anybody else's part better than his or her own. The problem is not a trivial one since not everybody agrees on the worth of specific items. And since the quartet is, fortunately, not a mathematical one, instead of finding an intelligent way to divide the spoil, they fight. Long enough for the police to find them in their hiding place.

## Fair or Envy-Free?

Note that in a problem of division of a number of goods between a number n of people it is not the same to say that everybody got his fair share (a part worth at least 1/n of the overall worth of the goods) and to say that nobody thinks that somebody got a more valuable part. It is usual to speak of the goods to be divided as the "cake" (imagine a cake made of parts with various flavours, and not everybody has the same taste). If we find a division ensuring that all of the n persons dividing the cake believe their parts to be worth at least 1/n of the worth of the whole cake, we say that the division is fair. If additionaly nobody believes that anybody else got more than 1/n of the worth of the cake, we say the division is envy-free.

Of course, every envy-free division is fair, but not vice versa. For example, let three sisters (Alice, Betty and Carol) divide three books they inherited - a book on science, a book on art and a book on sports. The three sisters do not have the same interests, so although the books themselves are approximately of the same money worth, they do not have the same worth for them. Alice loves science, and also art, but hates sports, so for her the science book is worth, say, 50% of the whole of three, the arts book about 40% and the sports book only 10%. Betty's favourite is also science, but she likes art just a little bit more than sports, so for her the three books have values 50%, 30% and 20% (in the same order). The third sister, Carol, is a sports-freak, and has no special interest either in science or in art, but prefers art to science, so she rates the three books as being worth 20%, 30% and 50%, in the mentioned order. Now, if Alice takes the art book, Betty the science book and Carol the sports book, each one of them got something worth even more than her fair share, 1/3 of the whole value, so this division is fair. But, Alice will envy Betty since Betty got the science book which Alice values more than her own art book.

## Fair Division for Two - The Divide and Choose Method

If only two persons have to divide a "cake", there is a simple algorithm guaranteeing both fairness and envy-freeness: One of the two divides the "cake" in two parts that are equal in his opinion, and the other chooses one of the two parts. Notice that this will generally not be an "exact" division, in the sense that it can happen that not both of them believe they got exactly 1/2 of the "cake". This algorithm can be found in quite ancient texts, e.g. in the Bible (Genesis 13) when Abraham suggest this method to Lot to divide the land between them.

## Threesome is more cumbersome than twosome

For a long time in history there was no general method to achieve a fair division of any "cake" for any three persons (i.e. an algorithm that always results in a fair division, independent on the cake to be divided and personal preferences). Then in 1943 the famous Polish mathematician Hugo Steinhaus found such a method. Let us denote the three persons A, B and C. One of them, say A, divides the cake into three parts he believes to be worth each exactly 1/3 of the "cake" (i.e. A will be equally satisfied whichever of the three parts he gets). The second person, B, either passes (if he believes that at least two of the parts are acceptable, i.e. they are worth at least 1/3 of the whole "cake" in his opinion) or otherwise secretly labels the two too small pieces (note that it is impossible that B or C think all the three parts too small). If B has passed, then C chooses one of the parts, then B and the last is left for A. If B thought two parts worth less than 1/3 each, then C has the same options as B. If C passes, then B first chooses a part, then C and A again gets the last part. But, if C also considers two parts as too small, then at least one of the pieces was considered too small both by B and C, so A has to take that piece. The other two pieces are "reassembled" and B cuts them into half and C chooses one of the offered two parts (as in the Divide-and-Choose method for two). The described procedure is known as the Steinhaus Proportional Protocol (for three). The result is always a fair, but not necessarily an envy-free division.

Example: Imagine that A, B and C want to divide the cake shown in the left picture below. A likes all flavours equally well, so A can divide the cake into thirds in any way that results in three equally sized pieces. Say A cuts along the two blue lines shown in the second picture below. Now, B likes only chocolate, so for him all the value of the cake is in the chocolate part. Consequently, only the rightmost part (with much chocolate) is acceptable for B and he (secretly) labels the other two pieces as "too small". Suppose C  likes lime and strawberry, but not vanilla or chocolate. For him only the middle piece is acceptable. This means that both B and C consider the leftmost part as not acceptable and A has to take that part. The other two parts are reassembled. B and C throw a coin to decide who cuts the cake. Say B is the cutter. He will make a cut (e.g. the red line on the right picture below) dividing the rest of the cake in such a way to obtain two parts with equal amount of chocolate. Now C will choose the part with more fruit flavor, i.e. the upper part, and the part between the red and blue line goes to B.

Two other Polish mathematicians, Stefan Banach and Bronislaw Knaster, devised a proportional protocol, i.e. one that guarantees a fair division, for more than three persons. The protocol is known as the Banach-Knaster Proportional Protocol (or "the last diminisher method"). The algorithm is also quite simple. For ease, let us call the persons who want to divide the cake "players". If there are n (> 2) players, first their order is decided on. Let us denote them and their order by numbers 1 to n. They "play" in rounds, always in that order, and in each round one of them gets his fair share and drops out of the game. In the first round, player 1 cuts out a fair piece of the "cake", i.e. a piece P he considers as being worth 1/n of the whole "cake". Now each of the following players can either agree that P is a fair piece, in which case the player passes, or he can disagree, in which case this player trims the piece to a fair one (cuts the part he believes to be superfluous and this cutted part is reassembled to the rest of the "cake"). After the last player has trimmed or passed, the piece P goes to the last player who trimmed it (if all passed, the first player gets it) and that player drops out. The procedure is repeated with the rest of the "cake" and in each round one player less, until only two players are left (and then they apply the divide-and-choose method).

Example: Imagine that five Croats, Zeljka, Kreso, Kiki, Vladek and Tomica, are stranded on a lone island. They decide to divide it into five parts using the Banach-Knaster protocol. They keep the alphabetic order, so Zeljka goes first and chooses the K part on the leftmost picture below as the one she finds worth 1/5 of the whole island. Kreso considers this part even less worth and passes, but Kiki considers that Anne took too large a piece and reduces it (second picture below). Vladek thinks that even now K is too large and reduces it further (third picture below). Finally Tomica considers this a fair piece and passes, so the K piece as it was defined by Vladek goes to him and he drops out of the game. Again, Zeljka chooses a new part K of the island, disjoint with the Vladek's one, and worth 1/4 of the rest in her opinion (picture 4). Both Kreso and Kiki agree that this is a fair piece so they pass, but Tomica thinks Zeljka's choice to be too large, so he reduces it (picture 5). As he is the last, he gets to keep that part and drops out of the game. Zeljka, Kreso and Kiki now have to divide the rest of the island into three fair pieces. Again, Zeljka chooses a part K she considers fair (picture 6). This part is too large in Kreso's opinion, so he reduces it (picture 7). Kiki agrees that Kreso's choice is not too large, so the part goes to Kreso. Now Zeljka and Kiki divide the rest using the divide-and-choose method. Zeljka "cuts" the rest in two halves (picture 8), of which Kiki chooses the L part, and Zeljka gets to keep the K part. Finally, the island is divided as in the last of the pictures below.

## Is There an Envy-Free Protocol?

It took 16 more years for an envy-free protocol for three players to be found (by American mathematicians John Selfridge and John Horton Conway, 1960). The first envy-free protocol for an arbitrary number of persons was devised in 1995 by Steven Brams and Alan Taylor, but there are still many open questions, e.g. to find protocols with additional good features, simpler envy-free protocols or envy-free protocols in which there is no danger of crumbles. Crumbles? Yes. We shall describe the Selfridge-Conway Envy-Free Protocol, and then you will understand what we mean by crumbles.

The Selfridge-Conway protocol starts like the Steinhaus protocol: player A cuts the "cake" into three pieces that he considers as fair. Now, player B either passes (if he thinks that two or three pieces are tied for largest), or he trims the piece that is largest in his opinion in such a way that he reduces it to the worth of the second one (he creates a tie for the largest piece). The trimmed parts are set aside, as L (leftover). Now, C chooses on of the three parts, ignoring L. If B has trimmed a piece and C has not taken that piece, now B has to take it, otherwise B can take any of the two possible pieces, and A gets the last. Now, if B didn't trim a piece, we are done, otherwise the part L is left to be divided. The player B or C who did not receive the piece trimmed by B now divides L into three fair pieces. The other of B and C (who did not cut L into thirds) chooses one of the parts, then A and the last part gets the one who cut L. This finishes the procedure. Since the trimming in the first part of the protocol will probably result in a small leftover L, and that is to be cut into thirds in the second part of the protocol, it is easy to see that if the "cake" was really a cake, it is quite probable that L would be divided into crumbles.

## Continuous vs. Discrete

The previous methods supposed that our "cake" can be cut into arbitrarily small pieces (or at least into small enough) - imagine a cake, a pizza, a piece of land, a time interval. Methods - protocols - applicable to such "cakes" are referred to as continuous division protocols. If the "cake" consists of indivisible parts, e.g. paintings, cars, jewellery, houses, candies - we speak of discrete protocols. And, if the "cake" has both continuous and discrete parts, the corresponding protocol would be a mixed one.

## Two Discrete Protocols

The first discrete protocol we shall describe is the method of sealed bids, that is particularly appropriate if the number of players and number of goods to be divided are comparable, but it assumes that each player has enough money to pay the possible difference in value and is ready to accept money as a substitute for any of the goods. Also, the method works only if no player has substantial information about the value systems of other players (before the bidding). The procedure is simple: Each player makes a sealed bid, giving an estimate of the money value of each good. Each player’s fair share is computed by dividing the total of the bids by the number of players. Each good goes to the highest bidder for that good and the player adds or subtracts from the money-pot the difference between his fair share and the total value of the goods allocated to him. Any money left in the pot at the end of this process is divided evenly among the players.

The other method, method of markers, is applicable when the number of items to be divided is significantly larger than the number n of players. Each player receives n - 1 markers in "his" colour. The items are ordered into a sequence. Each player independently (and secretly) divides the items into n consecutive segments with markers. The markers of the players form natural sets: the first set of markers consists of everybody's first (leftmost) markers, the second set of everybody's second markers etc. The player with the first marker of the first set receives the segment before the marker, and his markers are removed. The player with the first marker in the second set receives his second segment and his markers are removed, etc., until each player got a segment of items. The possible leftovers can be divided by lottery (if there are less leftover items than players) or by repeating the method.

## Suggestions for a workshop

Fair division methods can easily be demonstrated in a popular workshop. After a short introduction, the attendants should be able to discover the divide-and-choose-method for two by themselves, and can try to suggest a possible fair division method for three (which they will probably fail to do, but it is good practice to notice that it is not a trivial problem). For demonstration of the method of markers, various sorts of candies are ideal. For demonstration of the Banach-Knaster protocol the author has used pizzas, that were made in such a way that the toppings were clearly separated (see the picture on the right) in order to help the attendants to concentrate on which parts the like more or less (and make the cutting easier). For both methods we choose 5 or 6 attendants to divide the candies/pizza according to the two methods. Other methods can be demonstrated also, and for most candies will work fine (one can "improvise" a cake by putting the candies on a heap). Possible additional requisites are cards representing more valuable goods and playing money, for the method of sealed bids. Also, if no candies are available, game-chips or other small items in various colours can be used instead (and the players can assign values to the chips according to their taste in colours).

## What is this good for?

Fair division methods can be applied in many situations: breaking-up of firms, dividing goods in divorces, dividing inheritances, setting up electoral boundaries, ... Of course, many methods are applicable under special assumptions that are not always present in real-life situations (e.g. in most cases players have an idea of each other's preferences), but still the mathematical procedures can help to obtain a more fair solution. If you are interested in reading more about the mathematics of fair division, the author suggests the following: Introduction to Fair Division; S, J. Brams and A. D. Taylor: "An Envy-Free Cake Division Protocol", Amer. Math. Monthly, 102 (1995) 9-18; J. Robertson and W. Webb: "Cake-Cutting Algorithms", Amer. Math. Monthly 107 (2000) 185-188; S. J. Brams, M. A. Jones and C. Klamler: "Better Ways to Cut a Cake", Notices of the AMS 11(52) 2006 1314-1321; Z. Landau, O. Reid and I. Yershov: "A Fair Division Solution to the Problem of Redistricting"; Envy-free Cake Division. Mudd Math Fun Facts; Fair Division Problems and Fair Division Schemes: Cut the Knot - Method of Sealed Bids (and further links on that page); Extra Cake-Cutting Practice, Fair Division Calculator.