Similar to this is the white elephant method: each player in order choose to CUT a slice for themselves, or TAKE someone else’s slice. If your slice is taken, you are inserted to the front of the queue. A slice that is taken cannot be re-taken until a new slice is cut. Go through the queue until each player has a slice.
No player has an incentive to cut a larger than fair slice, as it will be stolen from them. You can still collude with the final player, however (who is guaranteed to get the largest larger than fair slice)
this wouldn’t guarantee that each person is satisfied with their piece of cake though. Even if everyone is attempting to create a fair piece, some people may consider certain pieces larger than others. e.g. if 3 out of 4 people agree that 2 pieces are a little larger than fair and 2 are a little smaller than fair (totally possible, if the 1st person cuts the first a little large but he thinks it’s fair, 2 will take it. then he cuts the 2nd the same way, and 3 takes it. Now 1 cuts the remainder exactly in half and is happy with his piece. 4 doesn’t want the last piece because the first 2 are larger, so he takes from either 2 or 3. then whichever was taken from, takes from the other. then lastly 2 (or 3) is stuck with the final piece of cake, which by his reckoning is smaller than fair.
The thing is, in order to be able to guarantee that a given person is getting what they consider a ‘fair’ piece, they have to either a) have cut it themselves or b) have chosen it from a set of pieces that contains at least 1 piece that they consider to be fair. I am not sure there is a way to have people make cuts based on their idea of what a fair piece is which might not jive with other peoples and still satisfy those requirements. So the answer has to be more along the auction style that was suggested earlier where people basically bid on how small a piece they are willing to take.
[quote=“rethfernhim, post:10, topic:77643, full:true”]
For three people, the first person cuts a piece. The second person gets to choose between taking that piece, or dividing the remaining cake into two pieces. If person 2 takes the first slice, we’re back to the n=2 problem. If person 2 slices, then person 3 gets to choose their slice, then person 1 chooses a slice, and person 2 is left with the last slice.
This should work for all n…unless I’m missing something. Thoughts?
[/quote]Person one has bad eyesight, so cuts the cake into more like 40/60, but thinks it’s 33/67. Person 2 takes the 40% slice. Person 1 cuts again, correctly this time into 30/30. Person 3 demands person 2’s slice since it’s obviously larger. Fisticuffs ensue.
Related to this is “equitable sequencing”. Let’s say we’re divvying up baseball cards. Alternating choices favors the first person, but you can mix things up using the Thue-Morse sequence…
Simply invite people with sufficient combinations (at least one per person) of:
• dietary restrictions: medical, religious, whatever
• caloric intake caps
• personal preferences
With an appropriately constructed cake (including, for example, GMO flour, gluten, milk, bacon)
OK, I teach this stuff, so have been avoiding commenting here, but part of what makes this problem interesting is that different people might judge pieces differently. For example, if your cake is frosted, then person A might prefer more frosting, person B might prefer more cake and less frosting. Likewise if there is more than one kind of frosting…
It is also quite hard to generalize algorithms that work for 2 people to more people and still stay “envy-free” (that is, not only do you think you got at least 1/n of the cake, you also don’t think anyone else got more than you did).
Hmm…I think that assumes that people are selfish or don’t have manners…In my experience, folks will tend to take the smaller and leave the bigger for someone else. (Also, no one takes the last piece of anything on the platter…)
everyone is satisfied he has at least 1/n of the cake.
Where have all the pedants gone who deconstruct the wording of a puzzle?
Allow me to make an attempt.
First, I’m assuming that “he” is being used in the old(ish) fashioned sense of “each member of the group, regardless of gender”, and that this isn’t a hint that there’s only one person who needs to be satisfied that they’ve got at least 1/nth of the cake.
Now, I’m stuck. I don’t see how you solve it as written without some sort of deceptive cake-magnifying plates. All of the n people cannot be both satisfied that they have at least 1/nth of the cake, and also be correct that they’ve got at least 1/nth of the cake if even one portion is the tiniest shade greater than 1/n.
