Geez there's plenty of cake for everyone don't be ridiculous
November 5, 2012 11:39 AM Subscribe
I remember reading a description of a fair(ish) cake-cutting procedure for an unlimited number of people. It was NOT the one described in this post on the blue with all the broken links. Please help me find either the original source or a more coherent description than the one I provide here.
I the method was presumably not mathematically optimal, but it is fairly practical. And it's really much better suited to literal cake cutting and would be hard to apply to other "fair division" processes. I believe this is the way it worked (imagine either a long loaf-shaped cake or a round cake in which a "starting" cut has already been made):
One person, the cutter, moves the knife over the cake and any person who has not yet received cake can call out for the knife to stop and a slice to be cut, which that person then takes. The cutter then keeps moving the knife until the next person calls out; and so on, until there is only the cutter and one other person left, at which point the "I cut, you choose" method is applied. (This seems maybe wrong, though - the cutter could get shafted. Maybe the cutter sets aside a piece at the beginning?)
Basically, people are going to call out as soon as there is a slice that is of acceptable size/quality to them, for fear of someone else calling out first and getting that slice.
Does this ring a bell with anyone? I have been thinking about it for about 48 hours now and it is driving me crazy. Which is kind of silly given that among my acquaintance cakes are generally way too big for the party, such that everyone can have as much damn cake as they want.
I the method was presumably not mathematically optimal, but it is fairly practical. And it's really much better suited to literal cake cutting and would be hard to apply to other "fair division" processes. I believe this is the way it worked (imagine either a long loaf-shaped cake or a round cake in which a "starting" cut has already been made):
One person, the cutter, moves the knife over the cake and any person who has not yet received cake can call out for the knife to stop and a slice to be cut, which that person then takes. The cutter then keeps moving the knife until the next person calls out; and so on, until there is only the cutter and one other person left, at which point the "I cut, you choose" method is applied. (This seems maybe wrong, though - the cutter could get shafted. Maybe the cutter sets aside a piece at the beginning?)
Basically, people are going to call out as soon as there is a slice that is of acceptable size/quality to them, for fear of someone else calling out first and getting that slice.
Does this ring a bell with anyone? I have been thinking about it for about 48 hours now and it is driving me crazy. Which is kind of silly given that among my acquaintance cakes are generally way too big for the party, such that everyone can have as much damn cake as they want.
Best answer: Appropriately enough this is known as the moving-knife procedure.
posted by jedicus at 11:57 AM on November 5, 2012 [3 favorites]
posted by jedicus at 11:57 AM on November 5, 2012 [3 favorites]
This seems maybe wrong, though - the cutter could get shafted.
The cutter chooses how the remaining cake is divided, the only way they would get "shafted" is if they cut it into very uneven portions and expected the remaining person to choose the smaller piece.
This process does seem to assume that on average no-one will take more than their "fair share" though otherwise you could run out of cake - or the portions get smaller and smaller as the game goes on.
posted by missmagenta at 12:10 PM on November 5, 2012
The cutter chooses how the remaining cake is divided, the only way they would get "shafted" is if they cut it into very uneven portions and expected the remaining person to choose the smaller piece.
This process does seem to assume that on average no-one will take more than their "fair share" though otherwise you could run out of cake - or the portions get smaller and smaller as the game goes on.
posted by missmagenta at 12:10 PM on November 5, 2012
Response by poster: missmagenta, the cutter chooses how the remaining cake is divided, but the remaining amount of cake could be very small if the last people to call out "cut" were very reckless. And as I understand it, the portions getting smaller and smaller is actually part of the deal - the people who pick later in the game had the *chance* to get the big early pieces but chose not to for whatever reason (perhaps because they greedily hoped to get an even more oversized piece). A canny player of the game will choose not what so much what he thinks is his fair share, but rather as big of a piece as he can get before someone else calls for the cut.
jedicus, that's it, of course! Thank you!
posted by mskyle at 12:54 PM on November 5, 2012
jedicus, that's it, of course! Thank you!
posted by mskyle at 12:54 PM on November 5, 2012
Wouldn't the following generalization of "i cut you choose" also work? The cutter cuts a slice he or she thinks is fair. The first chooser either accepts that slice or leaves it for the cutter, taking the rest of the cake but also the obligation to continue the game with the next chooser. In addition to the normal advantages to this system of the cutter being motivated to make a fair slice, you have the additional advantage that a good cutter will probably get to cut for more people, and bad cutters will be cut off, no pun intended. It also eliminates the risk-taking behavior from the moving-knife procedure.
posted by ubiquity at 1:18 PM on November 5, 2012
posted by ubiquity at 1:18 PM on November 5, 2012
Wouldn't the following generalization of "i cut you choose" also work? The cutter cuts a slice he or she thinks is fair. The first chooser either accepts that slice or leaves it for the cutter, taking the rest of the cake but also the obligation to continue the game with the next chooser.
The moving-knife algorithms and the "I cut, you choose" algorithms are what are called "envy-free", in that despite how the players prioritize the various parts of the "cake", nobody is left with a piece of the cake they'd rather trade for someone else's. Your algorithm isn't envy-free, since players 3 through N (player 1 = first cutter, player 2 = first choose) never get a crack at the first slice.
As an example: suppose that there's a delicious-looking frosting rose on the cake. You would give anything to get that particular frosting rose. If it's in the slice cut off by the first cutter, and you're "Player 3", then you won't end up with that frosting rose, and so you envy whoever ended up with it. Thus, it's not an "envy-free" algorithm.
posted by Johnny Assay at 1:55 PM on November 5, 2012 [1 favorite]
The moving-knife algorithms and the "I cut, you choose" algorithms are what are called "envy-free", in that despite how the players prioritize the various parts of the "cake", nobody is left with a piece of the cake they'd rather trade for someone else's. Your algorithm isn't envy-free, since players 3 through N (player 1 = first cutter, player 2 = first choose) never get a crack at the first slice.
As an example: suppose that there's a delicious-looking frosting rose on the cake. You would give anything to get that particular frosting rose. If it's in the slice cut off by the first cutter, and you're "Player 3", then you won't end up with that frosting rose, and so you envy whoever ended up with it. Thus, it's not an "envy-free" algorithm.
posted by Johnny Assay at 1:55 PM on November 5, 2012 [1 favorite]
Response by poster: Oh, and my problem of the cutter getting screwed over is eliminated if the cutter is a disinterested party who is not getting any cake regardless (gluten-free? diabetic? robot?). That would solve the problem of the cutter getting shafted, so long as you had a cake robot handy.
posted by mskyle at 4:03 PM on November 5, 2012
posted by mskyle at 4:03 PM on November 5, 2012
In the algorithm I learned as a kid, the 'cutter' isn't any special role - anyone can ask for the cutter to stop. That prevents the cutter from getting screwed.
posted by muddgirl at 5:38 PM on November 5, 2012
posted by muddgirl at 5:38 PM on November 5, 2012
I think that the cutter can't get shafted. Imagine only three people are splitting the cake, and everyone wants to maximize their share. Then, once the knife has marked out 1/3 of the cake, either of the two non-cutters should call for a cut, since to not do so would allow the other non-cutter to call for a cut, and receive greater than 1/3. The remaining 2/3 will be split between the other two participants by the cut-choose method.
(If people are allowed to collude, then the last two non-cutters can shaft the cutter. They agree to wait to call for a cut until the slice has become very large, and then later divide the monster slice between themselves. Of course, if we are truly in pessimistic game-theory land, there's no incentive for the person who gets the large slice not to shaft their co-conspirator in turn.)
(Now I'm thinking about whether and how cake-slice insurance and a cake derivatives market would (/not) increase the fairness of the scheme.)
If I ever get invited to a libertarian potluck I'm going to bring cupcakes, exactly one per attendee. Socialism with frosting!
posted by dendrochronologizer at 12:45 AM on November 6, 2012 [1 favorite]
(If people are allowed to collude, then the last two non-cutters can shaft the cutter. They agree to wait to call for a cut until the slice has become very large, and then later divide the monster slice between themselves. Of course, if we are truly in pessimistic game-theory land, there's no incentive for the person who gets the large slice not to shaft their co-conspirator in turn.)
(Now I'm thinking about whether and how cake-slice insurance and a cake derivatives market would (/not) increase the fairness of the scheme.)
If I ever get invited to a libertarian potluck I'm going to bring cupcakes, exactly one per attendee. Socialism with frosting!
posted by dendrochronologizer at 12:45 AM on November 6, 2012 [1 favorite]
In the algorithm I learned as a kid, the 'cutter' isn't any special role - anyone can ask for the cutter to stop. That prevents the cutter from getting screwed.
This sounds right - if the cutter has the same right to call a stop as anyone else, he or she has exactly the same chance as anyone else to get a fair slice of the cake. Collusion between other people wouldn't matter, because colluders can only delay the time at which they claim their slice and have no way to prevent a non-colluder from claiming it at the point where the slice is fair.
posted by A Thousand Baited Hooks at 3:03 AM on November 6, 2012
This sounds right - if the cutter has the same right to call a stop as anyone else, he or she has exactly the same chance as anyone else to get a fair slice of the cake. Collusion between other people wouldn't matter, because colluders can only delay the time at which they claim their slice and have no way to prevent a non-colluder from claiming it at the point where the slice is fair.
posted by A Thousand Baited Hooks at 3:03 AM on November 6, 2012
« Older How do I respectfully dispose of my deceased mom's... | Need some carcinogen-free lipsticks. Newer »
This thread is closed to new comments.
posted by telegraph at 11:53 AM on November 5, 2012