Cake Cutting Algorithm -4 : Trimming Algorithm

Hi All,

We have seen already in previous post why we need a better algorithm for simple fair division. Let us see a new algorithm for simple fair division for cake-cutting.

Let’s recall our good old friends Pinku, Rinku and Chinku. Pinku can cut a piece X_1 from the cake which he values at 1/3. Pinku will pass on this piece to Rinku to scrutinize it. If Rinku values X_1 at more than 1/3 then Rinku will trim the piece to X'_1 such that f_r(X'_1) = 1/3. This piece now will be further passed on to Chinku. Chinku can either take it or leave it.

So we have three cases :

Case 1 : Chinku takes the piece passed on to him. Clearly, f_c(X'_1) \geq 1/3. Pinku and Rinku can now play “Cut and Choose”. From Pinku’s point of view f_p(X_1) = 1/3 \geq f_p(X'_1), so he will be happy to play “Cut and Choose” with the remaining piece. Same argument can be given for Rinku too. Note that, Rinku may or may not trim the cake in which case X'_1 = X_1. If Rinku does not trim the cake, it means she believes that the rest of the cake is worth at least 2/3.

Case 2: Chinku leaves the piece trimmed by Rinku. In this case, Chinku and Pinku will play “Cut and Choose”. As Rinku has trimmed the piece, she will be happy to take it.

Case 3: Chinku leaves the piece which was passed on to him without Rinku trimming it. In this case, Pinku will take the piece as he originally valued it at 1/3. Remaining two will happily play “Cut and Choose” because both have chosen to leave the piece as they believe it not worth 1/3 from their perspective.

Let’s now go on to generalize the algorithm.

Base case : n=1, Obviously true.

Induction hypothesis : Trimming algorithm divides the cake fairly amongst n-1 contenders.

Induction step : Let first contender cut a piece which he/she values at 1/n. Other contenders one by one will be offered the piece for trimming. Let P_i be the last person to trim the piece. Finally, this piece arrives at P_n who can either take it or leave.

Case 1 : P_n takes the piece. By induction the other n-1 contender successfully divide the cake. P_n is happy because he/she received a piece which he/she values at 1/n. Rest will be happy as they value rest of the cake to be at least (n-1)/n.

Case 2: P_n decides to leave the piece. In which case P_i takes the piece and by induction they all lived happily ever after :-). Here i can be 1 also.

So it seems that we are able to divide the cake fairly between n contenders. But does it actually improve on number of cuts required??? In the worst case, it will so happen that everyone will decide to trim the cake. In which case number of cuts required would be (n-1) + (n-2) + ...+1 = n(n-1)/2. This is a far better bound as compared to O(n!).

Did we manage to solve the problem?? Well, someone said, “People are not as miserable due to their own miseries as they are miserable due to others happiness”. One can clearly see that, even though the first person gets 1/n of the cake, he might find from his point of view that someone else received a more worthy piece then he/she already has.

This gives rise to a new problem:

Envy free cake-cutting : Divide a cake amongst people P_1,\dots,P_n such that \forall i, j f_i(X_i) \geq f_i(X_j).

In simple words, people want a piece which is at least as big as others. So, the constraint is not only to divide the cake fairly, but also to make sure that everybody feels that he/she has got the biggest piece. We will look into this direction in the next post.

–Saurabh Joshi

Advertisements

Tags: , , ,

One Response to “Cake Cutting Algorithm -4 : Trimming Algorithm”

  1. Cake Cutting Algorithms - 5 : Envy Free Division « Me, Myself and Mathematics Says:

    […] 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 […]

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: