Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Math Programming Science

How To Share a Cake Over the Internet 123

Posted by timothy 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."
This discussion has been archived. No new comments can be posted.

How To Share a Cake Over the Internet More

How To Share a Cake Over the Internet

Comments Filter:

  • Right.. (Score:5, Funny)

    by Anonymous Coward on Friday April 06, 2012 @09:17PM (#39604057)

    The Cake is a Lie

  • Pie in the sky (Score:5, Insightful)

    by explosivejared ( 1186049 ) * <hagan.jared@NOsPaM.gmail.com> on Friday April 06, 2012 @09:18PM (#39604071)

    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 (Score:5, Insightful)

      by fuzzyfuzzyfungus ( 1223518 ) on Friday April 06, 2012 @10:13PM (#39604255) Journal
      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...

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

        • Re:Pie in the sky (Score:5, Insightful)

          by fuzzyfuzzyfungus ( 1223518 ) on Friday April 06, 2012 @11:25PM (#39604515) Journal
          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...

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

          • Re: (Score:2)

            by Kjella ( 173770 )

            Not to mention fraudulently specifying the utility function to reach a more desired outcome. For example, take a divorce where there's only two goods to be distributed, the house and the money. He loves the house, she hates it. But he knows if he says so he will get little money because he got a lot of utility from the house. So he says he dislikes the house, he'll still get the house as he likes it more than her, but it'll cost him much less utility. Of course in this case the house has an actual market va

            • Re: (Score:2)

              by Trepidity ( 597 )

              Indeed, this seems to depend pretty heavily on the assumption that the utility functions are provided accurately. If that isn't the case, various kinds of gaming are possible. The general problem is studied as "social choice theory", and unfortunately most criteria you might put forth for a "fair" choice rule are provably impossible to satisfy. The classic Arrow Theorem for voting systems is the best-known, but there are a dozen impossibility theorems littering the combine-utility-functions landscape.

            • I've often considered the issue of negotiating price of an item. One thing that seems fair is to take the average of the sellers lowest acceptable price and the buyers maximum price. Even if they could agree that this is "fair", getting them both to play without lying seems a near impossibility.

              • There is a book that covers this pretty well. I think it is called "Getting to Yes" but that may be another, related book. The thesis is that we all have three numbers: What I would love to get, the absolute minimum, and what I'm willing to get. The key to the whole thing is that every party has a BATNA - "Best Alternative To a Negotiated Agreement". This is what I know I can get without negotiating. The zone that is bounded by the parties' BATNAs is the area of negotiation.

                Often the hardest part of negotia

        • Except that it still does not address those situations where one or more of the participants does not consider one or more of the other participants as deserving of any share in the cake, which is what the poster you replied to was getting at.

      • by Deborah Stone explores "fairness": http://www.amazon.com/Policy-Paradox-Political-Decision-Revised/dp/0393976254 [amazon.com]

        The paper itself is an great review, but as they say at the end: "In a more general setting, even with the combined tools of Mathematics, Economics and Computer Science at our disposal it would seem that further progress will be no cakewalk." So, you make good points in those regards.

        For example, one thing the paper does not seem to consider in my cursory skimming of it (which Deborah Stone ta

    • Re: (Score:3)

      by arth1 ( 260657 )

      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.

      • Re: (Score:2)

        by dgatwood ( 11270 )

        Not unless every party involved first agrees that everybody else has a right to an equal share.

        Pretty much what I was thinking. Put another way, there will always be at least one party that thinks that sharing is stealing, even if it's really just copyright infringement....

      • In a two person problem, the solution to ask one side where to draw the "fair" dividing line and ask the other person which "half" they want.

        A three or more person solution could be achieved by asking one person to draw a three+ way dividing line and asking the others if to choose a piece (or veto). If there are are veto's and no pieces have been chosen twice, then the divider gets the remaining piece. Else the lines are undrawn and the next person in the circle gets to redraw the lines from scratch, and as

        • A three or more person solution is to have each person except the last make a single cut that adds one more piece to the cake. Then the last person picks the first piece, and the choosing continues from the start.

          e.g. for three people
          'A' cuts the cake into two pieces
          'B' cuts the cake into three pieces
          'C' chooses one of the three pieces
          'A' chooses one of the remaining two pieces
          'B' gets the remaining piece.

          This method assumes that all parties are interested in a fair division, however. A and C ca

    • Re: (Score:1)

      by Anonymous Coward

      The problem with several of your examples is that one side will settle for nothing but the whole cake, while the other sides won't give up the pieces with extra frosting.

    • Re: (Score:3)

      by bmo ( 77928 )

      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 [blogspot.com]

      --
      BMO

    • Fair doesn not necessarily mean Equal. For instance, you have a 2 person team working on a racing game. 1 person writes the top-down 2d view of the cars racing around. The other writes a complex AI for the computer-controlled cars. Do you think giving them equal portions of the profit would be fair?
      • You pose it like an objective question with a correct answer. It is not such a thing.

      • Re: (Score:2)

        by TheLink ( 130905 )
        Might have to give the "2d view" person more ;) , the AI programmer won't have to deal so much with "user facing" stuff, bosses/etc changing their minds on the colour/appearance of the cars on a daily basis. Unless the racing game is trackless or involves really complex stuff, you wouldn't need a very complex AI for _fun_ gameplay.
        • Tell that to EA. They are *still* resorting to $@&#% rubberband AI to make their games competitive.

          • Re: (Score:2)

            by TheLink ( 130905 )
            No need to give the AI programmer more money if people still keep buying racing games with rubberband AI.

            Most human gamers wouldn't want strong computer opponents. They may think and say that's what they want, but they won't be happy when they get them, because in many games out there the computer would be able to beat or even trash most human gamers consistently.

            Imagine WoW if the enemies weren't so stupid and let players commit genocide on them week after week. Or those fighting games- you get max-comboed
            • There is a HUGE difference between a "strong" computer opponent and rubber band AI. Both can win, yes, but with a "strong" opponent, the better you play, the better you place. With rubberband AI, a noobie will get about the same placement as a professional since the strength of the AI is not fixed. I've seen NFS computer oponents half a lap behind go 600Km/h (250 is the fastest car in the game) to catch up and pass the human player on the last lap. It's not the difficulty that pisses off the players, it's t

  • I'm pretty sure "cake slicing" is analogous to efficiently sharing any finite resource. (And what resource isn't finite?)

    • Well according to the CATO Institute [cato.org] natural resources aren't finite.

    • Re:analogs (Score:4, Funny)

      by Anonymous Coward on Friday April 06, 2012 @10:33PM (#39604357)

      And what resource isn't finite?

      Human stupidity.

      • And what resource isn't finite?

        Human stupidity.

        That's only a resource if you're a con artist.

    • I don't think so. Cake slicing problems (aka dividing fairly) have nothing to do with efficiency (aka allocating according to preferences). One has a global utility function, and the other has multiple individual utility functions.

      • I don't think so. Cake slicing problems (aka dividing fairly) have nothing to do with efficiency (aka allocating according to preferences). One has a global utility function, and the other has multiple individual utility functions.

        Are you saying that "allocating according to preferences" uses a global utility function? Because the whole point of the cake cutting problem is that each participant has different utility functions.

        In response to the person above who said this had already been solved, the asynchronous solution is the the new piece I believe.

        • Are you saying that "allocating according to preferences" uses a global utility function? Because the whole point of the cake cutting problem is that each participant has different utility functions.

          No, I'm saying fairness is a global utility function. In the cake cutting problem, the goal is to maximize the minimum sized piece that someone might get. If you generalize, that's when you introduce utilities that can be different for each player, etc.

  • But... (Score:3)

    by Guppy06 ( 410832 ) on Friday April 06, 2012 @09:44PM (#39604155)

    How can the carrier pigeons lift the cake?

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

    Surely that should be minimum bid? Otherwise all I need to do in order to win is to bid the highest possible value, and then I get the entire cake.

    If the person with the lowest bid "wins" then each person is forced to balance between a bid that's too high (not getting the current piece) and a bid that's too low (not getting enough of the cake).

  • The encrypted auction paper (the whole point of the summary) is at: http://arxiv.org/abs/1202.4507 [arxiv.org]
    and not at the arxiv link provided in the summary.

  • I wonder if this algorithm would have useful applications in such networks to make them share precious bandwidth resources efficiently or avoid other kinds of "tragedy of the commons" issues?

  • I thought this article was going to be about 3D printers and culinary science...

  • The fundamental problem here is the condition that "each person thinks they get a fair share." Everyone's perception of "fair" is different. There is always going to be someone who thinks the definition of "their fair share" is the largest piece in an inevitably-unevenly-cut cake. Even if you did divide it into perfectly equal pieces, they'd feel cheated. Or they'd develop a derivatives-trading scheme to get a few extra crumbs from someone else's plate (they've been doing it with rice for centuries... why n
    • Something like this could at least work in simple cases like sharing bandwidth over a network, where bids are often made by machines on behalf of people, and when most people are somewhat separated apart from what they get. Just like there are many different views on what's fair or not, there is also an abundance of problems and what's needed to solve.

  • "...so that everyone comes away happy."

    "A" for their algorithmic cleverness. "F" for their understanding of human nature...

  • Baking machine (Score:3)

    by MichaelSmith ( 789609 ) on Friday April 06, 2012 @11:52PM (#39604603) Homepage Journal

    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.

  • So you mean they haven't figured out how to digitize cake over the internet? What a let down.

  • how to eat your cake and have it too ?

  • Dividing up a cake fairly amount n people where n>2 is easy.

    Sit in a circle around the cake and randomly pick a starting person. That person cuts out the size piece that he/she thinks is fair. Going around the circle anyone who thinks that it's too big can knock a piece off that goes back into the cake. When no one else will reduce the size any further the last person to reduce the size of the piece to their idea of fair gets that piece and is out of the game. Repeat until n = 2 players, at which point o

    • Re: (Score:2)

      by allo ( 1728082 )

      the problem may be, if one person doesn't really want the biggest piece, he can ruin it for all the others, too.

    • I'm not sure what constitutes cake where you live, but from your description, it sounds more like what the rest of us would call, "pudding." Or "liquid terminator"

      With most western cakes, once you slice a piece off, you can't put it back.

  • I am not trying to troll here, but seriously, what? I read the headline several times, and then read the article summery, and all I can say is that I don't have a clue what this is talking about. I clicked on the first link, and it left me even more confused. This was the entire body of the first link:

    We examine the history of cake cutting mechanisms and discuss the efficiency of their allocations. In the case of piecewise uniform preferences, we define a game that in the presence of strategic agents has equilibria that are not dominated by the allocations of any mechanism. We identify that the equilibria of this game coincide with the allocations of an existing cake cutting mechanism.

    Cutting a cake is a game? I mean, at first I thought it was some sort of distributed computing post, but that doesn't really make sense either - why would distributed computing over the internet have this sort

  • I am probably missing the point, but why can't we have one agent controlling and dividing the cake according to the requests it receives?
    That would result in an envy-free an proportional allocation.

    I find the use of words like "cake" and "mousse" very confusing for someone who is not active in that field.
  • Does it work on babies? How about Holy Lands?

  • We already have such a system... (Score:3)

    by __aahlyu4518 ( 74832 ) on Saturday April 07, 2012 @07:21AM (#39605799)

    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.

    • Even if you look at the two-person problem you can see that honesty and trust don't handle everything. For instance, if you and I are both honest and trustworthy people who understand and believe that of each other, that doesn't prevent us from making mistakes. If I trusted you to cut the cake equally in two and you accidentally cut it such that one side was noticeably larger than the other, honesty and trust would help me to understand that it was an inadvertent mistake, but they wouldn't necessarily dicta

  • If I understand the explanation of the algorithm correctly, the outcome is only "simply fair", meaning that every participant is guaranteed to receive a piece of the cake which he considers at least fair - but some of the participants get what they would value as better than a fair share.

    This is easily demonstrated by the simplest case: one cake, two participants. Participant A draws the dividing line, participant B gets to choose his share. The outcome for A will always be fair (because he devided the c

Slashdot Top Deals

Technology is dominated by those who manage what they do not understand.

Close