An Online Guide to Envy-Free Cake Division
When visiting a friend, you’re offered a piece of cake. It looks delicious. It is thick chocolate, has cream filling and a dollop of cream on the top. One thing you notice however is that the pieces of cake are not divided evenly. This could be that the portions are larger, or one has more filling or cream than another. You’re allowed to take the first piece, but which piece should you choose?
You might feel that it is important to take the smallest portion, or the one with less cream, the one that is the least desirable on the platter so you do not seem rude. Then you start thinking that maybe the world should learn how to make equal slices of cake, with just the right amount of filling and cream on the top so that everyone is satisfied with their portions. This is something that is not easily done.
Maybe you should go with the greed aspect, and go with the bigger, more cream piece of cake. This might be the rule of the game that you’re playing. There is only one slice that is on your mind, and one slice that is going to fulfill your craving and this would be the biggest one or the one with the most cream, the one that is the most desirable to everyone at the table. Of course, if you’re the one that chooses last, you get the smallest, most undesirable piece of them all. This is unfair to you. Can dividing the cake evenly actually be done? Is this something that can be attempted and achieved?
When there are only two people involved in the cake dilemma, it is much easier. All I have to do is cut the cake, and you choose which piece you would like. Since I am the one in control of the knife, I can choose a size that is the most desirable to me and what I want and you can choose whichever piece you would like. This allows us both to be satisfied. It could work the other way around as well if you were cutting. Throw in another person or more, and things become more complicated. This is because it all depends on who is cutting, and who is able to choose first. Does everyone get a say on what size of cake they would like? There could also be a referee added to allow us to know when a piece is too big or too small and if the pieces are cut just right on an agreed set of cake cutting rules. They might be able to weigh the cake, or make sure the shapes of the cake are equal to each other. Whatever you get, you have to agree on because you have already agreed to the rules. This means that you have a bad feeling afterwards because the decision was ultimately out of your hands on the portion of cake that you received. What if the referee likes cake? What if they are unfair to the proportions? Can you really trust them with your slice? There should be a method that doesn’t use external rules. A few cake eaters, a knife, and a cake is all we need to determine how much you get.
Mathematics and the Relationship to Cake
This is a problem that has stumped a lot of brainy mathematicians in the world for many years. Of course, we thought they were coming up with a new formula or way that we could cut our cake where it would be accepted and everyone would get a fair share, but instead they are just enjoying the cake instead of actually figuring out a way to cut it. They even published papers about how to cut cake, and how to get the best cuts from a cake in journals and highly respected books out in the world. The first to publish a paper on this matter was H. Steinhaus and he wrote ‘The Problem of Fair Division.” This was published in 1948, but there have been advances since then in cake cutting etiquette. There are even hundreds of papers full of research and books that are on the topic of cake cutting. This should not be surprising since mathematicians love cake too.
What is Fair?
There needs to be an understanding when it comes to fair division. You need to know what is fair, and what is not considered fair. You need to be able to cut the cake into five pieces, one for each person so that each person knows that it is one fifth of the cake. This is something that H. Steinhaus went over in his cake cutting definition and method:
One person is the cutter; they hold the knife above one edge of the cake. They can then slowly begin moving the knife across the cake. The slice that is going to be cut increases in size as the knife moves down over the cake. Once the person thinks it is a fair portion for them, they can then tell the cutter to cut the cake at the point where the knife stops. This is their fair portion. They get their slice. Of course, if two or more people want the same piece then the slice can be given to any of them. The process can then be repeated until everyone gets their fair share of cake.
There are downfalls when it comes to this method. The first thing is that there is a reliance on the one who is cutting the cake. This is because they have to make sure to stop and cut when the person says so. They must not move away from the original place that the person said stop. This might be a better task to give to a referee rather than just a regular person because you can incorporate rules. This might not be the best thing for a large group of people either.
Reviews of Methods by Peers
There is another method that has been released by Martin Gardener that allows each of the cake eaters to be able to inspect each of the slices to make sure the pieces are not too large. One piece is cut, and everyone there has to approve that the piece is not too big. This is a fair piece for the person that wants the cake, but everyone else must agree. This goes on until everyone gets their piece of cake approved by everyone else. The people that have approved pieces of cake do not have to approve the remaining pieces.
The downfall of this method is that the amounts of cuts made are generated by trimming of the pieces of cake. This is because if you prefer a smaller portion at first, then you’re not going to get another helping since there will be nothing left at the end after everyone else chose their large portions.
Envy of the Cake
Of course, both methods above have another problem. If you pick a slice that is desirable to you out of the whole cake, you do not know until the rest of the cake is divided and you compare to everyone else’s pieces of cake. This is because their slices might be more desirable then the slice that you received. You of course are going to remain envious of the rest of the pieces of cake. This is when mathematicians decided to do something more to solve this problem. They created the “Envy-Free Cake Division.” This is because they wanted to come up with a way where they could divide the cake so that everyone basically got their first choice out of all the pieces. In 1980, Stromquist came up with a plan that everyone gets their own knife, and involves a referee that wears a large sword:
The referee holds the sword over the piece of cake, and then moves the sword over the cake to make bigger slices. The other people also hold their knives over the cake. They have to be parallel, and then they have to place their knives where they think they could cut the largest portion of the two. Since each person has different judgment on their pieces of cake, the knives will move to different place. Each time the sword moves, the knives move. When one of the players thinks that the slice between their knife and the sword is enough for them, they yell out ‘cut’ and then the piece should be cut for them. Then the rest of the people also get their share of the pieces between their knives and the sword as well. This is the ‘moving knives’ method.
This is, of course, an unfair way to cut cake since each of the players has to be able to stop simultaneously over their pieces. They also have to be able to cut fairly. There is no explanation to why the referee has to have a sword instead of a knife.
Refinement Over the Years
The previous method was only for 3 cake eaters. The new methods that have been added include more than 3 cake eaters since sometimes there might be more than 3. They have come up with a method for 4 cake eaters, but not for 5 yet. The slices might be fragmented, but everyone is envy free, and satisfied with their cake slices. Adding on a fifth cake eater might complicate the process of dividing the cake as well, which is why another was not added since it would be impractical to implement.
Julius Barbanel came up with a method in 2004. This is for 3 people:
Starting from the left, a referee holds a knife over the cake until the person yells out “stop.” The referee can then mark the cake in that spot without cutting through it yet. The person who shouted stop then makes another mark parallel to the first mark made. This then bisects the cake, and makes it into three equal pieces. Then the remaining people choose between the other two pieces on which one they would like. If they choose different pieces then they get those pieces and everyone enjoys their cake. If they do not, and they want the same piece then they have to go through another portion of the process. The referee needs to then put the knife over the left portion of the piece that is wanted and the person that yelled stop originally puts a knife over the right portion. They can then move the knives towards each other. This shrinks piece two, but increases the other two pieces on the cake. One of them must yell stop when they think that it is equal with the other pieces. Then each of the people can then enjoy their cake once it is cut where everyone is satisfied and the pieces match up.
Of course, if they think that the remaining piece is the one that they want, and is bigger than the rest, it can also go through the same process as before to shrink its size, and increase the others to find the perfect size of cake. The person must shout stop, and everyone should be in agreement in the end of the cake cutting process.
This might be a bit confusing and seem like a lot of work, but it has been proven to work when it comes to getting equal pieces of cake in the end. Of course, if you’re at a large event where a lot of people want cake, this is not the process you’re going to want to go through.
Other Types of Applications
There have been over 50 years of research done on cake cutting. The subject is cake, but mathematicians also tell you that you can use these processes for other problems in real life that do not include cake. This includes dispute resolution as well as fair division. Barbanel is one mathematician that states that his solution can extend much further than cake.