How To Share a Cake Over the Internet

mikejuk writes "The problem to be solved sounds trivial — cut up a cake so that each person thinks they get a fair share. This classical problem gets even more difficult if the 'players' can't all see what is going on at the same time — for example because they are negotiating via the internet. Now there is an asynchronous algorithm that is guaranteed to be fair and it all depends on using an encrypted auction. The new algorithm is simple and easy to use, and might be the solution to any number of difficult situations where people need to share things so that everyone comes away happy."

Comments

Pie in the sky

[explosivejared]

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.

This seems like a pretty interesting game, fit for nerd parties and the like. Solving territorial or resource disputes? Not so much. You and your friends are basically equal. State actors, ethnic groups, etc. tend not to be perfectly equal. For example, I doubt the Sunni insurgency in Iraq would have submitted to such an auction. The same goes for the actors in the South China Sea, Israel Palestine, really any territorial dispute of note.

I could see something like this being useful for divvying things like mineral resources that crop in international waters, like all those manganese nodes on the ocean floor.

Re:Pie in the sky

[fuzzyfuzzyfungus]

I suspect that the deeper problem is that virtually nobody, even if they use the word 'fair' to describe the outcome they want, actually wants what this outcome provides...

The classic 'cake slicing' analogy holds in situations where it is agreed that the cake ought to be sliced evenly and there is simply the problem of doing the slicing. It does not cover the situations where ownership of the cake is my Manifest Destiny, where the cake was given to you by God, where possession by those subhumans of any part of the cake would be unacceptable, or where it is only just that the invisible hand allocate the cake...

Re:Pie in the sky

[fuzzyfuzzyfungus]

My intended point was not that it is impossible to cope with utility functions in general; but that many real-world actors have hard minimums that add up to greater than one cake across the group you are dividing for. Sometimes, their utility functions even appear to be dependent on the deprivation of others of the cake, not of the possession of the cake themselves(and, in the somewhat-less-fucked-up-but-not-much-more-helpful, intermediate case you have the 'keeping up with the Joneses' where people continually recalibrate their utility functions based on the shares allocated around them).

There are certainly unequal-utility cases that are solvable, I just suspect that those don't include many of the real ones...

Your solution only works for mousse...

[mindwhip]

Did you RTFA?

From the article "A cake is not a mousse. The resource is heterogeneous, different agents can attach different values to different regions of cake."
Or in other words... "I like the thick icing at the edge but you can't stand it and you love the cherry in the middle that I couldn't care less about".

Wait this is /. what was I thinking?

Re:Just cut the pieces into equal portions?!

[zarlino]

Objective C is actually a good language. But too niche and awkward to be used in a funny /. comment.