Cake Cutting Algorithms – 5 : Envy Free Division

Hi All,

It has been ages since I have posted anything on cake-cutting. But now, I am back and as I promised in my previous post on the same topic I am posting about envy free division. We have already seen in the last post on cake-cutting what envy-free division means.

What is the motivation behind envy-free division? Well, as saint kabir said :

दुनिया अपने दुःख से उतनी दुःखी नहिं है, जीतनी दूसरों के सुख से है |

— संत कबीर

Let us recall our old friends Pinku and Chinku. How do we divide a cake between them so that the division is envy free? It is easy to see that cut-and-choose algorithm would render an envy free division of the cake. The cutter would be envy free because from cutter’s point of view both the pieces are same. The chooser also remains envy free because he gets to choose the largest piece.

What if Rinku joins the party? Now, things get a bit complicated.

We will let Pinku cut the cake in 3 equal pieces named X_1, X_2, X_3. If largest piece from Rinku and Chinku’s perspective are different than we are in a good shape. Because we can give Rinku and Chinku whichever piece they desire and the remaining piece to Pinku. Pinku is still envy free because from his point of view all three pieces were equal. This is an example where disagreement between people makes things easy.

What if Rinku and Chinku both desire to get the same piece. We will let Rinku arrange three pieces in an order so that X_1 \geq X_2 \geq X_3. Now, if X_1 > X_2 we will let Rinku cut X_1 such that X'_1 = X_2 from her perspective. Let the trimmed piece be called L.

Let Chinku choose any one piece between X'_1, X_2, X_3. Rinku can choose whichever piece is left, that is either X'_1 or X_2 . If however, should Chinku choose X_3 we insist that Rinku take X'_1. Chinku is envy free because he got his piece of choice. Rinku is envy free because she got X'_1 or X_2 which she believed to be of equal size but larger than X_3. Pinku is envy free because he gets either X_2 or X_3 which he believed to be of equal size but larger than X'_1.

What about the left over L? We know that even if entire L is given to the person who got X'_1 Pinku would be envy free to that person as from his point of view f_p(X'_1) + f_p(L) = 1/3. Without loss of generality let us assume that Chinku got X'_1. Then we will let Rinku cut L into 3 equal pieces. Out of these three, let Chinku choose first, it is obvious that other two will remain envy free of Chinku. Let Pinku choose second and Rinku will get the remaining piece.

So we have achieved an envy free division of cake amongst 3 persons. Things get more complicated as more number of persons participate in the division.

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: