Slashdot Mirror

← Back to Stories (view on slashdot.org)

How To Share a Cake Over the Internet

Posted by timothy on from the first-you-divide-it-into-bits dept.

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

18 of 123 comments (clear)

  1. Right.. by Anonymous Coward · · Score: 5, Funny

    The Cake is a Lie

    1. Re:Right.. by Karl+Cocknozzle · · Score: 3, Funny

      Riiiiight... There is no cake!

      Fucking matrix again...

      --
      Who did what now?
    2. Re:Right.. by bobbomo · · Score: 2

      Cake, and grief counseling, will be available at the conclusion of the test.

  2. Pie in the sky by explosivejared · · Score: 4, Insightful

    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.

    --
    I got a catholic block.
    1. Re:Pie in the sky by fuzzyfuzzyfungus · · Score: 5, Insightful

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

    2. Re:Pie in the sky by arth1 · · Score: 2

      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.

      Not unless every party involved first agrees that everybody else has a right to an equal share. That is the real problem - the division seldom is.

      Not only is this a solution looking for a problem, but unless my memory fails me completely, it is also solved before, among others by (I believe) Steinhaus.

    3. Re:Pie in the sky by bmo · · Score: 2

      You think this is a motherfarking game?

      That cake is trivial, and this is only a nerd thing?

      http://1.bp.blogspot.com/_D_Z-D2tzi14/TLT2bSprcdI/AAAAAAAAD9M/6v6AJVGNyxw/s1600/Picture+6.png

      --
      BMO

    4. Re:Pie in the sky by subreality · · Score: 2

      I suspect you didn't RTFA: "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."

    5. Re:Pie in the sky by fuzzyfuzzyfungus · · Score: 5, Insightful

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

    6. Re:Pie in the sky by subreality · · Score: 2

      Ah, I see now. Yes, that's a good point.

  3. Re:Just cut the pieces into equal portions?! by Cinder6 · · Score: 4, Funny

    If the players can't see what's being done (as per TFS), then the following method should work perfectly:

    -(BOOL)isSliceFair:(Slice *)slice {
            return YES;
    }

    Related: http://xkcd.com/221/

    --
    If you can't convince them, convict them.
  4. But... by Guppy06 · · Score: 2

    How can the carrier pigeons lift the cake?

  5. Re:Give an Even Better Algorithm by Cryacin · · Score: 4, Funny

    What I really want is algorithm that allows me to have my cake and eat it too [wikipedia.org].

    Easy one. Buy two cakes. qed

    --
    Science advances one funeral at a time- Max Planck
  6. Re:analogs by Anonymous Coward · · Score: 4, Funny

    And what resource isn't finite?

    Human stupidity.

  7. Baking machine by MichaelSmith · · Score: 2

    It would actually be interesting to extend the idea of a bread machine into something more universal. It would have hoppers for various ingredents and an internet connection. The idea would be that you would remotely control it from a web browser and select an item from a menu from its internal storage, but it would also have the ability to use programming instructions from elsewhere, so you really could share cakes.

    --
    http://michaelsmith.id.au
  8. Your solution only works for mousse... by mindwhip · · Score: 4, Insightful

    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?

    --
    [The Universe] has gone offline.
  9. Re:Just cut the pieces into equal portions?! by zarlino · · Score: 3, Insightful

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

    --
    Check out my cross-platform apps
  10. We already have such a system... by __aahlyu4518 · · Score: 2

    It's called honesty and trust. If you don't have those, even a thing like this won't work 'cause people will think the program is rigged.