Forgot your password?
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

Comments Filter:
  • Right.. (Score:5, Funny)

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

    The Cake is a Lie

  • by Anonymous Coward on Friday April 06, 2012 @10:18PM (#39604063)

    n/t

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

    by explosivejared (1186049) * <hagan@jared.gmail@com> on Friday April 06, 2012 @10: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 @11: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...
      • by subreality (157447) on Saturday April 07, 2012 @12:11AM (#39604489)

        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 Saturday April 07, 2012 @12:25AM (#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...
          • by subreality (157447) on Saturday April 07, 2012 @12:47AM (#39604589)

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

          • by Kjella (173770) on Saturday April 07, 2012 @07:34AM (#39605669) Homepage

            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 value, but if we're talking personal items that don't really translate well to dollars then this is a real problem.

            • by Trepidity (597) <delirium-slashdot@@@hackish...org> on Saturday April 07, 2012 @05:59PM (#39609091)

              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.

            • by gr8_phk (621180) on Saturday April 07, 2012 @09:46PM (#39610017)
              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.
              • by garyebickford (222422) <gar37bic.gmail@com> on Saturday April 07, 2012 @11:16PM (#39610347)

                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 negotiating, or facilitating or arbitrating a negotiation, is to find out what each party's BATNA really is.

                IIRC this system was used by Jimmy Carter's negotiating team when they got Israel and Egypt together at Camp David and got them to sign a peace treaty.

        • by Attila Dimedici (1036002) on Saturday April 07, 2012 @12:29AM (#39604531)
          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 Anonymous Coward on Saturday April 07, 2012 @01:54AM (#39604795)

        From the paper

        What are the qualities of this resource? Well, a cake is not a bag of sweets. The resource is continuous, and any given piece can be subdivided into smaller pieces. A cake is not a mousse. The resource is heterogeneous, dierent agents can attach different values to different regions of cake. Finally, a cake is not meant to be eaten alone. No agent has exclusive right to the cake; it is a windfall good, its origin unimportant. We have a cake, and we must cut it.

        So they specifically state that this only works when everyone agrees that the cake should be shared equally. Doesn't make your point any less valid/relevant, just felt that it's worth mentioning.

      • 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 talks about in "Policy Paradox") is if the number of entities changes during the course of the cake cutting and distribution. And also it is possible that the availability of other cakes may change during that time, too (like with the invention of cold fusion or LENR cheap energy devices). So, if the cake is the Earth, but there are future generations, and also new inventions to be discovered, and we might someday move into space, then how do we "divide" it now? And how does an entity, whether human or animal or plant or other, be deemed to have a right to a share?

        As Albert Einstein said, reflecting your points:
        http://www.sacred-texts.com/aor/einstein/einsci.htm [sacred-texts.com]
        "For the scientific method can teach us nothing else beyond how facts are related to, and conditioned by, each other. The aspiration toward such objective knowledge belongs to the highest of which man is capabIe, and you will certainly not suspect me of wishing to belittle the achievements and the heroic efforts of man in this sphere. Yet it is equally clear that knowledge of what is does not open the door directly to what should be. One can have the clearest and most complete knowledge of what is, and yet not be able to deduct from that what should be the goal of our human aspirations. Objective knowledge provides us with powerful instruments for the achievements of certain ends, but the ultimate goal itself and the longing to reach it must come from another source. And it is hardly necessary to argue for the view that our existence and our activity acquire meaning only by the setting up of such a goal and of corresponding values. The knowledge of truth as such is wonderful, but it is so little capable of acting as a guide that it cannot prove even the justification and the value of the aspiration toward that very knowledge of truth. Here we face, therefore, the limits of the purely rational conception of our existence.
            But it must not be assumed that intelligent thinking can play no part in the formation of the goal and of ethical judgments. When someone realizes that for the achievement of an end certain means would be useful, the means itself becomes thereby an end. Intelligence makes clear to us the interrelation of means and ends. But mere thinking cannot give us a sense of the ultimate and fundamental ends. To make clear these fundamental ends and valuations, and to set them fast in the emotional life of the individual, seems to me precisely the most important function which religion has to perform in the social life of man. And if one asks whence derives the authority of such fundamental ends, since they cannot be stated and justified merely by reason, one can only answer: they exist in a healthy society as powerful traditions, which act upon the conduct and aspirations and judgments of the individuals; they are there, that is, as something living, without its being necessary to find justification for their existence. They come into being not through demonstration but through revelation, through the medium of powerful personalities. One must not attempt to justify them, but rather to sense their nature simply and clearly. "

    • by arth1 (260657) on Friday April 06, 2012 @11:20PM (#39604283) Homepage Journal

      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.

      • by Anonymous Coward on Friday April 06, 2012 @11:35PM (#39604365)

        there are only two real solutions: remove the cake from the equation or kill everyone involved.

      • by dgatwood (11270) on Saturday April 07, 2012 @12:28AM (#39604521) Journal

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

      • by James McGuigan (852772) on Saturday April 07, 2012 @09:11AM (#39605987) Homepage

        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 asks the others to choose. The game repeats until all players have accepted a non-conflicting choice. However if the parties are belligerent, or known to be adamant about specific items, then this game is not guaranteed to complete.

        The judgement of King Solomon also provided an alternative solution to this problem by offering to split the baby in half in order to determine who the real mother was, and giving the baby to the one who would rather give the object away rather than see it destroyed. However this only works if the rules of the game are not known about in advance.

        • by JimFive (1064958) on Monday April 09, 2012 @11:42AM (#39619349)
          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 can collude against B because B will always get the smallest piece.
          --
          JimFive
    • by Anonymous Coward on Friday April 06, 2012 @11:44PM (#39604387)

      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.

    • by bmo (77928) on Saturday April 07, 2012 @12:00AM (#39604453)

      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

    • by DarwinSurvivor (1752106) on Saturday April 07, 2012 @12:39AM (#39604557)
      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?
      • by pclminion (145572) on Saturday April 07, 2012 @01:05AM (#39604631)
        You pose it like an objective question with a correct answer. It is not such a thing.
      • by TheLink (130905) on Saturday April 07, 2012 @02:17AM (#39604847) Journal
        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.
        • by DarwinSurvivor (1752106) on Saturday April 07, 2012 @10:43PM (#39610229)
          Tell that to EA. They are *still* resorting to $@&#% rubberband AI to make their games competitive.
          • by TheLink (130905) on Sunday April 08, 2012 @05:02AM (#39611277) Journal
            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 every time you make a single mistake, whether in positioning or action.
            • by DarwinSurvivor (1752106) on Sunday April 08, 2012 @05:46AM (#39611383)
              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 the inconsistency. If the computer is able to do a lap in 1.5 minutes, then their is a goal to reach. If the AI is simply programmed to do the lap 3 seconds faster than you then it completely destroys the players will to play better.
  • by Anonymous Coward on Friday April 06, 2012 @10:19PM (#39604079)

    Too bad humanity is so manipulated low level emotional and out of control
    that most will have a problem, even with such a fair scientific empirical solution
    such as this.

    ie Make everyone think they have a slice slightly bigger than everyone else....
    Then everyone will be truly happy :D

    -k

  • by ThorGod (456163) on Friday April 06, 2012 @10:19PM (#39604081) Journal

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

  • by Anonymous Coward on Friday April 06, 2012 @10:23PM (#39604097)

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

        If someone can explain the encrypted algorithm with better words or examples then that would be great. Thanks!

  • by Anonymous Coward on Friday April 06, 2012 @10:39PM (#39604137)

    Is there icing on it? If not then f-it.

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

    How can the carrier pigeons lift the cake?

  • by gringer (252588) on Friday April 06, 2012 @10:44PM (#39604159)

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

  • by Main Gauche (881147) on Friday April 06, 2012 @11:02PM (#39604219)

    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.

  • by Anonymous Coward on Friday April 06, 2012 @11:17PM (#39604267)

    Simple... One byte at a time!

  • by Tracy Reed (3563) <treed&ultraviolet,org> on Friday April 06, 2012 @11:21PM (#39604297) Homepage

    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?

  • by Lohrno (670867) on Friday April 06, 2012 @11:25PM (#39604327)

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

  • by Anonymous Coward on Friday April 06, 2012 @11:30PM (#39604351)

    This paper assumes that people (groups, governments, etc) will be happy if they get their 'fair share', but doesn't allow folks to define their fair share in relation to anyone else. People are going not to be happy if they see others getting more than them, and this is not allowed to be part of their 'utility function'. So what problem is this solving exactly?
        If you could divide the resources evenly, accurately, with everyone happy you would have done it already.

  • by guttentag (313541) on Friday April 06, 2012 @11:44PM (#39604389) Journal
    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 not cake?). Or they'd wait for you to cut the first piece, then they'd take the rest of the cake.

    Unless the mathematical solution includes an unquestionable, spatula-wielding, hand-slapping matron who defines the term "fair portion," this won't work.
  • by Anonymous Coward on Friday April 06, 2012 @11:45PM (#39604395)

    Easy! The person doing the cutting is the last one to get a piece!

  • by Anonymous Coward on Saturday April 07, 2012 @12:03AM (#39604461)

    and might get you stopped by the T.S.A.

  • by osu-neko (2604) on Saturday April 07, 2012 @12:34AM (#39604545)

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

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

  • by MichaelSmith (789609) on Saturday April 07, 2012 @12:52AM (#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.

  • by flimflammer (956759) on Saturday April 07, 2012 @01:23AM (#39604713)

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

  • by Anonymous Coward on Saturday April 07, 2012 @02:31AM (#39604895)

    These algorithms are fascinating and all.

    But they ALL depend on certain assumptions about human nature...

    In particular that your valuation thresholds are well ordered, and consistent.

    Humans are virtually never either of those. People will value things more to spite others for taking what they want a lot, or for acting in a manner that they believe indicates this. They'll attempt to gain an edge and disrupt the system.

    The only guarantee they can provide is if everyone is consistent and everyone plays fairly, nobody can honestly claim they were cheated.

    Plus... all such systems are subject to collusion.

  • by WetCat (558132) on Saturday April 07, 2012 @02:38AM (#39604913)

    how to eat your cake and have it too ?

  • by Nom du Keyboard (633989) on Saturday April 07, 2012 @04:41AM (#39605181)

    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 one person divides and the other person picks. No fancy secret encrypted system needed.

  • by gravis777 (123605) on Saturday April 07, 2012 @05:04AM (#39605263)

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

    Once again, I am seriously not trying to be a troll, but can someone PLEASE explain wth this article is about, in layman's terms?

  • by billcarson (2438218) on Saturday April 07, 2012 @06:00AM (#39605405)
    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.
  • by retroworks (652802) on Saturday April 07, 2012 @08:07AM (#39605757) Homepage Journal
    Does it work on babies? How about Holy Lands?
  • by MarsDude (74832) on Saturday April 07, 2012 @08:21AM (#39605799) Homepage

    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.

    • by Anubis IV (1279820) on Saturday April 07, 2012 @10:33PM (#39610193)

      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 dictate a fair way to then split up the cake.

      As for people believing the system is rigged, that's inconsequential if it is not actually rigged. We call those false beliefs. It doesn't stop the system from working unless a sufficient number of people refuse to participate in it.

  • by Cow Jones (615566) on Saturday April 07, 2012 @10:39AM (#39606419)

    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 cake as fairly as he could), but participant B might very well consider one slice as more valuable than the other, and thus select what he considers "more than his share".

    The same thing goes for the algorithm in TFA, except that all participants indicate where they would cut the first slice from a (rectangular bar shaped) cake, without seeing the other participants' lines. The third-party automatic arbiter then assigns the smallest indicated slice to the participant who drew that line. This participant will consider his slice as "fair", whereas the others will think that more of the cake than they deserve remains.

    One way to game the system would be to intentionally draw one's line in a position which would give them an unfairly large slice. They probably won't win this round, but assuming that the other participants play fairly, the remaining cake will be slightly larger than (n-1)/n. Do this until only two participants are left. If, on the other hand, everybody places their lines in a way that would give them a larger-than-fair slice, the least greedy player will end up with an unfairly large slice.

Receiving a million dollars tax free will make you feel better than being flat broke and having a stomach ache. -- Dolph Sharp, "I'm O.K., You're Not So Hot"

Working...