How To Share a Cake Over the Internet 123
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."
Right.. (Score:5, Funny)
The Cake is a Lie
Re:Right.. (Score:4, Funny)
Riiiiight... There is no cake!
Fucking matrix again...
Re:Right.. (Score:1)
The cake is real, But there is no spoon.
And we are all forked.
Re:Right.. (Score:2)
Re:Right.. (Score:2)
Re:Right.. (Score:1)
The correct quote would be "Let them eat bread"
Re:Right.. (Score:0)
Pink haired girl: It's a piece of cake to bake a pretty cake.
Lil Jon: WHAT?
Best. Mash-up. Evar.
Re:Right.. (Score:2)
Cake, and grief counseling, will be available at the conclusion of the test.
Re:Right.. (Score:1)
Just cut the pieces into equal portions?! (Score:0)
n/t
Re:Just cut the pieces into equal portions?! (Score:5, 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/ [xkcd.com]
Re:Just cut the pieces into equal portions?! (Score:0)
Or you could, you know, use a real language.
Re:Just cut the pieces into equal portions?! (Score:0)
Go is pretty :)
func SliceIsFair(s *Slice) bool {
return true
}
Re:Just cut the pieces into equal portions?! (Score:2)
(defun fair (slice) (t))
Re:Just cut the pieces into equal portions?! (Score:2)
(defun fair (slice) t)
Re:Just cut the pieces into equal portions?! (Score:4, Insightful)
Objective C is actually a good language. But too niche and awkward to be used in a funny /. comment.
Re:Just cut the pieces into equal portions?! (Score:2)
Not so. It was a great source of meta-humor for me, choosing Obj-C specifically to see people's reactions to it.
Re:Just cut the pieces into equal portions?! (Score:0)
Since when is YES a boolean?
Re:Just cut the pieces into equal portions?! (Score:0)
Since when is YES a boolean?
Since i added '#define YES (!0)' to my included header... Fuck off.
Re:Just cut the pieces into equal portions?! (Score:2)
Your solution only works for mousse... (Score:5, 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?
Re:Your solution only works for mousse... (Score:2)
And that's what makes the algorithm nontrivial. It's easy for a homogeneous "cake" where any part is is of objective equal value and another part of equal size. The relevant algorithms are presented in TFA.
It gets interesting if different parts of the cake are of different value to each participant. That makes the algorithm more complicated, but at the same time any real life application might well become easier. You like the icing and the cherry? Ok, I don't care much for either, but maybe if I let you have mine, how about handing me more of the cake?
It's called trading. It's been done for ages. And I guess you could optimize it, even. But somehow I don't feel the urge to optimize a system that has become one of pure greed with little benefit for the general population.
Pie in the sky (Score:5, 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.
Re:Pie in the sky (Score:5, Insightful)
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 (Score:3)
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)
There are certainly unequal-utility cases that are solvable, I just suspect that those don't include many of the real ones...
Re:Pie in the sky (Score:3)
Ah, I see now. Yes, that's a good point.
Re:Pie in the sky (Score:2)
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.
Re:Pie in the sky (Score:2)
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.
A fair sale (Score:2)
Re:A fair sale (Score:2)
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.
Re:Pie in the sky (Score:2)
To be fair, researches mention that (Score:0)
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.
Policy Paradox: Art of Political Decision Making (Score:2)
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. "
Re:Pie in the sky (Score:3)
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:Pie in the sky (Score:0)
there are only two real solutions: remove the cake from the equation or kill everyone involved.
Re:Pie in the sky (Score:2)
there are only two real solutions: remove the cake from the equation or kill everyone else involved.
Hey, I still want MY piece!
Re:Pie in the sky (Score:2)
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....
Re:Pie in the sky (Score:2)
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.
Re:Pie in the sky (Score:2)
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
Re:Pie in the sky (Score:1)
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:Pie in the sky (Score:3)
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
Re:Pie in the sky (Score:2)
Re:Pie in the sky (Score:2)
Re:Pie in the sky (Score:2)
Re:Pie in the sky (Score:2)
Re:Pie in the sky (Score:2)
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.
Re:Pie in the sky (Score:2)
Re:Pie in the sky (Score:2)
You do realize that the US is the only victorious nation in history that not as a matter of common practice did not take sovereignty over defeated nations (see "right of conquest") but actually spent large amounts of money rebuilding them? And pushed to incorporate those ideas into the UN charter, and the post-WWII rules of war? And has since then in most cases actively encouraged and enforced the idea that 'right of conquest' is no longer valid? And continues to negotiate treaties expanding global trade, often not in the short term best interest of the nation?
Have Cake. Will eat it too. (Score:0)
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.... :D
Then everyone will be truly happy
-k
analogs (Score:2)
I'm pretty sure "cake slicing" is analogous to efficiently sharing any finite resource. (And what resource isn't finite?)
Re:analogs (Score:0)
Hope!
Oh wait....
re: analogs (Score:1)
Re:analogs (Score:0)
Re:analogs (Score:2)
* Yes, yes, yes, I know there's still the Sun's gravity, the Moon's gravity, your mom's gravity and many other cellestial bodies' gravities pulling on you.
Re:analogs (Score:4, Funny)
And what resource isn't finite?
Human stupidity.
Re:analogs (Score:2)
And what resource isn't finite?
Human stupidity.
That's only a resource if you're a con artist.
Re:analogs (Score:0)
And what resource isn't finite?
Human stupidity.
That's only a resource if you're a con artist.
Or a politician...
Re:analogs (Score:0)
And what resource isn't finite?
Human stupidity.
That's only a resource if you're a con artist.
Or a politician...
Or an Apple shareholder.
Re:analogs (Score:2)
Re:analogs (Score:2)
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.
Re:analogs (Score:2)
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.
Give an Even Better Algorithm (Score:0)
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!
Re:Give an Even Better Algorithm (Score:5, 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
Re:Give an Even Better Algorithm (Score:2)
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!
The phrase is actually to eat your cake, and then still have it, too.
Anyone can have a cake and then eat it.
Anyone who lives in the U.S., at least.
Re:Give an Even Better Algorithm (Score:2)
CAKE? (Score:0)
Is there icing on it? If not then f-it.
But... (Score:3)
How can the carrier pigeons lift the cake?
Maximum bid? (Score:2)
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).
Re:Maximum bid? (Score:2)
The author omitted that the cake is cut from the other end, (i.e. the maximum bid to the current cake size is selected as the cake piece. Not 0 to the maximum bid.) as specified in the paper at: http://arxiv.org/abs/1202.4507 [arxiv.org]
Wrong link, summary writer (Score:2)
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.
Sharing a cake over the Internet? (Score:0)
Simple... One byte at a time!
Re:Sharing a cake over the Internet? (Score:0)
Also don't forget to make sure your cake is encrypted, or your ISP might not want your internet friends to have any.
Freenet, TOR, etc (Score:2)
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 was disappointed... (Score:1)
I thought this article was going to be about 3D printers and culinary science...
Not how people think (Score:0)
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.
Fair Share? (Score:2)
Unless the mathematical solution includes an unquestionable, spatula-wielding, hand-slapping matron who defines the term "fair portion," this won't work.
Re:Fair Share? (Score:1)
Re:Fair Share? (Score:1)
Easy! (Score:0)
Easy! The person doing the cutting is the last one to get a piece!
Sharing a cake could be dangerous (Score:0)
and might get you stopped by the T.S.A.
Trying to do the impossible... (Score:1)
"...so that everyone comes away happy."
"A" for their algorithmic cleverness. "F" for their understanding of human nature...
Re:Trying to do the impossible... (Score:2)
They are assuming spherical people in a vacuum.
Baking machine (Score:3)
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.
Not a real cake? (Score:2)
So you mean they haven't figured out how to digitize cake over the internet? What a let down.
Re:Not a real cake? (Score:2)
Yes, I'm sorry to have to tell you....
The Cake is a Lie.
Re:Not a real cake? (Score:2)
So several Cakes would be a Lie group?
Won't work. (Score:0)
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.
It's all right, but (Score:2)
how to eat your cake and have it too ?
Cutting Cake Among n People (Score:2)
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.
Re:Cutting Cake Among n People (Score:2)
the problem may be, if one person doesn't really want the biggest piece, he can ruin it for all the others, too.
Re:Cutting Cake Among n People (Score:2)
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.
Uh, what? (Score:2)
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?
Re:Uh, what? (Score:1)
http://en.wikipedia.org/wiki/Cake_cutting [wikipedia.org]
Re:Uh, what? (Score:2)
Thanks, exactly what I was looking for. I understand now.
Let an agent control the cake? (Score:1)
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.
King Solomen Asks (Score:2)
We already have such a system... (Score:3)
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.
Re:We already have such a system... (Score:2)
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.
Only "simply fair" (Score:2)
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.