Slashdot Mirror
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."
The Cake is a Lie
n/t
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.
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
I'm pretty sure "cake slicing" is analogous to efficiently sharing any finite resource. (And what resource isn't finite?)
PS: I don't reply to ACs.
What I really want is algorithm that allows me to have my cake and eat it too.
If someone can explain the encrypted algorithm with better words or examples then that would be great. Thanks!
Is there icing on it? If not then f-it.
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).
Ask me about repetitive DNA
The encrypted auction paper (the whole point of the summary) is at: http://arxiv.org/abs/1202.4507
and not at the arxiv link provided in the summary.
Simple... One byte at a time!
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...
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.
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.
Easy! The person doing the cutting is the last one to get a piece!
and might get you stopped by the T.S.A.
"...so that everyone comes away happy."
"A" for their algorithmic cleverness. "F" for their understanding of human nature...
"Convictions are more dangerous enemies of truth than lies."
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
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.
So you mean they haven't figured out how to digitize cake over the internet? What a let down.
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.
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.
how to eat your cake and have it too ?
I'm sure she already knows how to do it.
my god, what has happened to slashdot ... i expect Justin Beiber / Lady Gaga stories soon...
I have diabetes, you insensitive clod! :(
The cake is auctioned one subset at a time and you have a fixed total to bid... So if you bid it all on A, you get A but nothing else.
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.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
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?
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.
Looks like I'm the only one that finds it amusing that they're cutting the cake with a chainsaw.
Does it work on babies? How about Holy Lands?
Gently reply
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.
Can someone elaborate on these:
cryptographically secure auction - ? Do they just mean an auction with homomorphic encryption?
homomorphic encryption - Wikipedia says there are no practical homomorphic encryptions, so is this algorithm practical or theoretical? The article makes it sound practical.
maximum bid - as I understand it, the bidder who asks for the smallest slice gets the first slice, drops out of the bid, and the process iterates. This discourages people from waiting too long because they might be left with a smaller slice than they first intend, so everybody gets a "fair" share only in the sense that they get the share that they asked for from the shares that are left. If all the bidders save one request 100% of the cake initially, and the one bidder requests 99%, the winner walks away with 99% of the cake and the rest get to bid over the 1% that's left. Is this truly how this algorithm works?
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.
Ah, arrogance and stupidity, all in the same package. How efficient of you. -- Londo Mollari
by Deborah Stone explores "fairness": http://www.amazon.com/Policy-Paradox-Political-Decision-Revised/dp/0393976254
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
"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. "
A 21st century issue: the irony of technologies of abundance in the hands of those still thinking in terms of scarcity.
I claim that any algorithm to cut up a cake so that each person thinks they get a fair share will either be incomplete (meaning it fails to return the correct result for at least problem), or inconsistent (meaning two or more people get the same part of the cake).
Proof: Pick some 3 year old children. Ask them how much of the cake they would fee is fair for them to get. At least two people will feel that the only fair distribution of cake means that they get the entire cake.
QED
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.