Hua Yinglei, Fan Xin, Hu Zhihao, Si Peiyu

Professor Chi-Kwong Li

Mathematicsin Daily Life

June 2014

Fair Division: the art of cutting a cake

Abstract

Fair division is the problem of dividing a set of goods between several people, such that each person receives his/her due share.In this paper, we show how mathematics can illuminate the study of cake-cutting in ways that have practical implications. Specifically, we analyze cake-cutting algorithms where a cake is a metaphor for a heterogeneous, divisible good, whose parts may be valued differently by different people.

Introduction

There are many different kinds of fair division problems, depending on the nature of goods to divide, the criteria for fairness, the nature of the players and their preferences, and other criteria for evaluating the quality of the division.For example, proportional division, also called simple fair division means, that every person gets at least his due share, according to his own value function, i.e., each of the n people gets a subset of Xwhich he values as at least 1/n, while envy-free division meansthat every person gets a share that he values at least as much as all other shares.The question of fair division becomes interesting when the goods to divide are heterogeneous and an envy-free division is desired.

The cake discussed in the paper is a metaphor. And the algorithms in the paper are mainly used to deal with other divisions in daily life such as the distribution of social welfare, divorce settlements, airport traffic management, to name just a few.

Cut-and choose method—2-people situation

Let’s start from a simple, but famous 2-person, 1-cut cake-cutting procedure.

The classical method ‘divide-and-choose’ is the key. It means that A divides this cake and B chooses in advance of A. For A’s own benefit, he must divide this cake, and he will divide it into two equal parts because he does not know which part B will choose. For B, he chooses cake in advance of A, so he has the chance to choose the bigger one. As a result, it’s a fair method.

However ‘divide-and-choose’ is not totally fair. Because if A still focuses the volume of this cake, then he can get half value of this cake, but things change if left half of this cake is with chocolate on it, and the right half is with strawberries on it. In fact, I prefer chocolate, and then if I choose the left half, then I can get more than half value of this cake. Obviously, it’s not fair. A more fair division is that A gets all the strawberries and small part of chocolate and B gets the rest of it.

In order to achieve this ideal division, A and B should know the other people’s subjective valuation. To tell the truth, it’s hard to realize in modern society. Therefore, we have to turn to ‘divide-and-choose’ method. The principle behind this method is called ‘proportional division’, which means that if n people share this cake ,then everyone can get at least one-nth value of this cake according their own valuations.

Proportional division

There are two solutions to proportional division with n people. The goal of proportional division is that each of the n people gets a subset of X which he values as at least 1/n.

  • Using the idea of induction

In this algorithm, we start from the well-known 2-person, 1-cut cake-cutting procedure, “I cut, you choose”. Let’s assume the players are P1 and P2. Then the cake can be divided into two equal halves with the cut-and-choose method. Next, P1 and P2 cut their half of cake into three smaller pieces. So we now get 6 small pieces of cake in total. Then P3 comes and he chooses one piece of cake from P1 and another piece from P2. So each of them now get 2 pieces of cake. Obviously, P3 will choose the largest 2 pieces. So if P1 or P2 doesn’t divide the cake fairly, the small piece will be left to himself and he will get less than 1/n of the cake, making others get more than he does. As rational people, P1 and P2 will try to avoid such situation and divide the cake in three equal pieces. Since each of the players get 2 pieces of cake and the pieces are equal in size according to our analysis, now P1, P2 and P3 each has the same amount of cake and a three-person proportional division is done.

What if we have 4 people? Using the idea of induction, we just need to repeat the process above. P1, P2 and P3 divide their own share of cake, at this time, into 4 small pieces. So we have 12 pieces in total. P4 comes and choose one piece from each person. 12 pieces can be divided into 4 groups and each group has 3 pieces. Now each one gets 3 pieces of the cake and the pieces will have the same size according to the previous analysis. And 4-person proportional division can also be done. Here comes the induction. When (n-1)-person proportional division is done, n-person proportional division can also be done. And n people can cut the cake fairly according to the standard of proportional division.

  • The Final Reduction Algorithm

Here is the other different way called “the final reduction algorithm” to cut the cake for proportional division.

If there are n (>0) people in total, the first person cuts the cake in n parts according to his valuation and gives the cut-cake to the next person. Then the second person has two choices. One of them is giving the cut-cake to the next one directly if he thinks the first cut is fair enough. Otherwise, he must cut down the size of cake into 1/n to modify it according to his valuation. And so on, everyone has a chance to modify the cake into 1/n and give it to the next person. We have a rule that the person who is the last one to cut the 1/n part will get this part of cake. Until now, we finish the first step. Other n-1 people will repeat this step until everyone gets the 1/n part of cake.

The cleverness of this way is that everyone must cut and modify the cake into 1/n according to their valuation consciously. No one can dare to cheat because if anyone cuts the cake into piece which is smaller than 1/n of the cake deliberately, people who follow him will not modify it and as the rule he must get this piece of cake in the end. If anyone gives a piece of cake which is bigger than 1/n of the cake to someone else, what he get in the final will probably less than 1/n.

This is the perfect solution to fair division. But sometimes this is far from the satisfaction of people in daily life.

Selfridge-Conway Algorithm—solution to envy-free division

Now let’s make the situation more complex and taking each player’s subjective valuation into consideration.

In problems of envy-free division, the Selfridge–Conway discrete procedure presents a solution for three players. It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told it to many people, but Selfridge did not publish it. John Conway discovered it independently in 1993, and also never published it, but the result is attributed to them in a number of books. This procedure was the first envy-free discrete procedure devised for three players. Solutions for n players were later found by Steven Brams and Alan Taylor.

A procedure is envy-free if each recipient believes that (according to its measure) no other recipient has received more than he has. In their solution, the maximal number of cuts in the procedure is five. The pieces are not always contiguous.

  • Selfridge–Conway division

Suppose we have three players P1, P2 and P3. Where the procedure gives a criterion for a decision it means that criterion gives an optimum choice for the player.

  1. P1 divides the cake into three pieces he considers of equal size.
  2. Let's call A the largest piece according to P2.
  3. P2 cuts off a bit of A to make it the same size as the second largest. Now A is divided into: the trimmed piece A1 and the trimmings A2. Leave the trimmings A2 to the side for now.
  4. If P2 thinks that the two largest parts are equal, then each player chooses a part in this order: P3, P2 and finally P1.
  5. P3 chooses a piece among A1 and the two other pieces.
  6. P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it.
  7. P1 chooses the last piece leaving just the trimmings A2 to be divided.

Now, the cake minus the trimmings A2 has been divided in an envy free manner. The trimmed piece A1 has been chosen by either P2 or P3. Let's call the player who chose it PA and the other one Player PB.

  1. PB cuts A2 into three equal pieces.
  2. PA chooses a piece of A2 - we name it A21.
  3. P1 chooses a piece of A2 - we name it A22.
  4. PB chooses the last remaining piece of A2 - we name it A23.
  • Analysis

Let's see why the procedure is envy-free. It must be shown that each player believes that no other player received more than he had. Without loss of generality, we can write (see illustration above):

  • PA received: A1 + A21.
  • PB received: B + A23.
  • P1 received: C + A22.

In the following analysis "largest" means "largest according to the player":

  • PA received A1 + A21. For him, A1≥B and A1≥C. And he considers his choice A21 to be the largest piece of A2. So no other player received more than he did: A1 + A21 ≥B + A23, C + A22.
  • PB received B + A23. For him, B≥A1 and B≥C since he chose B. Also, he is the one that cut A2 in 3 pieces, so for him all those pieces are equal.
  • P1 received C + A22. For him, C≥A1 and C=B.
  • P1 believes that PB didn't receive more than he did. In other words: C + A22 ≥B + A23. Remember that P1 chose his piece of A2 before PB, thus A22 ≥A23 in his view.
  • P1 believes that PA didn't receive more than he had. In other words: C + A22 ≥A1 + A21. Remember that for P1, C is equal to A since he cut the cake in the first round. Also, A=A1+A2=A1+(A21+A22+A23); therefore C ≥A1 + A21. (Even if PA took the whole A2 and P1 did not receive A22, P1 would not envy PA.)

Conclusions and applications

Most of the algorithms require us to divide the cake into small pieces and combine them together again into different larger sizes. Actually we rarely need to cut a real cake with such accuracy when sharing the happiness of eating a cake. Nevertheless, the algorithms are really useful in areas such as auctions, divorce settlements, electronic spectrum and frequency allocation, airport traffic management, or exploitation of Earth Observation Satellites.

As we can see, the cake cutting algorithms becomes more and more complex with more and more players and more and more complicated situations. However, the more complex the situation is, the closer it is to our real life. To solve the problem of fair division, we still have a long way to go.

Moreover, fair division is an active research area in mathematics or game theory and it also appears in popular culture.

  • Example 1: In Numb3rs season 3 episode "One Hour", Charlie talks about the cake-cutting problem as applied to the amount of money a kidnapper was demanding.
  • Example 2: A Dinosaur Comics strip is based on the cake-cutting problem.

References

  • “Fair Division.”N.p., n.d. Web. 22 June.2014
  • Brams S J, Jones M A, Klamler C. Better ways to cut a cake[J]. Notices of the AMS, 2006, 53(11): 1314-1321.
  • 顾森.思考的乐趣：Matrix67数学笔记. 北京：人民邮电出版社，2012

Appendix—Self-evaluation of the presentation

  • Preparation for the presentation

To tailor the information to our needs and make things clear for a better time management.

  • During the presentation

To take control of the time, and adjust the content according to the time limit flexibly.

To use more pictures and clearer pictures, making the logic clear and easy to understand when talking about Selfridge-Conway algorithm.

To add more interactions and make more classmates involved when explaining the algorithms of cutting a cake if we had more time.

  • Things we learnt from other groups

To be prepared for possible accidents and make a final check on all the materials to be displayed such as PPT and videos.

To talk without a script and speak confidently.