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