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

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 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.

### The Case of Three

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.

Thanks you for this post… great information.

ReplyDeleteworldcup live stream score t20

T20 WC 2016 Live Streaming Score