Getting your fair share

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

pheonix1123
Posts: 2
Joined: Fri Aug 24, 2007 1:52 am UTC

Getting your fair share

Postby pheonix1123 » Tue Jan 29, 2008 8:04 pm UTC

Most people are familiar with the idea that, if there are 2 people splitting something, one of the two divides it in two, and the other person gets first choice. This encourages the first person to split the (whatever) evenly, so the shares should be as fair as they can make them.

Is there something similar one can do splitting a (whatever- lets say a pizza) into 3 such that:

a) the cutter(s) are encouraged to divide the pizza as evenly as possible
b) there are no major arguments over who gets the first choice, second choice, third choice.

Obviously, one could still do that person A cuts, and the other two fight for who gets first choice, but this solution doesn't seem very interesting to me.

Any suggestions?

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Getting your fair share

Postby ThomasS » Tue Jan 29, 2008 8:43 pm UTC

I've seen a few solutions to this before. The solution that I know which is probably the closest to the classic two person splitting is as follows, but it tends to produce crumbs:
Spoiler:
Person A claims a piece for himself. If everybody else thinks it is a fair share, he takes it away. If person B thinks it is too large, then person B removes a portion, and claims the remainder. Everybody gets a chance to object again, until somebody has a piece of cake that everybody thinks is sufficiently small.

Then the remaining people divide the remaining cake in the same manner.


If you want to avoid the crumbs, then afaik you need to introduce a new mechanism:
Spoiler:
Assume a long cake. A cutter slowly moves the knife along the length of the cake until somebody says stop, at that point a piece of cake is cut wherever the knife is. The person who said stop first gets that piece.

User avatar
Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: Getting your fair share

Postby Moonbeam » Tue Jan 29, 2008 8:47 pm UTC

Assuming that all 3 are out to try and maximise their share of the cake and to minimise their opponents' shares - one idea that works at first glance is to.......
Spoiler:
..... let A make the first complete cut. B then makes another cut (cutting either of the 2 pieces that A has just made) making 3 pieces. C now chooses first, then B chooses one of the remaining 2 pieces and A is left with the remaining piece.

It is in A's interest to cut the cake into 1/3 and 2/3 - if not, then the following happens:

1. If he cuts one of the pieces less than 1/3 (for example A cuts 80/20), then when B comes to cut, he knows whatever pieces are left after his cut, C will take the largest and B will take the next largest, leaving the smallest piece for A (which at best will be 20% of the cake in this example).
2. If both pieces are cut larger than 1/3 (for example A cuts the cake 50/50), then B now cuts one of the sections removing as small a piece as poss (say 1%). C now takes 50% of the cake, B takes 49% and A has only 1%.

When A cuts the cake 1/3 / 2/3, then when the cut comes to B, if B wants his maximum share whilst minimising his opponents' share, then he has to cut the 2/3 piece exactly in half. If he cuts the other piece, C will take the 2/3 piece leaving B to take the larger of the 2 remaining pieces. If B cuts the 2/3 piece but doesn't cut it exactly in half (say he cuts this piece in the ratio 1/4 / 3/4 - so the cake now consists of pieces 1/3, 1/6 and 1/2), C ends up with the largest piece (1/2 in this example), B ends up with the second largest (1/3 in this example) and A ends up with the smallest piece (1/6 in this example).


This seems to work, but lets see if it stands up to the test :shock: .

notallama
Posts: 236
Joined: Fri Jun 01, 2007 4:28 pm UTC

Re: Getting your fair share

Postby notallama » Tue Jan 29, 2008 9:08 pm UTC

Spoiler:
there shouldn't be any arguments if one person splits, then everyone else takes a peice.
the person who splits will have to make them all equal, since they get the smallest part.
the other people shouldn't care what order they pick in, since the person who splits will have to make all the parts equal.


We like to spoilerise our answers here. -jr

xkcd_n00bz
Posts: 134
Joined: Sat Jul 28, 2007 11:33 pm UTC
Location: Seattle, WA

Re: Getting your fair share

Postby xkcd_n00bz » Tue Jan 29, 2008 9:25 pm UTC

The problem lies in that addresses the real world- there are no rulers, no protractors, no CNC cake-cutting machines to insure that each slice is precisely equal. One piece is going to be bigger, have more frosting, or otherwise be more desirable.

That's why the 2 person solution is so elegant. The first person has control of slice sizes, second person allocates those slices.

We could always use the MotBMfAoLR: (Mutiny on the Bounty Method for Allocation of Limited Resources)
Spoiler:
One person slicess off a portion from the whole, where each portion is as close to 1/# of intended number of recipients as they can make it. After the slice is made, the "slicer" hollers out "who shall receive this portion?". Another predetermined person, the "caller" who cannot see the size of the slice nor how much is remaining from the foodstuff, calls out the name of one of the remaining people (including himself and the slicer) who have yet to receive their portion. Continue until everyone has a portion.

If collusion is noted between the caller and slicer, their throats are cut, and their bodies added to the available foodstuffs. (my addition ;)
I am +20 dB hot.

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Getting your fair share

Postby ThomasS » Tue Jan 29, 2008 11:07 pm UTC

To add a little to the problem, consider what happens when different people value different portions of the cake differently. Suppose in the 2 person case that one person 1 sees piece A as being 60% of the cake, and piece B as being 40%, while person 2 sees piece B as being 60% and piece A as being 40%. Then with the obvious assignments, the total cake being believed in is 120%, which is a good thing.

In the one person splits the other chooses method, the total cake believed in will be at least 100% and can certainly be larger. Do these other methods have this property?

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Getting your fair share

Postby Cosmologicon » Tue Jan 29, 2008 11:15 pm UTC

In my opinion, an ideal solution:
  • makes it impossible for any one person to get screwed, either by collusion of the other players, or failure of the other players to be perfectly logical. (A person getting screwed by their own failure to be logical is okay.) Moonbeam's, notallama's, and xkcd_n00bz's solutions do not have this property.
  • allows different people to have different utility functions (eg one person likes frosting a lot). To answer the question in the previous post, Moonbeam's, notallama's, and xkcd_n00bz's solutions do not have this property.
  • requires as few cuts as possible. ThomasS's first solution doesn't do this.
  • doesn't require people to evaluate the utility of theoretical (as yet uncut) pieces, as in ThomasS's second solution.

But of course, different people have different criteria for what makes a solution ideal. So I'm not saying that my solutions is objectively better, but I wanted to justify adding it to the mix:
Spoiler:
It's easy to do with four cuts. Person A divides it into three equal pieces (or more precisely, three pieces, any one of which she'd be happy with). B and C then identify all the pieces they'd be happy with. They must each identify at least one. If they identify two different ones, you're golden. If they both identify just one and it's the same one, A takes one of the two they didn't identify, and they divide up the rest of the cake using the regular two-person algorithm.

notallama
Posts: 236
Joined: Fri Jun 01, 2007 4:28 pm UTC

Re: Getting your fair share

Postby notallama » Tue Jan 29, 2008 11:31 pm UTC

Spoiler:
person 1 cuts
person 2 picks person 1's peice
...
person n picks person n-1's peice

this way, one person has control of the slices, and each other person gets to improve their own slice by removing the least desirable one from the pool.

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Getting your fair share

Postby ThomasS » Wed Jan 30, 2008 1:23 am UTC

Cosmologicon wrote:In my opinion, an ideal solution:
But of course, different people have different criteria for what makes a solution ideal. So I'm not saying that my solutions is objectively better, but I wanted to justify adding it to the mix:

Spoiler:
My first solution also uses a maximum of 4 cuts in the 3 person case.
Edit: oops.. I guess you could end up with 5 cuts my way. nevermind.

Well, technically as phrased somebody could increase the number by objecting to a piece that he already trimmed once, but you could add a rule against that.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Getting your fair share

Postby Cosmologicon » Wed Jan 30, 2008 4:04 am UTC

Yep, you're right, my solution is no better than the first one you posted (modified). When you said it produced crumbs, I misinterpreted that as lots and lots of tiny pieces, which is a product of some solutions I've seen before.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Getting your fair share

Postby skeptical scientist » Thu Jan 31, 2008 7:14 am UTC

I have no algorithm to add, since all of the good ones have already been mentioned. I just wanted to point out that this problem is discussed in great detail (with humorous examples) in Neil Stephenson's excellent book Cryptonomicon which all xkcdians should already have read. (If you haven't, immediately visit the nearest library/bookstore. I promise you won't regret it.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

hnooch
Posts: 128
Joined: Mon Nov 26, 2007 6:55 pm UTC

Re: Getting your fair share

Postby hnooch » Mon Feb 04, 2008 8:23 pm UTC

What if we also add the condition that no person should wind up thinking that someone else's share is larger than their own?
Spoiler:
For instance, using Cosmologicon's solution, A might wind up envious of B's piece if A gets stuck with a measly 33 percent and B gets 50 percent, under A's utility function.

That is, A divides a pizza into three equal pieces (by A's evaluation).

B and C both pick piece 1, so A takes piece 2 and B and C agree to divide pieces 1 and 3. But now, say C cuts the pizza's according to C's evaluation, which doesn't necessarily agree with A's evaluation. Now, one of the two of them will end up with a piece worth more than a third of the whole by A's evaluation, and so now A is jealous.
Is there a strategy whereby everyone thinks that they have an equal share, and everyone thinks their share is at least as good as everyone else's?

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Getting your fair share

Postby Cosmologicon » Mon Feb 04, 2008 9:27 pm UTC

hnooch wrote:Is there a strategy whereby everyone thinks that they have an equal share, and everyone thinks their share is at least as good as everyone else's?

It's mathematically possible, according to MathWorld:
It is always possible to "fairly" divide a cake among n people using only vertical cuts. Furthermore, it is possible to cut and divide a cake such that each person believes that everyone has received 1/n of the cake according to his own measure (Steinhaus 1999, pp. 65-71).

I thought this was called the cake-cutting theorem, but maybe not. Anyway, I don't know if this means with a limited (or even finite) number of cuts.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Getting your fair share

Postby Token » Tue Feb 05, 2008 1:00 am UTC

Cosmologicon wrote:
hnooch wrote:Is there a strategy whereby everyone thinks that they have an equal share, and everyone thinks their share is at least as good as everyone else's?

It's mathematically possible, according to MathWorld:
It is always possible to "fairly" divide a cake among n people using only vertical cuts. Furthermore, it is possible to cut and divide a cake such that each person believes that everyone has received 1/n of the cake according to his own measure (Steinhaus 1999, pp. 65-71).

I thought this was called the cake-cutting theorem, but maybe not. Anyway, I don't know if this means with a limited (or even finite) number of cuts.

Well, I've done some research into the problem. Thinking that Mathworld might actually be accurate, I located a copy of the Steinhaus book in my college library. While it mentions three possible solutions for ensuring that every person gets at least 1/n according to his measure, it makes no mention of any solution in which everyone gets a piece which is valued at 1/n by everybody's measure. An assertion of this (without proof) in fact appears in a paper of Steinhaus's from the 17th edition of the Econometrica journal, in 1949 (written in French, no less).

I eventually managed to track down a paper which proves the existence of such a solution. If you have access to JSTOR, you can read it here.

After a bit more searching, I found an algorithm that uses a finite number of cuts to create an "envy-free" solution for an arbitrary number of people cutting the cake. Again, JSTOR has it here. This isn't a 1/n solution, however - it merely ensures that every player gets at least 1/n, and no player believes any other player has a larger piece.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Silas
Posts: 1091
Joined: Sat Feb 02, 2008 9:08 pm UTC

Re: Getting your fair share

Postby Silas » Fri Feb 08, 2008 6:02 am UTC

notallama wrote:
Spoiler:
person 1 cuts
person 2 picks person 1's peice
...
person n picks person n-1's peice

this way, one person has control of the slices, and each other person gets to improve their own slice by removing the least desirable one from the pool.


I think what you mean is
Spoiler:
A divides the pie in two pieces; B chooses a piece; C pick's from among the existing pieces and splits it with the current owner (we already know of an equitable method), and so on until everyone has a piece.

But that doesn't guarantee or incentivize an equitable outcome:
Spoiler:
With N=3, A can divide the pie directly in half. B's choice is irrelevant; C will receive one fourth of the pie. A will receive an expected three eighths, more than the equitable one third.


Also, I'd like to point out that any method that converges to an equitable outcome as the process is dragged on will in fact generate an outcome that uses the minimum number of cuts, since rational cutters won't waste time jockeying for a bigger piece when they can see it won't avail them. (There are obviously division methods that will break this rule, but I think it's equally obvious that they're dumb: a method that cannot yield the optimal outcome is plainly deficient.)
Felstaff wrote:Serves you goddamned right. I hope you're happy, Cake Ruiner

User avatar
Military
Posts: 15
Joined: Tue Feb 05, 2008 3:30 am UTC

Re: Getting your fair share

Postby Military » Sat Feb 09, 2008 9:14 am UTC

Spoiler:
Person A cuts one slice, person B divides the remaining, person C chooses the largest slice, and person B gets the largest the remaining slice. If A cuts less then 1/3 then A gets less then 1/3. if A cuts larger then 1/3 he gets less then 1/3. if A cuts 1/3 then person B would at least 1/3 and would have to give C a slice larger then 1/3 in order for person A to get less then 1/3.

Should we assume emotional ties, collaboration? Is there any other reason to give C the larger slice?


Please, we have a spoiler policy in effect here in this part of the forums. Spoilerise your answers. Please. - jr

User avatar
Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: Getting your fair share

Postby Moonbeam » Sat Feb 09, 2008 12:45 pm UTC

Military wrote:
Spoiler:
Person A cuts one slice, person B divides the remaining, person C chooses the largest slice, and person B gets the largest the remaining slice. If A cuts less then 1/3 then A gets less then 1/3. if A cuts larger then 1/3 he gets less then 1/3. if A cuts 1/3 then person B would at least 1/3 and would have to give C a slice larger then 1/3 in order for person A to get less then 1/3.

Should we assume emotional ties, collaboration? Is there any other reason to give C the larger slice?


Isn't this just the same as mine - just worded differently :?:

User avatar
Ansain
Posts: 207
Joined: Sun Apr 15, 2007 1:15 am UTC
Location: Here

Re: Getting your fair share

Postby Ansain » Sat Feb 09, 2008 10:08 pm UTC

This gets as few cuts as possible, It also ensures that if one person cuts a piece larger or smaller than 1/3 than that person will get less than his/her fair share.

Spoiler:
The idea of my solution is that the two people cutting want to cut exactly into 3rds in order to get the most.
Person A starts by cutting out a slice of the pizza.
Person B has three choices, take the first slice, give person A the first slice, or cut the remaining pizza.
If person B takes the slice person C cuts the last bit in half and person A chooses which half he wants.
If person B gives person A the slice then person C cuts the last bit in half and person B chooses which half he wants.
If person B chooses to cut the remaining piece then person C chooses first, person A chooses second and person B gets the last piece.
Why put off till today what you could just as easily get done tomorrow?

I can mathematically prove that 1 equals 0!.

Parts a-x in my plan weren't that important anyways.

User avatar
Zak
Posts: 2230
Joined: Sun Dec 16, 2007 7:25 am UTC
Location: In the making.

Re: Getting your fair share

Postby Zak » Sun Feb 10, 2008 12:04 am UTC

My solution involves zero cuts:

Spoiler:
Deathmatch. Winner takes all.
*waggles eyebrows*

User avatar
duckshirt
Posts: 567
Joined: Thu Feb 15, 2007 1:41 am UTC
Location: Pacific Northwest

Re: Getting your fair share

Postby duckshirt » Mon Feb 11, 2008 2:53 am UTC

Spoiler:
I would probably person A cuts it into six pieces, person B chooses a piece, person C chooses two pieces, and person B chooses another piece.

But if you don't want to cut into two pieces, you could make person A cut off about a third, and person B can choose whether to take it or leave it. If he takes it, person A and C do the two-person thing. If he leaves it, person A gets the piece and B and C do the two-person thing. You just have to hope that two of the three don't gang up on the other one.
lol everything matters
-Ed

zealo
Posts: 321
Joined: Sun Dec 17, 2006 11:36 am UTC
Location: perth, australia
Contact:

Re: Getting your fair share

Postby zealo » Mon Feb 11, 2008 3:29 pm UTC

Spoiler:
naming people A/B/C

1) A cuts 1/3 from the cake, B and C may claim it, otherwise A gets it.

2) B cuts remaining 2/3 in half, C chooses from that.

if piece from 1) is claimed, the one who had the chance to claim but didn't gets to cut, and A chooses in 2)

if piece from 1) is claimed by both B and C, then it is obviously a terrible cut, and 2.1) shall result

2.1) B cuts remaining 2/3 with the aim of matching piece from 1), C shall choose piece from the 3, followed by B, followed by A

all that remains is deciding who gets what letter, personally i would recommend volunteering for A, then pointing out that since you have the knife, you decide who gets how much cake
ave_matthew wrote:in a perfect system a gallon of body fat is worth one third of the US GDP

Silas
Posts: 1091
Joined: Sat Feb 02, 2008 9:08 pm UTC

Re: Getting your fair share

Postby Silas » Mon Feb 11, 2008 9:55 pm UTC

zealo wrote:
Spoiler:
It's in the post above, people. Don't be so lazy.

That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:
Spoiler:
No matter what size piece A cuts, B and C will both claim it, then screw A over by cutting him a miniscule piece, since he picks last in that case. B and C can divide the spoils among themselves.
Felstaff wrote:Serves you goddamned right. I hope you're happy, Cake Ruiner

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Getting your fair share

Postby btilly » Mon Feb 11, 2008 10:10 pm UTC

Token wrote:After a bit more searching, I found an algorithm that uses a finite number of cuts to create an "envy-free" solution for an arbitrary number of people cutting the cake. Again, JSTOR has it here. This isn't a 1/n solution, however - it merely ensures that every player gets at least 1/n, and no player believes any other player has a larger piece.

A description of the algorithm may be found at http://www.ams.org/notices/200611/fea-brams.pdf for free.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

zealo
Posts: 321
Joined: Sun Dec 17, 2006 11:36 am UTC
Location: perth, australia
Contact:

Re: Getting your fair share

Postby zealo » Fri Feb 15, 2008 4:54 pm UTC

silas: the is no possible system where A won't be screwed over if B + C work together with that goal. i was assuming no 'alliances' between players and the that the secondary aim (after getting as much cake as possible) is to limit the amount you 'lose' by.
ave_matthew wrote:in a perfect system a gallon of body fat is worth one third of the US GDP

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Getting your fair share

Postby Cosmologicon » Fri Feb 15, 2008 5:04 pm UTC

zealo wrote:silas: the is no possible system where A won't be screwed over if B + C work together with that goal. i was assuming no 'alliances' between players

Not so, there are definitely systems where alliances don't screw over the third player. Including some posted in this thread. Including the very first one posted in this thread.

User avatar
Chrismclegless
Posts: 240
Joined: Wed Dec 05, 2007 8:25 pm UTC
Location: Sigma 957
Contact:

Re: Getting your fair share

Postby Chrismclegless » Sun Feb 24, 2008 3:04 pm UTC

zealo wrote:
Spoiler:
naming people A/B/C

1) A cuts 1/3 from the cake, B and C may claim it, otherwise A gets it.

2) B cuts remaining 2/3 in half, C chooses from that.

if piece from 1) is claimed, the one who had the chance to claim but didn't gets to cut, and A chooses in 2)

if piece from 1) is claimed by both B and C, then it is obviously a terrible cut, and 2.1) shall result

2.1) B cuts remaining 2/3 with the aim of matching piece from 1), C shall choose piece from the 3, followed by B, followed by A

all that remains is deciding who gets what letter, personally i would recommend volunteering for A, then pointing out that since you have the knife, you decide who gets how much cake


Silas wrote: That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:
Spoiler:
No matter what size piece A cuts, B and C will both claim it, then screw A over by cutting him a miniscule piece, since he picks last in that case. B and C can divide the spoils among themselves.

Could that not be solved by swapping B and A in 2.1, such that:
Spoiler:
B cuts remaining 2/3 with the aim of matching piece from 1), C shall choose piece from the 3, followed by A, followed by B
Londo: Maybe it was something I said?
G'Kar: Maybe it is everything you say.

How tasty is YOUR brain?

GENERATION 21: The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.

Silas
Posts: 1091
Joined: Sat Feb 02, 2008 9:08 pm UTC

Re: Getting your fair share

Postby Silas » Sun Feb 24, 2008 7:06 pm UTC

Silas wrote: That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:
Spoiler:
No matter what size piece A cuts, B and C will both claim it, then screw A over by cutting him a miniscule piece, since he picks last in that case. B and C can divide the spoils among themselves.

Could that not be solved by swapping B and A in 2.1, such that:
Spoiler:
B cuts remaining 2/3 with the aim of matching piece from 1), C shall choose piece from the 3, followed by A, followed by B


That solves the problem of B and C conspiring, but enables A to form an alliance with C:
Spoiler:
A cuts a miniscule piece from the pie and claims the big part- now B has to cut the tiny piece; C claims the big piece, A claims the best of the two remaining pieces, and C is left with a scrap. A and B then divide their mutual spoils.

You can reduce this effect by scrapping the part about claiming a piece; with N people: in order, P1-Pn-1 all divide one of the existing pieces into two, then Pn chooses, then everyone else, starting with P1.
Then (I think) the best alliance (when N=3) has A cutting the original pie in half- B cuts (and gets) one quarter, A+C gets 3/4 > 2/3
Felstaff wrote:Serves you goddamned right. I hope you're happy, Cake Ruiner

User avatar
katkov
Posts: 31
Joined: Fri Sep 28, 2007 9:11 pm UTC

Re: Getting your fair share

Postby katkov » Wed Mar 05, 2008 7:36 pm UTC

Spoiler:
Person A cuts the pie into thirds, Player B and C then flip a coin, who ever calls it correctly gets to choose a peice then the other person and finally A.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Getting your fair share

Postby btilly » Wed Mar 05, 2008 7:40 pm UTC

katkov wrote:
Spoiler:
Person A cuts the pie into thirds, Player B and C then flip a coin, who ever calls it correctly gets to choose a peice then the other person and finally A.

They may agree to this procedure up front, but person B may wind up believing that C got the bigger piece.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Getting your fair share

Postby Random832 » Tue Apr 08, 2008 9:12 pm UTC

hnooch wrote:Is there a strategy whereby everyone thinks that they have an equal share, and everyone thinks their share is at least as good as everyone else's?


not an answer really, but spoilering just in case
Spoiler:
I don't think a general solution that does this is possible in principle, because utility functions can be arbitrarily... well, arbitrary. (note, the theorem mentioned above is that everyone's slice is at least 1/n by his own measure; it does not guarantee that person B does not have a portion greater than person A by person A's measure.)

It'd be nice to _maximise_ the amount each person has by their own measure, but I don't think this is possible either.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Getting your fair share

Postby Robin S » Tue Apr 08, 2008 9:19 pm UTC

There is some information on this problem in the relevant Wikipedia article. It mentions that
Wikipedia wrote:The first cake cutting procedure that produced an envy-free division of cake for any natural number of persons was first published by Steven Brams and Alan Taylor in 1995. But because the procedure is somewhat impractical when the number of persons is large, fair division continues to be an important problem in mathematics and the social sciences.
In other words, the answer to hnooch's question is "yes, but it's not yet very convenient when large numbers of people are involved."
This is a placeholder until I think of something more creative to put here.

ikkleste
Posts: 16
Joined: Tue Apr 22, 2008 12:37 pm UTC

Re: Getting your fair share

Postby ikkleste » Fri Apr 25, 2008 1:47 pm UTC

Spoiler:
A cuts one slice... Lets call it 1
B divides the remainder into two slices 2 and 3.
C picks from 1, 2 and 3
If C selects 2 or 3 B gets the other (2 or 3), A gets 1.
If C selects 1, A picks 2 or 3, B gets the remainder.

I think this works well. A is incentivised to make the first cut a fair one if not he'll end up with it, B is incentivised to make the second cut fair if not he'll end up with the smaller part of the two.

I think theres elimination of colusion as well. If A cuts big to favour C, then A gets the smallest peice of all.
If B cuts unevenly then he'll be the only one that suffers. If C picks the largest, A will get his first fair slice. If c picks the fair slice A gets to pick the largest.
A and B can't conspire as C gets first pick.

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Getting your fair share

Postby AvalonXQ » Fri Apr 25, 2008 5:43 pm UTC

ikkleste wrote:
Spoiler:
A cuts one slice... Lets call it 1
B divides the remainder into two slices 2 and 3.
C picks from 1, 2 and 3
If C selects 2 or 3 B gets the other (2 or 3), A gets 1.
If C selects 1, A picks 2 or 3, B gets the remainder.

I think this works well. A is incentivised to make the first cut a fair one if not he'll end up with it, B is incentivised to make the second cut fair if not he'll end up with the smaller part of the two.

I think theres elimination of colusion as well. If A cuts big to favour C, then A gets the smallest peice of all.
If B cuts unevenly then he'll be the only one that suffers. If C picks the largest, A will get his first fair slice. If c picks the fair slice A gets to pick the largest.
A and B can't conspire as C gets first pick.


Spoiler:
Doesn't work. Assume A makes 1 equal to 95% of the cake. B never has the opportunity to select 1, and so B is unfairly screwed.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Getting your fair share

Postby Xanthir » Fri Apr 25, 2008 8:34 pm UTC

AvalonXQ wrote:
ikkleste wrote:
Spoiler:
A cuts one slice... Lets call it 1
B divides the remainder into two slices 2 and 3.
C picks from 1, 2 and 3
If C selects 2 or 3 B gets the other (2 or 3), A gets 1.
If C selects 1, A picks 2 or 3, B gets the remainder.

I think this works well. A is incentivised to make the first cut a fair one if not he'll end up with it, B is incentivised to make the second cut fair if not he'll end up with the smaller part of the two.

I think theres elimination of colusion as well. If A cuts big to favour C, then A gets the smallest peice of all.
If B cuts unevenly then he'll be the only one that suffers. If C picks the largest, A will get his first fair slice. If c picks the fair slice A gets to pick the largest.
A and B can't conspire as C gets first pick.


Spoiler:
Doesn't work. Assume A makes 1 equal to 95% of the cake. B never has the opportunity to select 1, and so B is unfairly screwed.


Spoiler:
Of course, A also gets unfairly screwed, likely by an equal amount (after all, there's no reason for B *not* to split it evenly).

I'm thinking that the simple option involving a slowly moving yardstick is the best. Someone slowly passes a yardstick over the cake. Any of the three can call dibs whenever they want - they then cut it where the yardstick is and give that piece to the dibs-caller. You then do the standard "one person cuts, the other chooses" strategy for the remaining part.

This solution has the advantage that it's completely symmetric for the first piece, which is where most of them fail. There's simply no way to get an unfair piece that isn't your fault. You either called early (your fault for estimating badly) or tried to call late but got scooped (your fault for being greedy).

Plus, I believe this can be generalized to any number of players. Just use dibs-calling until you get down to 2 people, then do the standard 2-person algorithm.

(Really, the 2-person algo is just a simplification of the dibs-calling algorithm that takes advantage of the symmetry of the situation.)

You could also handle the n-player situation by using a variant of the 2-person solution. If the number of players is odd, do a dibs-calling. If the number of players is odd, split the players into two groups. One group decides collectively on how to split the cake in half, while the other group collectively decides which piece to select. Repeat and recurse as necessary. This minimizes the number of dibs that have to be called and minimizes the average difficult of estimating each cut.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

chickenwire
Posts: 4
Joined: Wed Apr 16, 2008 9:47 pm UTC

Re: Getting your fair share

Postby chickenwire » Mon Apr 28, 2008 1:43 am UTC

I am fairly certain that no one has posted the BEST solution yet. Order doesn't matter. Only n-1 slices. Everyone is happy.

Spoiler:
Have any member of the crew slowly move the knife from the left edge of the pizza/cake/loafofbread/livingroom to the right. When any of the splitters is satisfied that he/she would be content that the portion to the left of the knife is at least 1/3 of the total, he/she calls out, the item is sliced where the knife lays, and the piece is handed to him/her. At this point, the other two parties are satisfied that no more than 1/3 of the value has been handed out (or else they would have called out sooner). Then you have two people with one piece to split, which is the simple I-cut-you-choose method.


The great part about this method is that it works with an infinite number of people. After the first cut, continue the knife-sweeping until there is only one piece left, and two people fighting over it.

Ah, and I now see that ThomasS posted this solution at the top of the thread. I think it is worthy enough to post again.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Getting your fair share

Postby Xanthir » Wed Apr 30, 2008 6:36 pm UTC

chickenwire wrote:I am fairly certain that no one has posted the BEST solution yet. Order doesn't matter. Only n-1 slices. Everyone is happy.

Ah, and I now see that ThomasS posted this solution at the top of the thread. I think it is worthy enough to post again.

In addition, I posted that exact solution in the very last post before yours. I also posted an optimization that makes it easier to do with large groups of people (which is what made my post relevant, given that it had already been mentioned before).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

chickenwire
Posts: 4
Joined: Wed Apr 16, 2008 9:47 pm UTC

Re: Getting your fair share

Postby chickenwire » Thu May 01, 2008 4:30 am UTC

Xanthir wrote:In addition, I posted that exact solution in the very last post before yours. I also posted an optimization that makes it easier to do with large groups of people (which is what made my post relevant, given that it had already been mentioned before).


Yikes. Yes, you did. I am now quite ashamed. I reread them in ascending order, and must have accidentally skipped yours.

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Getting your fair share

Postby AvalonXQ » Fri May 02, 2008 12:01 am UTC

The following is a solution which works for an arbitrary number of people and doesn't assume a long cake or incremental cutting ability. This solution assures that each person has the ability to act such that he gets a fair share of cake, no matter how all of the other people choose to act.

Spoiler:
For n people.
Put the people "in order" (how you determine order is irrelevant).
The first person, designated "The Cutter", divides the cake into n slices.
Each person other than The Cutter designates as many slices as they choose, any number between 0 and n-1 of them.
Loop these two steps:
1) If any slice is designated by no one, it is given to the first person who has designated no remaining slices (The Cutter is the first of these). That person is then done.
2) If any group of x slices are designated by the exact same set of x remaining people, that set of people take those slices and distribute them, with the first person choosing first and on down the line. That set of people are then done.
... if those steps caused any people to become done, start whole the process over with the new, smaller "n" (and likely a new person as "The Cutter", who may unfortunately change the slices and produce more cake slivers. BONUS: If the new Cutter didn't designate any slices the last time, don't let him change the slice division at all).
If those steps DIDN'T cause any people to become done, then take the slice with the fewest designations and perform this division process with all the people who designated it as though those people were the whole group. Each of those people get credit for having a "fractional" piece of cake according to the number of people in the group, and are only done when their fractions have added up to a whole piece. After each step of the fractional division, check Steps 1 and 2 above before performing the next fractional division.
This will work in a finite number of cuts. For a large group of people, it can potentially cut up the slices pretty bad (but generally only if there's a LOT of disagreement over which piece is biggest).

If you can construct a scenario where this method fails, either by looping endlessly or short-changing someone, please present it.

User avatar
BoomFrog
Posts: 1070
Joined: Mon Jan 15, 2007 5:59 am UTC
Location: Seattle

Re: Getting your fair share

Postby BoomFrog » Wed May 07, 2008 9:37 am UTC

AvalonXQ wrote:The following is a solution which works for an arbitrary number of people and doesn't assume a long cake or incremental cutting ability. This solution assures that each person has the ability to act such that he gets a fair share of cake, no matter how all of the other people choose to act.

Spoiler:
For n people.
Put the people "in order" (how you determine order is irrelevant).
The first person, designated "The Cutter", divides the cake into n slices.
Each person other than The Cutter designates as many slices as they choose, any number between 0 and n-1 of them.
Loop these two steps:
1) If any slice is designated by no one, it is given to the first person who has designated no remaining slices (The Cutter is the first of these). That person is then done.
2) If any group of x slices are designated by the exact same set of x remaining people, that set of people take those slices and distribute them, with the first person choosing first and on down the line. That set of people are then done.
... if those steps caused any people to become done, start whole the process over with the new, smaller "n" (and likely a new person as "The Cutter", who may unfortunately change the slices and produce more cake slivers. BONUS: If the new Cutter didn't designate any slices the last time, don't let him change the slice division at all).
If those steps DIDN'T cause any people to become done, then take the slice with the fewest designations and perform this division process with all the people who designated it as though those people were the whole group. Each of those people get credit for having a "fractional" piece of cake according to the number of people in the group, and are only done when their fractions have added up to a whole piece. After each step of the fractional division, check Steps 1 and 2 above before performing the next fractional division.
This will work in a finite number of cuts. For a large group of people, it can potentially cut up the slices pretty bad (but generally only if there's a LOT of disagreement over which piece is biggest).

If you can construct a scenario where this method fails, either by looping endlessly or short-changing someone, please present it.


I think I have a counter example,
Spoiler:
I'm confused by the logic, but I it seems like the point is that you should designate all the best pieces unless you believe they are all equal, then you designate none (it would have been more clear to set things up with 1 to n slices designated, but whatever).

Anyway, the fractional division doesn't always work. Lets say there are five people. Two designate one piece and three designate another single piece. The two divide their slice and then the four remaining slices are used to start again. Now the remaining cake is perfectly divided into five pieces. Everyone designates none and takes a piece. Now two people got extra cake.
"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes." - Cronos

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Getting your fair share

Postby AvalonXQ » Wed May 07, 2008 1:56 pm UTC

BoomFrog wrote:
AvalonXQ wrote:The following is a solution which works for an arbitrary number of people and doesn't assume a long cake or incremental cutting ability. This solution assures that each person has the ability to act such that he gets a fair share of cake, no matter how all of the other people choose to act.

Spoiler:
For n people.
Put the people "in order" (how you determine order is irrelevant).
The first person, designated "The Cutter", divides the cake into n slices.
Each person other than The Cutter designates as many slices as they choose, any number between 0 and n-1 of them.
Loop these two steps:
1) If any slice is designated by no one, it is given to the first person who has designated no remaining slices (The Cutter is the first of these). That person is then done.
2) If any group of x slices are designated by the exact same set of x remaining people, that set of people take those slices and distribute them, with the first person choosing first and on down the line. That set of people are then done.
... if those steps caused any people to become done, start whole the process over with the new, smaller "n" (and likely a new person as "The Cutter", who may unfortunately change the slices and produce more cake slivers. BONUS: If the new Cutter didn't designate any slices the last time, don't let him change the slice division at all).
If those steps DIDN'T cause any people to become done, then take the slice with the fewest designations and perform this division process with all the people who designated it as though those people were the whole group. Each of those people get credit for having a "fractional" piece of cake according to the number of people in the group, and are only done when their fractions have added up to a whole piece. After each step of the fractional division, check Steps 1 and 2 above before performing the next fractional division.
This will work in a finite number of cuts. For a large group of people, it can potentially cut up the slices pretty bad (but generally only if there's a LOT of disagreement over which piece is biggest).

If you can construct a scenario where this method fails, either by looping endlessly or short-changing someone, please present it.


I think I have a counter example,
Spoiler:
I'm confused by the logic, but I it seems like the point is that you should designate all the best pieces unless you believe they are all equal, then you designate none (it would have been more clear to set things up with 1 to n slices designated, but whatever).

Anyway, the fractional division doesn't always work. Lets say there are five people. Two designate one piece and three designate another single piece. The two divide their slice and then the four remaining slices are used to start again. Now the remaining cake is perfectly divided into five pieces. Everyone designates none and takes a piece. Now two people got extra cake.


Spoiler:
I'm having trouble finding a scenario in which what you've described actually happens. Remember that at least one person, The Cutter, doesn't get to designate any pieces at all. And the fractional division never occurs if at least one person takes cake by either of the earlier steps.
The scenario you're describing causes the cake to be unfairly divided when at least some of the cake is undesignated. But fractional division only ever occurs when EVERY piece is designated -- otherwise, the Cutter takes an undesignated piece and the steps loop.
So, I'm pretty sure your counterexample doesn't actually happen. If you disagree and would be willing to spell it out more precisely, I'd appreciate it.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests