The problem to be solved sounds trivial - cut up a cake so that each person thinks they get a fair share. You have to also throw in the observation that people cheat and are greedy to see that their might be a problem. Now we have an algorithm that works even when the cake is being shared over the internet.

Cutting up a cake might not sound like an important problem but if you rephrase it as sharing resources or territory, then you can quickly see that it has lots of practical applications.  It might even come in useful when there is a real cake to share but I suspect only if the party involves a group of programmers.

Before you decide that cake cutting is simple let's go over a simple case - just two people to share a single cake. If each value the cake in the same way then it is obvious that they both want to get an equal amount of cake. To make things interesting, let's suppose that each person has a utility function u₁ and u₂ that measures how much they value different amounts of cake.

Introducing utility functions makes the problem more interesting because each participant has a different view of the value or "size" of the portions of cake. What matters in this problem is that all of the participants think that they have got at least their fair share, or more, of the cake as measured by their utility function.

So now how do you share the cake between two people?

One solution is the "divide and choose" algorithm.

One of the participants cuts the cake and the other chooses. The cutter will divide the cake into two portions that are equal as measured by their own utility function. The chooser will then select the slice that is bigger according to their utility function (or at random if they appear equal).

You should be able to see that this algorithm has a number of desirable properties.

The cutter's best play is to divide the cake equally because then no matter what piece the chooser takes it appears that the cake has been divided equally. No matter what the difference is between the chooser and cutter utility functions the chooser will always come away happy because they get to choose the biggest or at least equal piece of cake.

So the cake is divided "fairly" from both players point of view - they each get what they measure to be half the cake or better.

To generalize to n people:
an algorithm is simply fair if each participant gets a slice that they value at 1/n or more of the whole.

Thus for n=2 the "divide and choose" algorithm is good and provably "simply fair".

There are algorithms that are simply fair for n>2. For example the "Dubins-Spanier" moving knife algorithm makes use of a "trusted third party" TPP. The TPP moves the knife steadily long the cake - which for simplicity we now assume is a rectangular bar.

As the knife moves the slice S to be allocated grows in size. Each of the participants works out u_i(A) and the first to notice that their u_i(A)=u_i(cake)/n calls stop and is awarded the slice.

They then drop out of the procedure and which repeats with the n-1 participants and the remainder of the cake.

Notice that each participant gets a slice worth at least 1/n of the total cake and there is no incentive to cheat because you could end up with a smaller rather than larger slice.

The moving knife algorithm seems simple but it can be difficult to see that it really is simply fair and to prove that it is takes a bit of work.

There are two problems with this algorithm. The first is that it works only if the division is continuous and if all of the participants can see what is happening without any delay and can shout stop without any delays.

Now we have a new algorithm that works asynchronously and so is suitable for use for sharing algorithms implemented on the internet say. The details are slightly complicated because it involves a cryptographically secure auction where each participant bids in an encrypted form making it possible to know the maximum and who made the bid without knowing the other bid - this requires homomorphic encryption.

With this cryptographic auction in place the new discrete asynchronous algorithm works as follows:

First assume that the cake to be shared runs from 0 to 2^m where m is a large integer and each cutting point is an integer.

1. Each player works out their preferred integer cutting point x_i such that the slice that they would get is worth 1/n of the total cake - by their utility measure.
2. This cut point is encrypted and broadcast to the other participants as a bid in a secure auction.
3. All the players work out the maximum bid and the player who made it - without revealing the other bids - and the winner gets the piece they bid for.

Again just like the moving knife algorithm the result is that the participant gets a slice worth at least 1/n of the entire cake by their measure. As in the moving knife algorithm the participant awarded the piece drops out and the procedure repeats with the remainder of the cake.

There are some subtleties that have to be taken care of to make the procedure efficient but this is the general idea. The algorithm is simply fair and none of the events need to be executed simultaneously.

So the next time you organize an internet party and need to share the cake you can do the job asynchronously.

More Information

A Cryptographic Moving-Knife Cake-Cutting Protocol: arXiv:1202.4507v1

If you would like a more general introduction to cake cutting algorithms - Cake Cutting Mechanisms arXiv:1203.0100v1

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.