The Cake Cutting Problem - Fair Division Problem (Part 1)

As humans we tend to own everything. When dividing something among people we need to own a fair portion, if not a bigger portion. Thus problems regarding dividing has become the source of many conflicts, wars and sometimes crimes. Cake Cutting problem is an interesting thing in mathematics which deals with dividing a cake between several people such that each person is fully satisfied with the piece he gets.The generalized dividing problem is also known as the fair division problem and there are several algorithms to solve this. This problem is very much associated with real life problems.

Basics

Before solving the problem of fair division the word "Fair" should be defined properly. Fair can mean two things. The first condition is everyone should be satisfied, that the piece they got is at least an equal portion of the total resources. That is, if the resource is divided between n people each person should feel that they have received at least 1/n portion. The other condition is that every person should feel that no one has received more than himself. In other words everyone should feel that they received the largest part. Satisfying the first condition is less problematic than the second. Thus sometimes the dividing problem is limited to satisfy only the first condition. Yet the human behavior demands not only the first condition but also the second condition should be satisfied so that everyone is happy about the division of the resource. The problems which mandate the second condition is also known as Envy Free division. 

Also the criteria to decide the value of each portion is important. In the simplest case the value of each piece is based on its size. But in complex (and practical) cases the value of each piece will be different     to each participant. One participant may value a piece of cake with more icing on it while one prefer a  piece with cherries. Even under these conditions the definition of fair will help us to tackle the fair division problem easily.

Simplest Case

The simplest case is the division of a cake between two people. This can be easily solved using the divide and choose method. In this scenario one person divide the cake into two pieces which he thinks that is fair. The other person gets the chance to select a piece he like. The other piece is left to the first person. As the first person initially divided the cake in to two fair parts he gets a fair portion. Although second person do not agree with the division of the cake in to two as fair he gets the chance to select any piece. Thus he will also be satisfied with the piece he gets.

The Case of Three

The next case is the division of a cake between three people. There are several methods to solve this fair division problem for three people. Almost all these methods can be generalized to solve problems containing more than three people.The divide and select approach which was used for two person case can not be extended to solve this.  And there are solutions which seems plausible but proved wrong when thoroughly analyzed.

Let's now analyze one such incorrect approach. Let the three people be named as A,B and C. This solution includes following steps.

• A cuts the cake in to two pieces where he thinks one is 1/3 and the other is 2/3 of the cake.
• B cuts the 2/3 part of the cake in to two fair pieces.
• C chooses any piece he likes.- So C is satisfied
• Then A chooses.
• Finally B chooses.

Now lets analyze the above solution. Since C selects first, clearly C is satisfied. If C has chosen a piece that is cut by B then A can select the initial piece he cut. If C has selected the initial piece cut by A, then A can select one of the pieces cut by B. As A initially divided in to 1/3 and 2/3 parts, at least one piece cut by B should be 1/3. So A is satisfied in any case. The problem is with B. If B thinks the initial cut by A is not fair (ie. The smaller piece is larger than 1/3 of the cake) B is only satisfied with that piece. Thus if that piece is selected by A or C then B is left unsatisfied. Thus the solution given here is not correct.