h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

There's another way I learned to do this, rather different from the methods outlined in this entry. It works for any number of people, but it's not necessarily efficient, as far as time goes....

Suppose you have five people. Person #1 cuts the cake into 5 pieces, which are denoted piece A through piece E. The idea is that Person #1, doing the cutting, will be happy with any of the five pieces.

Each of the other 4 people writes down on a scrap of paper their name, as well as a list of pieces that they'd be happy with. Each person could write only one piece down, if there's only one that would please them, or they can write two, or three, or four, or as many as all five, if they're easy-going about it. They write down any and all slices that could make them happy, relinquishing all claim to slices they didn't write down.

Now Person #1 collects the slips of paper and looks at them. If they find that each person can be given a piece of their choosing, then the pieces are distributed and the eating begins. If, on the other hand, it's not possible to please all 4 non-cutting participants, then we go to phase II.

At this point, we have two kinds of people: happy people and choosy people. The happy people are those who can be given cake that the choosy ones didn't want anyway. Choosy people are those who only want pieces that other choosy people also want. There may be more than one way to separate the happy from the choosy - we go for the way that maximizes the number of the happy.

If everyone is happy, then we all eat cake.

If there are only two choosy people, then the remaining pieces of cake are combined onto one plate, and the two remaining people proceed with "you cut, I choose".

If there are more than two choosy people, then the whole process we've described starts again, with a new Person #1 being named (the old person #1 is always among the happy ones), new slips of paper, etc.

This process is bound to end eventually, because at least one person is eliminated after each round of division and voting. Here are two examples, one quick, and one painfully slow:



Person #1 divides
Person #2 chooses A
Person #3 chooses A
Person #4 chooses A or B
Person #5 chooses A, B, C or D

Now, who is happy, and who is choosy? Notice that Persons #4, #5 and #1 can all be pleased without encroaching on anything that Persons #2 or #3 wanted, whereas #2 and #3 cannot be pleased without upsetting the other. Thus we have three happy people, and two choosy ones.

Let the happy people please themselves; in this case there is more than one way to do this. Giving B to #4, C to #5, and D to #1 does the trick. That leaves pieces A and E in contention between Persons #2 and #3. Those two pieces are placed together on a plate, and Person #2 adjusts them so that she is happy with either. Person #3 then chooses one of the two adjusted pieces, leaving the other for Person #2. Now, everyone is happy.



Person 1 divides: A, B, C, D, E
Person 2 chooses A, B or C
Person 3 chooses A, B or C
Person 4 chooses A, B or C
Person 5 chooses A, B or C

Now none of Persons #2-#5 can be given cake and still leave enough to please the remaining ones. Thus, Person #1, the only one happy at this stage, takes a piece, say piece E, which nobody else wanted, and bows out. Next....

Person 2 re-divides: A', B', C', D'
Person 3 chooses A'
Person 4 chooses A'
Person 5 chooses A'

Person #2 takes piece D' for their own, enjoying their status as the second happy person, without making anyone else jealous. Next...

Person 3 divides: A'', B'', C''
Person 4 chooses A''
Person 5 chooses A''

Person #3 takes piece C'', and allows the final two people to re-adjust A'' and B'' one last time, and work it out between the two of them.



I think I read this in a book somewhere. Having typed it out now, it seems even more complicated than I remember it, leaving me with an increased respect for the methods outlined in the article. Having typed it out though, I'm going to go ahead and post it, so that these 30 minutes weren't a complete loss.

cheers,
GTBacchus

Thank you!

I think this is an improvement on the "Peer Review" method described, as there's less trimming.

It's not an Envy-free method, though, as there are rounds of cake allocation, and an early recipient may be jealous of a larger portion subsequently appearing in a later round.

Icy

Yeah, I wondered about that. I guess someone satisfied in an earlier round gets a piece that they think is >= 1/5 of the cake, but they may see a piece arise in a later division that they think is EVEN larger, and which they would have chosen exclusively had they seen it earlier... Yeah, I see that. Tricky stuff, innit?

There's also the matter of proving that there will always be at least one happy person, after a round of choosing. That's a claim in elementary set theory that I'll have to chew on for a bit.

You start with two sets, A and B, equal in size. (We could assume they're finite, too, but I don't know if that's necessary.) Then we have a mapping, f:A --> P(B), assigning to each member of A a non-empty subset of B, and we know that, for at least one a in A, f(a) = B. We want to claim that we can always find a non-empty subset A' < A, such that there is a subset B' < B and a bijection g:A' --> B' satisfying

|A'| = |B'|
g(a) is in f(a) for all a in A'
For any a in (A - A'), we have f(a) < (B - B')

I think that captures what's needed. An algorithm for determining a maximal A' would be ideal. Hmmm.....

GTB