×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

How To Share a Cake Over the Internet

timothy posted about 2 years ago | from the first-you-divide-it-into-bits dept.

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

123 comments

Could be really useful... (-1)

Anonymous Coward | about 2 years ago | (#39604051)

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

But I'll bet we'll never get the 1% to sign up for it...

Right.. (5, Funny)

Anonymous Coward | about 2 years ago | (#39604057)

The Cake is a Lie

Re:Right.. (3, Funny)

Karl Cocknozzle (514413) | about 2 years ago | (#39604067)

Riiiiight... There is no cake!

Fucking matrix again...

Re:Right.. (0)

Anonymous Coward | about 2 years ago | (#39604819)

Pink haired girl: It's a piece of cake to bake a pretty cake.
Lil Jon: WHAT?

Best. Mash-up. Evar.

Just cut the pieces into equal portions?! (0)

Anonymous Coward | about 2 years ago | (#39604063)

n/t

Re:Just cut the pieces into equal portions?! (4, Funny)

Cinder6 (894572) | about 2 years ago | (#39604119)

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?! (0)

Anonymous Coward | about 2 years ago | (#39604425)

Or you could, you know, use a real language.

Re:Just cut the pieces into equal portions?! (3, Insightful)

zarlino (985890) | about 2 years ago | (#39605127)

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?! (0)

Anonymous Coward | about 2 years ago | (#39604651)

Since when is YES a boolean?

Re:Just cut the pieces into equal portions?! (0)

Anonymous Coward | about 2 years ago | (#39604837)

Since when is YES a boolean?

Since i added '#define YES (!0)' to my included header... Fuck off.

Your solution only works for mousse... (4, Insightful)

mindwhip (894744) | about 2 years ago | (#39604605)

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

Opportunist (166417) | about 2 years ago | (#39607221)

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 (4, Insightful)

explosivejared (1186049) | about 2 years ago | (#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 (5, Insightful)

fuzzyfuzzyfungus (1223518) | about 2 years ago | (#39604255)

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

Re:Pie in the sky (2)

subreality (157447) | about 2 years ago | (#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 (5, Insightful)

fuzzyfuzzyfungus (1223518) | about 2 years ago | (#39604515)

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

Re:Pie in the sky (0)

Anonymous Coward | about 2 years ago | (#39605311)

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

that's because you're not using your imagination. you need to stop assuming that the "people" are actual persons, and that "cake" represents a tangible asset.
Consider a networking protocol, designed to give multiple users fair access to a common pool of bandwidth. There are many more, but that's the first thing which sprang to mind and frankly I was surprised to see so much of the discussion focusing on actual people fighting over actual food.

The cake is a lie, or rather it's an analogy.

Re:Pie in the sky (1)

Kjella (173770) | about 2 years ago | (#39605669)

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 (1)

Attila Dimedici (1036002) | about 2 years ago | (#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.

To be fair, researches mention that (0)

Anonymous Coward | about 2 years ago | (#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.

Policy Paradox: Art of Political Decision Making (1)

Paul Fernhout (109597) | about 2 years ago | (#39606655)

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 (2)

arth1 (260657) | about 2 years ago | (#39604283)

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 (0)

Anonymous Coward | about 2 years ago | (#39604365)

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

Re:Pie in the sky (1)

DarwinSurvivor (1752106) | about 2 years ago | (#39604551)

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 (1)

dgatwood (11270) | about 2 years ago | (#39604521)

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

Re:Pie in the sky (1)

James McGuigan (852772) | about 2 years ago | (#39605987)

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 (1)

Anonymous Coward | about 2 years ago | (#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.

Re:Pie in the sky (1)

DarwinSurvivor (1752106) | about 2 years ago | (#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?

Re:Pie in the sky (1)

TheLink (130905) | about 2 years ago | (#39604847)

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.

Re:Pie in the sky (0)

Anonymous Coward | about 2 years ago | (#39605391)

You forgot the US whose way of life is based on "what's ours is ours, what's yours is ours"

Have Cake. Will eat it too. (0)

Anonymous Coward | about 2 years ago | (#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

analogs (1)

ThorGod (456163) | about 2 years ago | (#39604081)

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

Re:analogs (0)

Anonymous Coward | about 2 years ago | (#39604175)

Hope!

Oh wait....

Re:analogs (0)

Anonymous Coward | about 2 years ago | (#39604317)

Gravity.

Re:analogs (1)

DarwinSurvivor (1752106) | about 2 years ago | (#39604573)

Gravity is VERY finite. Once you reach the center of the earth, gravity's no longer going to do any work for you! *

* 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 (4, Funny)

Anonymous Coward | about 2 years ago | (#39604357)

And what resource isn't finite?

Human stupidity.

Re:analogs (1)

sixtyeight (844265) | about 2 years ago | (#39604397)

And what resource isn't finite?

Human stupidity.

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

Re:analogs (0)

Anonymous Coward | about 2 years ago | (#39604779)

And what resource isn't finite?

Human stupidity.

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

Or a politician...

Re:analogs (0)

Anonymous Coward | about 2 years ago | (#39604967)

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 (1)

martin-boundary (547041) | about 2 years ago | (#39604363)

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.

Re:analogs (1)

KhabaLox (1906148) | about 2 years ago | (#39604469)

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 (1)

martin-boundary (547041) | about 2 years ago | (#39604601)

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.

Re:analogs (0)

Anonymous Coward | about 2 years ago | (#39606093)

No, the gaol in the problem is to maximize the *utility* eac person gets from there slice. Because of varying utility functions, the pieces will be of different sizes. Did you read TFA (second link)? It actually explains it quite well.

Even though "fairness" is globally defined, that doesn't mean that everyone gets the exact same thing. The value resources differently, so they can all be (collectively) better off by distributions other than everyone get 1/n of the cake.

This idea is also the underpinning of free market transactions. You and I value the same resources differently ( ie we get different utility from them) so we can enter into a transaction in which we both come out with higher utility.

Give an Even Better Algorithm (0)

Anonymous Coward | about 2 years ago | (#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!

Re:Give an Even Better Algorithm (4, Funny)

Cryacin (657549) | about 2 years ago | (#39604211)

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 (0)

Anonymous Coward | about 2 years ago | (#39606875)

Your solution is delicious!

Re:Give an Even Better Algorithm (1)

sixtyeight (844265) | about 2 years ago | (#39604417)

      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.

You insensitive clod! (0)

Anonymous Coward | about 2 years ago | (#39605065)

I have diabetes, you insensitive clod! :(

CAKE? (0)

Anonymous Coward | about 2 years ago | (#39604137)

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

Maximum bid? (1)

gringer (252588) | about 2 years ago | (#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).

Nope... (0)

Anonymous Coward | about 2 years ago | (#39605099)

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.

Sharing a cake over the Internet? (0)

Anonymous Coward | about 2 years ago | (#39604267)

Simple... One byte at a time!

Re:Sharing a cake over the Internet? (0)

Anonymous Coward | about 2 years ago | (#39604433)

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 (1)

Tracy Reed (3563) | about 2 years ago | (#39604297)

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

Lohrno (670867) | about 2 years ago | (#39604327)

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

Re:I was disappointed... (0)

Anonymous Coward | about 2 years ago | (#39604983)

you wouldn't steal a cake

Re:I was disappointed... (0)

Anonymous Coward | about 2 years ago | (#39605299)

If no one is looking, I steal take 40 cakes. I would steal 40 cakes.
That's as many as four tens.
And that's terrible.

Not how people think (0)

Anonymous Coward | about 2 years ago | (#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.

Fair Share? (1)

guttentag (313541) | about 2 years ago | (#39604389)

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! (0)

Anonymous Coward | about 2 years ago | (#39604395)

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

Sharing a cake could be dangerous (0)

Anonymous Coward | about 2 years ago | (#39604461)

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

Trying to do the impossible... (1)

osu-neko (2604) | about 2 years ago | (#39604545)

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

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

Baking machine (2)

MichaelSmith (789609) | about 2 years ago | (#39604603)

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.

Won't work. (0)

Anonymous Coward | about 2 years ago | (#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.

Ask Pinkie Pie (0)

Anonymous Coward | about 2 years ago | (#39604995)

I'm sure she already knows how to do it.

icing on the cake .. (0)

Anonymous Coward | about 2 years ago | (#39605009)

my god, what has happened to slashdot ... i expect Justin Beiber / Lady Gaga stories soon...

Cutting Cake Among n People (1)

Nom du Keyboard (633989) | about 2 years ago | (#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.

Re:Cutting Cake Among n People (1)

allo (1728082) | about 2 years ago | (#39605687)

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 (1)

zippthorne (748122) | about 2 years ago | (#39605903)

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? (1)

gravis777 (123605) | about 2 years ago | (#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?

Re:Uh, what? (0)

Anonymous Coward | about 2 years ago | (#39605455)

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.

Cutting cake is a game in the same way the Prisoner's Dilemma is a game, "Chicken" is a game, negotiating your salary is a game, ...

People are about as much interested in cutting imaginary cake over the internet as they are in confessing or not confessing imaginary crimes to reduce an imaginary sentence.

Let an agent control the cake? (1)

billcarson (2438218) | about 2 years ago | (#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.

I guess I'm the only one (0)

Anonymous Coward | about 2 years ago | (#39605739)

Looks like I'm the only one that finds it amusing that they're cutting the cake with a chainsaw.

We already have such a system... (2)

MarsDude (74832) | about 2 years ago | (#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.

Glossary (0)

Anonymous Coward | about 2 years ago | (#39605815)

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?

Only "simply fair" (1)

Cow Jones (615566) | about 2 years ago | (#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.

Cake is the halting problem (0)

Anonymous Coward | about 2 years ago | (#39606911)

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
   

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...