Cake Cutting Algorithms-1

Hi All,

Well, I know I have already described a few details about cake cutting algorithms on my another blog. But now I would like to write down about this interesting problem in detail. Actually, I happen to come across a very interesting book “Cake Cutting Algorithms : Be Fair If You Can”. The book is written in so lucid manner that even a person without any computer science background will be able to understand most of it.

Problem : Given a cake $X$ divide the cake between Pinku and Rinku in a fair manner.

The word “fair” is tricky over here. How do we define “fair”? Actually, meaning of this word is subjective. What is fair to one person may be injustice to another. If we give 2/3 cake to Pinku, he might think that division is “fair”. Pinku might describe it as a fair division even if entire cake is given to him and none to Rinku. Of course, but such a division is not “fair” from Rinku’s perspective.

So, by “fair” we mean that both are given at least “half” portion of the cake from their own perspective. Okay, so now we have yet another word appearing in double quotes, that is, “half”. It may be the case that Pinku may like cherry and Rinku may like cream. In that case, even if all the cake to Pinku, he might think he did not get even “half” of the cake, as he thinks of cherry as more valuable as compared to rest of the portion. Similarly, Rinku may not be happy with her portion of the cake if no cream is contained in it.

Let $f_{p}(X_1)$ be the function by which Pinku evaluates a given piece $X_1$ of cake, and let $f_r(X_1)$ be the same for Rinku. Of course, these functions are consistent in a sense that they must obey following conditions :

$f_p(X) = f_r(X) = 1$ , that is, if entire cake is given then they will evaluate as they have got entire cake.
$f_p(\phi) = f_r(\phi) = 0$ , that if no cake is given then they will evaluate it as zero.
$f_{p|r}(X_1+X_2) = f_{p|r}(X_1) + f_{p|r}(X_2)$ if $X_1 \cap X_2 = \phi \wedge X_1 \cup X_2 = X$ , if a piece is divided into two pieces, evaluation of sum of these two piece will be exactly equal to the evaluation of the original piece.

Given that evaluation functions obey these constraints, our task is to find out an algorithm to divide $X$ into $X_1$ and $X_2$ such that $f_p(X_i)$ if Pinku gets $X_i$ , similarly for Rinku.

Solution :

Let’s first try various possibilities.

Method 1 : Let Pinku cut the cake and take a piece. The remaining piece will be given to Rinku. This method will fail for obvious reasons.

Method 2 : Let Mom cut the cake into “half” and distribute the pieces to Pinku and Rinku. Well, even if Mom thinks she has cut two “halves”, Pinku and Rinku might disagree as evaluation function of Mom will differ from those of Pinku and Rinku.

Pinku might think Rinku has got 90% of the cake and Rinku might think that Pinku has received 60% of the cake. However, scenario is not bad in this case. We can just switch the pieces and both will happily enjoy their cake. The trouble starts when both of them likes the same piece.

Method 3 : The best stretagy to ensure “fair” division of cake is to let Pinku cut the cake into what he thinks two “halves” and let Rinku choose first. Clearly, Pinku is satisfied with any of the pieces because he evaluates both the pieces as 1/2. Rinku is also satisfied because she gets to choose whichever piece she thinks is bigger. This method is called “Cut and Choose Algorithm”.

Note : One might wonder, why so much fuss about cutting a cake?? Well, cake is symbolic for any resource and Pinku and Rinku are contenders for that resource. Processes contending for processor time slots, Relatives fighting for their share of inheritence, Team members trying to divide team winnings and little kids fighting for “fair” share of their favourite “cake” are all examples where cake-cutting algorithms might help us.

We will look at situations when more than two contenders are involved next time.

–Saurabh Joshi

Tags: cake-cutting algorithms

This entry was posted on March 31, 2008 at 5:54 pm and is filed under algorithm, math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Cake Cutting Algorithms-1”

Cake Cutting Algorithms - 2 « Sbjoshi’s Weblog Says:
April 3, 2008 at 6:20 pm | Reply
[…] Sbjoshi’s Weblog Math, algorithms, theorems, puzzles …. « Cake Cutting Algorithms-1 […]

Me, Myself and Mathematics