Getting your fair share
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 2
 Joined: Fri Aug 24, 2007 1:52 am UTC
Getting your fair share
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?
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?
Re: Getting your fair share
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:
If you want to avoid the crumbs, then afaik you need to introduce a new mechanism:
Spoiler:
If you want to avoid the crumbs, then afaik you need to introduce a new mechanism:
Spoiler:
Re: Getting your fair share
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.......
This seems to work, but lets see if it stands up to the test .
Spoiler:
This seems to work, but lets see if it stands up to the test .
Re: Getting your fair share
Spoiler:
We like to spoilerise our answers here. jr

 Posts: 134
 Joined: Sat Jul 28, 2007 11:33 pm UTC
 Location: Seattle, WA
Re: Getting your fair share
The problem lies in that addresses the real world there are no rulers, no protractors, no CNC cakecutting 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)
If collusion is noted between the caller and slicer, their throats are cut, and their bodies added to the available foodstuffs. (my addition
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:
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.
Re: Getting your fair share
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?
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?
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Getting your fair share
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:
 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:
Re: Getting your fair share
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:
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Getting your fair share
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.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Getting your fair share
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
"With math, all things are possible." —Rebecca Watson
Re: Getting your fair share
What if we also add the condition that no person should wind up thinking that someone else's share is larger than their own? 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?
Spoiler:
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Getting your fair share
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. 6571).
I thought this was called the cakecutting theorem, but maybe not. Anyway, I don't know if this means with a limited (or even finite) number of cuts.
Re: Getting your fair share
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. 6571).
I thought this was called the cakecutting 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 "envyfree" 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.
Re: Getting your fair share
notallama wrote:Spoiler:
I think what you mean is
Spoiler:
But that doesn't guarantee or incentivize an equitable outcome:
Spoiler:
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
Re: Getting your fair share
Spoiler:
Please, we have a spoiler policy in effect here in this part of the forums. Spoilerise your answers. Please.  jr
Re: Getting your fair share
Military wrote:Spoiler:
Isn't this just the same as mine  just worded differently
Re: Getting your fair share
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:
Why put off till today what you could just as easily get done tomorrow?
I can mathematically prove that 1 equals 0!.
Parts ax in my plan weren't that important anyways.
I can mathematically prove that 1 equals 0!.
Parts ax in my plan weren't that important anyways.
Re: Getting your fair share
Spoiler:
ave_matthew wrote:in a perfect system a gallon of body fat is worth one third of the US GDP
Re: Getting your fair share
zealo wrote:Spoiler:
That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:
Spoiler:
Felstaff wrote:Serves you goddamned right. I hope you're happy, Cake Ruiner
Re: Getting your fair share
Token wrote:After a bit more searching, I found an algorithm that uses a finite number of cuts to create an "envyfree" 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/feabrams.pdf for free.
Some of us exist to find out what can and can't be done.
Others exist to hold the beer.
Re: Getting your fair share
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
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Getting your fair share
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.
 Chrismclegless
 Posts: 240
 Joined: Wed Dec 05, 2007 8:25 pm UTC
 Location: Sigma 957
 Contact:
Re: Getting your fair share
zealo wrote:Spoiler:
Silas wrote: That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:Spoiler:
Could that not be solved by swapping B and A in 2.1, such that:
Spoiler:
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.
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.
Re: Getting your fair share
Silas wrote: That system can be gamed by B and C, if they're willing to flip a coin for the extra pie:Spoiler:
Could that not be solved by swapping B and A in 2.1, such that:Spoiler:
That solves the problem of B and C conspiring, but enables A to form an alliance with C:
Spoiler:
Felstaff wrote:Serves you goddamned right. I hope you're happy, Cake Ruiner
Re: Getting your fair share
katkov wrote:Spoiler:
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.
Re: Getting your fair share
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:
Re: Getting your fair share
There is some information on this problem in the relevant Wikipedia article. It mentions that
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."Wikipedia wrote:The first cake cutting procedure that produced an envyfree 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.
This is a placeholder until I think of something more creative to put here.
Re: Getting your fair share
ikkleste wrote:Spoiler:
Spoiler:
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Getting your fair share
AvalonXQ wrote:ikkleste wrote:Spoiler:Spoiler:
Spoiler:
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 4
 Joined: Wed Apr 16, 2008 9:47 pm UTC
Re: Getting your fair share
I am fairly certain that no one has posted the BEST solution yet. Order doesn't matter. Only n1 slices. Everyone is happy.
The great part about this method is that it works with an infinite number of people. After the first cut, continue the knifesweeping 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.
Spoiler:
The great part about this method is that it works with an infinite number of people. After the first cut, continue the knifesweeping 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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Getting your fair share
chickenwire wrote:I am fairly certain that no one has posted the BEST solution yet. Order doesn't matter. Only n1 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)))

 Posts: 4
 Joined: Wed Apr 16, 2008 9:47 pm UTC
Re: Getting your fair share
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.
Re: Getting your fair share
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.
If you can construct a scenario where this method fails, either by looping endlessly or shortchanging someone, please present it.
Spoiler:
If you can construct a scenario where this method fails, either by looping endlessly or shortchanging someone, please present it.
Re: Getting your fair share
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:
If you can construct a scenario where this method fails, either by looping endlessly or shortchanging someone, please present it.
I think I have a counter example,
Spoiler:
"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes."  Cronos
Re: Getting your fair share
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:
If you can construct a scenario where this method fails, either by looping endlessly or shortchanging someone, please present it.
I think I have a counter example,Spoiler:
Spoiler:
Who is online
Users browsing this forum: No registered users and 6 guests