# Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an hour to an hour, and then just grins at me, and whispers whole day: "You will never solve me..."

Please save me from this torturer.

Here it is:

Let's say there are two people and a sandwich. They want to share the sandwich, but they don't trust each other. However, they found the way how both of them will have a lunch without feeling deceived: One of them will cut the sandwich in two halves, and another will choose which half will be his. Fair, right?

The problem is:

Is there such mechanism for three people and a sandwich?

EDIT: This was roller-coaster for me. Now, it turns out that there are at least two books devoted exclusively on this problem and its variations:

Fair Division

Cake Cutting Algorithms

I was yesterday in a coffee shop, in a small company. We ordered coffee and some chocolate cakes. As I was cutting my cake for my first bite, I felt sweat on my forehead. Would some of my buddies just interrupt me and say: Stop! You are not cutting the cake in a fair manner! My hands started shaking in fear of that. But, no, nothing happened. Fortunately.

-
Yes, see Wikipedia: Category:Fair division and in particular Selfridge–Conway –  Chris Culter Jan 14 '14 at 5:20
I can't believe this. My salvation was in Wikipedia? –  VividD Jan 14 '14 at 5:23
Since we are in mathematics, we might want to apply the Banach–Tarski paradox N-1 times to solve the problem for N people... –  PlasmaHH Jan 14 '14 at 10:57
This seems trivial. Each person rolls dice. The low score cuts the sandwhich into portions. Then each participant chooses a single portion according to highest dice order. Now since the cutter chooses last, he will obtain the smallest portion, as in the case with 2 participants, but it is clear that the number of participants do not matter. Therefore, he will maximize the size of the smallest portion. But this must mean that all portions are equal. Am I missing something here? –  Paul Jan 14 '14 at 11:01
@paul your algorithm assumes that the players agree on which pieces are bigger than each other. The problem becomes nontrivial when you remove that assumption. If A cuts the cake, then A will believe all three pieces are equal. Then B takes a piece-but if C disagrees with A and believes B's piece is bigger than the others, the solution isn't envy-free. That's the beauty of the Selfridge-Conway procedure: all three players are guaranteed to believe they got a fair slice. –  Kevin Carlson Jan 14 '14 at 22:00

Just for the record, here's the Selfridge–Conway discrete procedure mentioned in the comments. The Wikipedia article also contains some commentary on its origin and why it works.

This procedure was the first envy-free discrete procedure devised for three players. The maximal number of cuts in the procedure is five. The pieces are not always contiguous. Solutions for n players were also found later.

Suppose we have three players P1, P2 and P3. Where the procedure gives a criterion for a decision it means that criterion gives an optimum choice for the player.

Step 1. P1 divides the cake into three pieces he considers of equal size.

Step 2. Let's call A the largest piece according to P2.

Step 3. P2 cuts off a bit of A to make it the same size as the second largest. Now A is divided into:

• the trimmed piece A1
• the trimmings A2.

Leave the trimmings A2 to one side. If P2 thinks that the two largest parts are equal, then each player chooses a part in this order: P3, P2 and finally P1.

Step 4. P3 chooses a piece among A1 and the two other pieces.

Step 5. P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it.

Step 6. P1 chooses the last piece leaving just the trimmings A2 to be divided.

Now, the cake minus the trimmings A2 has been divided in an envy free manner. The trimmed piece A1 has been chosen by either P2 or P3. Let's call the player who chose it PA and the other one Player PB.

Step 7. PB cuts A2 into three equal pieces.

Step 8. PA chooses a piece of A2 - we name it A21.

Step 9. P1 chooses a piece of A2 - we name it A22.

Step 10. PB chooses the last remaining piece of A2 - we name it A23.

Wikipedia on the origins this procedure:

This procedure is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told it to many people, but Selfridge did not publish it. John Conway discovered it independently in 1993, and also never published it, but the result is attributed to them in a number of books.

-
this method is envy-free, @Chris Culter, but is it coalition-resistant? –  VividD Jan 14 '14 at 18:10
@VividD, yes it is. It's easy to see if you read the analysis in the end of the wikipedia articles. –  zespri Jan 14 '14 at 20:28
This answer is no good. It refers to cutting up a cake, whereas the question is clearly about cutting sandwiches. –  AviD Jan 14 '14 at 22:16
There is a difference between cutting a cake and cutting a pie. From Science News: Mathematicians simplify cake cutting by assuming that all slices are perpendicular to one particular side of a rectangular cake, with no crosswise cuts. Following that rule, there is only one way to split a rectangular cake into two equal-size pieces. For a pie, however, there are an infinite number of ways, because there an infinite number of lines going through the center of a circle. –  Joel Reyes Noche Jan 14 '14 at 23:37
@Mottie It handles it well. Each player divides the sandwich into equally valued pieces from their perspective. If they value meat more, pieces with meat should be smaller than pieces with less meat. If they don't care about bread at all, then they can just cut the meat up evenly, and ignore the amount of bread in each piece. The big downside is incompetence: in the two-player game, it is almost always a better idea to be the 2nd player than the 1st, because it is easier to determine which of two pieces are bigger than it is to cut something into two even pieces. –  Yakk Jan 15 '14 at 14:52

This presentation contains background and main results in resource allocation and fair division areas. "A cake" is formally defined as (0,1) interval. The author outlines and compares eight procedures for fair division of a cake. For the sake of comparison, following properties of fair division procedures are defined: proportionality, envy-freeness, equability, Paretto-efficiency. Some of the procedures require a referee, and some do not. Some produce contiguous pieces, some do not. All procedures are evaluated against the set of properties above.

Following table from the presentation summarizes features of described procedures:

Regarding avoiding envy, the authors even mention and define degree of envy-freeness for some of presented procedures.

The key conclusion of the presentation is:

The problem becomes non-trivial for more than two players, and there are many open problems relating to finding procedures with “good” properties for larger numbers of players.

-

Nobody said it has to be a discrete process. Just blend the sandwich into infinitestimally small pieces, everyone eats small pieces at the same speed until there is nothing left. Lucky person gets to lick the blades.

-
"until they ate a third of the mess." How do you decide when that happens? –  Dan Hulme Jan 14 '14 at 14:19
I believe it will naturally happen when the sandwich ends, if each person eats 1 piece at a time. –  Conrad Clark Jan 14 '14 at 15:07
@DanHulme fixed –  pwned Dec 16 '14 at 17:51

My proffesor for Game Theory ask me that,and I gave him an answer he said that is the simplest he heard(also Steaven Brhams said it's nice):

P1 divides the cake to 3. P2 notes the smallest,in his opinion,let it be A. if P3 wants A,take it.else P1 takes it,and we have only 2 witch we know how to do.

-

From You cut I choose:

An interesting solution is outlined in "Mutiny on the H.M.S. Bounty", called the Who-shall-have-this Method. Say there are $N$ people to divide between, they choose from amongst themselves two people - $A$ and $B$. $A$ stands where $B$ cannot observe him, and divides the cake. B then points to someone and that someone comes to claim his share of the cake. $B$ may at any time point to $A$ or to himself, but since he never can see which segment of cake he's giving out, and since $B$ and $A$ are both chosen by the crowd, there is virtually no opportunity for intentional collusion.

This method still won't guarantee everyone a satisfactory cut of the cake, but it gives $A$ the correct motivation, since only by dividing the cake evenly can he hope to get a large piece for himself.

-
I think I like this method the best so far, even better than the solution I proposed. –  Kevin Fegan Jan 14 '14 at 21:20
This method really has some appeal. @Nancy Hastings-Trew : I maybe don't fully understand it. Does this mean that A cuts the cake in N peaces? And that B repeatedly points to next person who in turn chooses his/her share? –  VividD Jan 15 '14 at 17:30
@VividD Yes, I believe so. A cuts all pieces the same so that if he is pointed to last, he still gets 1/n of the cake. However, this still has the same flaw as the "You Cut I Choose" method, in which A cannot plan to receive more than 1/n of the cake, while the first person chosen is guaranteed more than 1/n (because no one can cut cake that evenly). –  Timtech Jan 15 '14 at 22:08
@Timtech - "... while the first person chosen is guaranteed more than 1/n (because no one can cut cake that evenly". It's assumed that A will attempt to cut the cake as evenly as possible (of course, there will be some variation). But, the first piece A chooses to distribute will not necessarily be the biggest. A will just start at some "random" point for the first piece, so there is no guarantee that the first person chosen will get a piece that is larger than 1/n. If this was somehow guaranteed, then B would always choose himself first to be guaranteed a bigger piece. –  Kevin Fegan Jan 16 '14 at 20:08
@VividD - your interpretation is close... A first divides the cake to allow for a piece for everyone, and then selects a piece to be distributed. B selects a person to receive the selected piece, but B can't see the piece that A selected. The selected person must accept the piece that A selected. A then selects the next piece, and so on. –  Kevin Fegan Jan 16 '14 at 20:29

I think I might have an algorithm that a) Is fair b) Can be generalized for n players c) Only uses a bounded number of cuts (a different bound for each n)

odds are that I am wrong =P

The procedure for 3 players:

1. P1 divides the cake in 3 parts

2. P2 and P3 choose each a 'smallest piece', such that they dont want part of it.

2.1 If P2 and P3 agree,then they take the 2 pieces they like, and divide each amongst themselves. P3 gets the remaining

2.2 If P2 and P3 disagree, we have: P2 'likes' two pieces P3 'likes' two pieces P1 will be assumed to like the two pieces that are not liked by both P2 and P3 Now, each piece has 2 people that like it. These 2 divide the piece amongst themselves

P1 is happy (if he divided correctly): he either got 1 piece, or half of 2 pieces

P2 and P3 are happy: they each got half of the two pieces they think are bigger

The procedure for n (using the procedure for n-1)

1. P1 divides in N

2. Each P2, ..., PN chooses a piece they dislike (and therefore, n-1 they like). They get a 'stake' in each piece they like.

3. P1 gets 'stakes' in pieces such that each piece is 'divided' in n-1 stakes

4. recurse: each piece is divided amonsgt the people with stakes on them. If P1 has more then 1 stake, he can 'play as many players' in the division. As far as I can tell, that is not a problem

-
Yeah, apealing novelty is "don't like" method. I like it. :) –  VividD Jan 16 '14 at 22:45

I think I have a more practical solution than the one selected:

1. A cuts the cake in three.
2. B cuts each piece in three.
3. C cuts each piece in three.

We now have 27 pieces, each takes one piece in the same order they have cut the cake then reverse the sequence: ABC-CBA-ABC-CBA-...

No matter how A and B cut the cake, C can make sure that every piece is very close to the same size AND it is his best interest to do so. Similarly B, by cutting each piece properly in 3 equal parts, minimizes C's ability to screw up.

A has least incentive to cut fairly, but his cuts have the least influence on the final outcome. He can however set a baseline: if his cuts are fair, no screw-up can be bigger than one third of the cake.

The assumption here is that none of them is capable of making perfect cuts, but that the errors will cancel themselves out. The important issue is to make it in their best interest to attempt the fairest cuts possible.

By reverting the picking order on each turn, A & C will alternatively chose the biggest remaining piece and B will get the medium piece of each set, so even if there is a discrepancy in the portion sizes the picking order should minimize its impact.

There is also another aspect which is that the greater the number of portions of somewhat similar size, the harder it becomes for each person to keep track of the total amount of cake gotten. With 1 piece each, it's fairly easy for each one to compare portions. But if each person must chose 9 pieces, it's a lot harder to compare the total volume gotten by each.

-
A likes cake and B doesn't like cake, and A and B dislike C, so A cuts one huge and two small pieces, and B cuts each piece into one large and two tiny pieces. A goes first and takes the single huge piece, and B discards whatever crumbs he gets, but this eventually leaves C very sad and hungry. –  user21820 Jan 17 '14 at 9:37
Read again and that time do try to understand the solution. A and B cuts the cake into a large one and 2 tiny pieces. Now we have 2 big pieces and a bunch of crumbs. What you didn't understand is that C cuts EACH piece in 3 EQUAL pieces. Nothing A and B can do about it. After C, you have 6 equal pieces and a bunch of crumbs. If C cuts properly, he will get exactly 1 third of the cake. –  Sylverdrag Jan 18 '14 at 2:57
I think I responded to the wrong answer, but your method is still wrong. A likes cake and C doesn't like cake, and A and C dislike B, so A cuts equally. If B cuts equally, C cuts all equally except one which he cuts into one large and two tiny, so A goes first and takes that large piece, and B cannot get his fair share. If B does not cut equally, then C cuts equally and I am pretty certain that B also will not get his fair share if both A and C play perfectly. –  user21820 Jan 18 '14 at 4:52
You are outside the scope of the question: the original problem was sharing a cake betwen 2 people who want their fair share but don't trust the other. Expanding it to 3 people, we have 3 people who want their fair share. The failure can only occur if C does not actually wants his fair share, in which case most answers above fail completely, whereas my solution limits the failure to a single 1/9th piece. B gets less, but only if C agrees to take even less than B, which is outside the scope of the question asked. –  Sylverdrag Jan 18 '14 at 22:20
Ah you interpret the problem differently. The problem never explicitly stated that each of them wants his fair share. It only says that they don't trust each other, and implies that we are to find a procedure by which any player can obtain at least his fair share by playing correctly. But if you assume that every player wants his fair share, then it is enough to let one cut into 3 pieces and the rest choose, since the one cutting will then cut evenly. And I have indeed responded to many answers that fail, not just yours. –  user21820 Jan 23 '14 at 1:33

Here's a variation on the accepted answer.

A cuts the sandwich into 3 parts
If B thinks the top 2 pieces are equal
C chooses a piece
B chooses a piece
A gets the remaining piece
Else
B re-balances the 2 biggest pieces.
C chooses a piece
If only one of B's re-balanced pieces remain
B gets that piece
A gets the remaining piece
else
A chooses a piece
B gets the remaining piece


Summary:

• A will get one of their original "equal" pieces or more, and is thus happy.
• B will get one of the pieces they adjusted, and are thus happy.
• C will get first choice, and is thus happy.
• Although each person should get at least a third in their mind, this doesn't qualify as an envy-free solution. For example, if B re-balances two pieces and C chooses the piece B increased, then A would envy C because he got more than 1/3 in A's mind. However, A still gets 1/3 in their mind.

I think you can generalize this pattern for $N$ people. Simplified, you give up your place in the picking order if you rebalance, but the trade-off is that you are guaranteed to get a piece you rebalanced or a bigger one. Here's a first take at the priority rules for the picking procedure, though I'm not sure it handles all cases:

1. If N people each have N pieces they rebalanced remaining, the first person who rebalanced from that group gets to choose from their rebalanced pieces. For example, if there is one piece left from the pieces you re-balanced, you get that piece.
2. If you did not re-balance, the highest number gets to pick first
3. If you did rebalance, the lowest cutter gets to pick first

Also, here's an example of how it would work for 4 people:

A cuts the sandwich into 4 equal pieces
If B thinks the top 3 pieces are equal:
If C thinks the top 2 pieces are equal:
D chooses a piece
C chooses a piece
B chooses a piece
A gets the last piece
Else:
C rebalances the top 2 pieces
D chooses a piece
If only one of C's rebalanced pieces remain:
C gets the other rebalanced piece
B chooses a piece
A gets the last piece
Else:
B chooses a piece
If only one of C's rebalanced pieces remain
C gets the other rebalanced piece
A gets the remaining piece
Else
A chooses
C gets the remaining piece
Else:
B rebalances the top 3 pieces
If C thinks the top 2 pieces are equal:
D chooses a piece
C chooses a piece
If only one of B's rebalanced pieces remain:
B takes that piece
A gets the final piece
Else:
A chooses a piece
B gets the final piece
Else:
C rebalances the top 2 pieces
D chooses a piece
If only one of C's rebalanced pieces remain:
C gets that piece
If only one of B's rebalanced pieces remain:
B gets that piece
A gets the last piece
Else:
A chooses a piece
B gets the other piece
Else if only 2 pieces rebalanced by both C & B are left:
B chooses one of the rebalanced pieces
C gets the other one
A gets the last piece
Else:
A chooses a piece
If only one of C's rebalanced pieces remain:
C gets that piece
B gets the final piece
Else:
B gets to choose
C gets the final piece

-
A gets screwed if B and C are in cahoots together. –  Andrew Larsson Jan 14 '14 at 23:32
@AndrewLarsson: No, A will always get one of his fair pieces or more. –  Briguy37 Jan 15 '14 at 2:42
@AndrewLarsson: Thanks :) –  Briguy37 Jan 15 '14 at 14:45
One problem is the rebalancing, I personally wouldn't want a sandwich that is almost 1/3 + several small pieces of sandwich –  Vixen Jan 16 '14 at 23:06

Take the sandwich and divide it into 4 even squares, take 1 of the squares and cut it evenly into 3 rectangular pieces. Everyone now gets a big square and a small rectangular piece.

-
This solution is vaguely reminiscent of Egyptian fractions and becomes very appropriate if you wanted to divide two sandwiches between three people (each gets 2/3). The Egyptian fraction for 2/3 is: 1/2 + 1/6. Thus, you would divide the sandwich into halves and the remaining half into sixths. (See the "practical use of Egyptian fractions" in the link). –  MichaelT Jan 26 '14 at 23:23

Here's my solution...

Let's say it's a pizza and there are 3 people, but it would work for other items or numbers of people.

The pizza is divided into 3 pieces. It's assumed that the pieces are cut into equal sizes, but it's not important... because the "value" of a piece may not be solely dependent on it's size. For example, a smaller piece may have more of a particular topping, or it may be more/less burned, or thicker/thinner, etc.

Each person identifies the piece they want. If each piece is chosen, then everyone is happy... we're done.

Otherwise, each person "bids" an amount of money they are willing to pay for the piece they want. The piece with the highest bid is set aside for that person.

Bidding continues for the remaining pieces until the last piece (and 1 person) is left.

Everyone pays the amount that they bid, and the last person pays an amount that is the average of all the bids, less the amount that the highest bid exceeded the average (which could be $0 or even less, but that should not be typical). From this money, the pizza is paid for, and the remaining money is divided equally among all the people. In the case where the money collected is not enough to pay for the pizza, then everyone pays an equal amount to cover the shortage. Also in this case, you should consider 1: choose another place for your pizza, 2: choose different people to share pizza with. - Person 1 cut out a 1/3 piece. Person 2 and 3 decide what piece they want. If they pick different pieces, the 1/3 piece is given, and other play the 2 people game with the 2/3 piece and players 1. If they both pick the 2/3 piece, player 1 receives the 1/3 piece and they play the 2 people game with the 2/3 piece. If they both pick the 1/3 piece, person 2 cut off a part of the 1/3 piece, that part is then added to the 2/3 piece. Person 3 decide if he takes the remaining 1/3 piece, or plays the 2 people game with player 1. If you do not want to cut the sandwich in more than 3 pieces, go as follow: Person 1 cut out his piece (1/3); Person 2 cut out his piece (1/3); Person 3 can now switch with person 1 or 2 or keep the remaining piece himself. - Your first solution is equivalent to the (not envy-free) proportional division given on Wikipedia. Your second solution is incorrect. Person 1 does not like cake and Person 3 likes cake and Persons 1,3 dislike Person 2, so Person 1 cuts a huge piece out and Person 3 will definitely take it, leaving Person 2 forlorn. – user21820 Jan 17 '14 at 10:33 The second solution is obvious less work and therefore less fair; however if you add the assumption that when person 1 cut out 5/6 cake, person 2 and 3 might argue he meant to take only 1/6 part himself. Even when person 1 and 3 work together, this method still makes it hard to give person 2 less than 1/4th of the cake. If person 2 expect treason, person 1 can give him 1/2 cake and he can cut it into 1/4th parts. It works of course better when all players try to maximize there share. – Dorus Jan 20 '14 at 14:57 Also i did not read wikipedia but nobody else here mentioned that specific way so i tought it was fair to add it. – Dorus Jan 20 '14 at 14:59 I can understand, but we would like to have correct solutions listed here, so if there are like twenty solutions every reader will have to take a long time to think through every single solution, and in that case I would rather go to Wikipedia than come here to find the answer to this question. That said, I commented only to demonstrate that it is not as easy as one might think at first glance, and if you try to prove any of the correct solutions you will find that it is even harder to prove than to devise them. – user21820 Jan 23 '14 at 1:23 Also, if players always maximize their share, then it suffices to have one player cut the cake into 3 pieces and the rest choose one for each of themselves. – user21820 Jan 23 '14 at 1:24 Divide the sandwich into three portions and weigh each one on a digital scale. Adjust until the portions are the same. If equal distribution of condiments is a point of contention, the sandwich must be pureed prior to portioning. No one said it had to taste good. - Amusing to say the least. – Vladhagen Jan 14 '14 at 21:07 Perhaps we need an entropy measure of the resulting condiment distributions to quantify the tolerance of our eaters to condiment envy risk ;) – Trevor Alexander Jan 15 '14 at 7:05 This may be silly, but I think it's fairly straightforward for as many people as you want. If you have$n$people, order person number$1$to cut the sandwich into$n$pieces. All the other$n-1$people then pick their own piece. The person who was cutting gets the piece that was left. If he cut all pieces equally, he will have$1/n$of the sandwich. If any one piece was bigger, this means one piece had to be smaller, and the smaller piece will not get selected, so the cutter has motivation to cut equally. - What if... Person number 1 doesn't really care that much if their piece is a little smaller and that lack of care is reflected in their cutting accuracy. So person 2 selects the biggest piece and person 3-n are left to choose from smaller pieces, leaving the smallest piece for person 1. The only person happy with this is person 2 (and perhaps person 1 who didn't care). The others are left to wonder why person 2 was able to choose first. Even if person 1 cut carefully, some may view person 2's ability to choose first as being unfair. – Kevin Fegan Jan 14 '14 at 20:14 This comment can also be applied to the original case, so I don't think it's all that relevant. I think the task only makes sense if all the people present have the same measure of fairness and are equally interested in it. With those assumptions, my method works. – 5xum Jan 14 '14 at 20:52 It is different. In the original case, with 2 people, if the cutter didn't care and cut poorly (for any reason), the chooser would be happy, and the cutter would be happy (didn't care). The same is the case for the first-chooser and the cutter with 3 or more people (or if the cutter can't cut accurately). The difference is, the remaining "middle" people have no control of the outcome if they are not happy with their piece, compared to pieces choosen before they were able to choose. – Kevin Fegan Jan 14 '14 at 21:17 Point taken. I admit my method needs slighlty stronger assumptions if there are 3 od more people. I still kinda like it, though. – 5xum Jan 16 '14 at 10:20 It is a "classic" method... it's hard to beat the classics. – Kevin Fegan Jan 16 '14 at 19:54 It's simple: one person divides the sandwich into 3 pieces, and that person is the last one to choose (the other two can decide using odds and evens, for instance). The dividing person will not want to make no piece larger than another, because he/she would obviously be left with the smaller one. - If the first person makes one large piece and two small ones, then the person who picks the large piece will be envied by the person who picks the smaller. – Dan Hulme Jan 14 '14 at 14:19 By accident. Cutting three equal pieces of something is not that easy. – Dan Hulme Jan 14 '14 at 14:26 The accident could happen cutting in two, too, even being an easier division. Anyway, @VividD asked for a "such mechanism", not for a "better one". – Rodrigo Jan 14 '14 at 14:31 The point is that when cutting in two, only the cutter loses out if they screw up. In your algorithm, the cutter and one other person lose out, so that other person will "feel deceived". – Dan Hulme Jan 14 '14 at 14:39 Yes, you're right. But considering the practicality of it, I still recommend my solution. Have you memorized the "Selfridge–Conway discrete procedure" to apply it in the real world in a moment of hunger? :) – Rodrigo Jan 14 '14 at 15:11 Call the players A, B, C: A cuts the sandwich in two pieces, and calls it "one third" and "two thirds". B can either • accept the "one third" or • choose to cut the "two thirds" in two halves. In the first case, C gets to cut the "two thirds", and A will choose one of the two halves. In the second case, C chooses one of the two halves, B gets the other half, and A gets the "one third" he cut at the beginning. I think it's the easiest possible solution, assuming the players are honest. - Sounds like C loses if A cuts poorly. – gerrit Jan 14 '14 at 12:35 Actually, C has to wait for A and for B to cut/choose, but A "loses" just as much as C. – G B Jan 14 '14 at 12:51 This isn't a solution. It only works if the participants are in agreement over the value of each piece. – jwg Jan 14 '14 at 13:13 If each piece has a different value for every player, and the value is unknown to the other players, then there is no solution at all (not even for the simple case of 2 players). – G B Jan 14 '14 at 16:42 @GB: The problem is that this is not coalition-resistant. If A and B are friends, then A can cut the sandwich into two equal pieces, so B gets a ½ piece and C is limited to a ¼ piece. Then A and B can get together later and share ¾ of the sandwich. Worse, what if A cuts the sandwich into a huge piece and a tiny piece (e.g., 90% and 10%) and then points to the huge piece and says, “That’s the ⅓ piece.” What recourse does C have then? – Scott Jan 15 '14 at 1:20 Okay, so this is just a small comment about the "general science'' behind all these. You can understand a sandwich as a measure space with$n$given measures. Also, these measures are non-atomic, otherwise you can not solve the problem even for two people. These measures generate a vector measure on the sandwich''. Now you can apply Lyapunov theorem and say, that the range of this measure is closed and convex. But the points$(1,1,...,1)$and$(0,0,...,0)$lie in the range, thus the point$(1/n,..., 1/n)$does. This means, that there is a piece of sandwich such that each person thinks that it is exactly$1/n$of the whole sandwich. Now you can give it to anyone and repeat the procedure. Cool thing is that you will divide the sandwich in such a way that each person will think, that the sandwich is divided into equal parts. So one can solve the problem in the following form "There is a way to divide a sandwich such that each person thinks that no one have more sandwich than him". I have no idea how to make an explicit algorithm for that one. - +1 for "non-constructive" type argument. ;) – Trevor Alexander Jan 14 '14 at 7:27 Sounds a lot like the ham sandwich theorem, in fact. – Trevor Alexander Jan 14 '14 at 7:34 That result is originally due to Dubins and Spanier. – Michael Greinecker Feb 18 '14 at 13:02 The "one person cuts, the other chooses" algorithm generalises to any number of people, but the generalisation is (a) not envy-free; (b) vulnerable to collusion in a subset of at least two of the participants. It does work for cases where one or more participants want a piece of size$ < \frac{1}{n}$, but it splits their share unfairly among the remaining participants. The participants sit in a circle. Person 0 cuts a portion from the cake. (They don't cut the cake all the way through, but just cut one slice from it.) The resulting portion is offered to person 1. If he accepts it, he takes it and is removed from the circle; otherwise, it's offered to person 2, and so on around the circle. If no one takes it, the portion is returned to person 0, who must take it and is removed from the circle. This procedure is repeated with the remaining participants (starting with person 1 if they're still present, otherwise person 2), until there is only one person left. This person gets the left-over slice of cake which has never been offered to anyone. It's clearly very gameable, but if the participants are basically honest, it works well. At least it runs in bounded time and delivers connected portions. Its main practical problem is that one participant can cut a slice that's much too large, advantaging one participant at the expense of all the others. But unlike the "one person cuts all slices" method, the resentment gets to be spread among all the participants who slice, not just focused on one person. - Collusion, though possible, would not be subgame perfect. There are N people. I cut the sandwich into a large piece and N-1 tiny pieces, thinking that the recipient of the large piece will tip me a portion > (1/N). Problem is, they now have their meal, and they don't have to share. Such a bargain could only be enforced because (a) I have a knife, or (b) there is a repeated context, or (c) some other enforcement mechanism outside the game – Paul Jan 14 '14 at 11:13 That's true, but realistically, context outside the game is likely. Sitting a husband far from his wife would be an obvious precaution, for instance. – Dan Hulme Jan 14 '14 at 11:22 I think it's just too complex. If player 1 doesn't accept the first portion, and player 2 does, there is something wrong, unless you count other factors (getting a smaller portion instead of waiting longer). – G B Jan 14 '14 at 12:30 @GB - "If player 1 doesn't accept the first portion..." the piece may be a "fair" sized piece (1/n) and so player 2 accepts it. Player 1 may just be waiting for a piece that is larger or smaller (than 1/n), or a piece with a cherry (decoration) on it, or more/less frosting, or just one that "looks" better. – Kevin Fegan Jan 16 '14 at 20:50 @KevinFegan There goes the "not feeling deceived" part. If different pieces have different (subjective) values, there is no solution. – G B Jan 17 '14 at 9:14 It might help what is in the sandwitch. If it's a BLT for example then one of the people might be a vegetarian, but might feel cheated if the other gets more tomato. On the otherhand the bacon will be up for grabs. The lettuce is a wild card of course if they all want it. I think what you have to do is negotiate sandwitch parts with the others. Perhaps one person will be happy letting the other eat all the bacon if they can eat all the tomato and lettuce. Perhaps one is gluten intolerant so they don't mind the 3rd person having all the bread. The other alternative is for each person to bring their own sandwitches. We had a similar problem like this at work once with pizza and we basically decided not to eat shared pizza anymore. - Yeah, what if pizza is quattro stagione? – VividD Jan 14 '14 at 10:41 We had a similar problem like this at work once with pizza and we basically decided not to eat shared pizza anymore. — You must not be mathematicians at work. – gerrit Jan 14 '14 at 12:32 Hmm, if you cut it into an approximate 3rd and 2/3rds portions, then the cutter would get a slice that both other people think is about 1/3rd. To attempt to subvert this, player A could cheat and make 2 equal halves. In the real world, such a player would never get invited to party games again. ;) But let's just say that then one of the other players would have to divide each half into 1/6th and 1/3rd slices. Repeat ad nauseum? If you can 'uncut' the sandwich, then it's easier: Just keep having a different player cut the sandwich until the other 2 agree. This is similar to the moving-knife solution but where the cut is not done unless all 3 agree, in actual practice since 'uncutting' really means just not cutting yet. Once you get the bigger piece being roughly 2/3rds, then you can apply the normal 2-person method. To go to 4 people, vote in pairs? You could also apply this idea with 1/4th & 3/4ths slices. This is generalizable to 5,...,dozens of people. - Okay, I've got a weird idea that I think might work. Viewed from above, the sandwich is a square, right? Since a square is technically a disc in$L_1$space, I think you can use the pizza theorem to cut it into 12 pieces and divide it evenly with way less work than Selfridge-Conway. I think this should work because 12 divides into 4 (a pizza theorem requirement) but also divides into 3. I started with the following image from Wikipedia: My algorithm was, first divide the pizza along the cardinal directions. Then, enumerating over each such section, color each first wedge, second wedge, third wedge, and fourth wedge (modulo 3) black. Offset that sequence by 1, and repeat twice more. Here is the result: I have a feeling that this is at least a good approximation. The color permutation might not be so simple, though--the claim is that there exists such a permutation for any set of cuts that satisfy the requirements of the theorem. ### edit: I'm more confident about this one. The algorithm for this one is much more intuitive: 1. Observe that there are 3 "opposite pairs" of slices of each color. 2. Select one opposite pair of each color, and recolor it. The claim is that each pair of opposites is a third of half of the pizza sandwich. - Disclaimer: This may only work on square circles in a Manhattan world ;) – Trevor Alexander Jan 14 '14 at 7:08 Alternatively, you may perform a certain transformation on the sandwich to get a circle before attempting to use this algorithm. – Trevor Alexander Jan 14 '14 at 7:20 +1 for introducing the Pizza theorem to me, something I always thought to be true but had never completely worked out. – SQB Jan 14 '14 at 7:30 You can subdivide the (square) sandwich in an infinite number of circles, on which you can apply this theorem. Though, lunch time might be over by then.. – Jochem Kuijpers Jan 14 '14 at 12:39 I don't think so, because each cut affects four pieces, and there are only three players. Plus, you still cannot guarantee equal divisions, which is really the original problem. I was playing with the following example that exaggerates the "unfair cuts" problem. It would be impossible to distribute the pieces of this "sandwich" fairly, no matter how many players there are: i.imgur.com/3H1LWqG.png – indot_brad Jan 14 '14 at 21:54 For dividing a cake to$n$people, there is an algorithm that guarantees that: • Each of the$n$people gets a piece that he considers at least as good as each of the other pieces (i.e., the division is envy free); • All pieces are connected (actually, all pieces are rectangles). This algorithm was invented by Forest Simmons and published by Francis Su at 1999. The only problem with this algorithm is that its runtime is not bounded, i.e., it might take forever (As proved by Stromquist at 2008, no bounded algorithm can find an envy-free division when we want the pieces to be connected). But, you can stop at any time and get a division that is approximately envy free. - Great answer, explains high-level facts about the algorithm. – VividD Jan 14 '14 at 17:35 Still, this is basically a link-only answer, since it doesn't even give an hint on how the actual algorithm works. – Lohoris Jan 15 '14 at 15:54 According to Wikipedia, the Brams-Taylor procedure is the first finite procedure to produce an envy-free division of an infinitely divisible good among any positive integer number of players. A nice discussion about it can be found here. - Ironically it is patented instead of infinitely copied and shared in an envy-free way with the n players of the internet... – Chris Wesseling Jan 14 '14 at 13:32 @ChrisWesseling I'm going to patent the method for taking into account the overhead costs of paying a royalty every time you use this method to determining whether you would be better off using it versus luck or fend for yourself. – Michael Jan 14 '14 at 15:26 This was covered in the first class I ever TAed in graduate school. Naturally, the reaction of most of the students was, "why don't they just eat the cake?" Person A cuts it into two pieces she views as "of equal value." Person B then chooses her favorite half. A and B then each divide their halves into thirds that they views as "of equal value." Person C then chooses her 1 favorite piece from A and one favorite piece from B. This ensures a fair (but not envy-free) division. - Yes this is the inefficient solution in the Wikipedia article I gave. The other solution there takes a polynomial number of cuts which comes up to only 3 cuts for 3 people. – user21820 Jan 14 '14 at 5:55 I like this version for its simplicity. The general recursive algorithm: if$n = 1$then take the whole cake; if$n > 1$then recursively divide the cake among$n-1$people and then have each of those people divide their cake into$n$portions they believe are equal. The$n$-th person now chooses one portion from each of the$n-1$other people. – ntc2 Jan 16 '14 at 21:51 Complete EDIT (too lazy to formulate mathematically): Imagine X as a sandwich just for simplicity. The first person cuts X into thirds "horizontally" and they have to cut across the whole sandwich in a straight line with each cut. The second person cuts each third into thirds by cutting the sandwich "vertically" with each cut going through all of the original thirds in a straight line. Now there are 9 pieces. Third player picks one piece and then first person picks, then second and third again in a circle.... This operation with the horizontal and vertical constraints (and having to go right across the sandwich) should avoid anyone feeling deceived. - Of course if it was an actual sandwich it would be destroyed probably by cutting it into 27 pieces :) – John U Jan 14 '14 at 5:17 I am upvoting this solution because of its 3D nature. :) – VividD Jan 14 '14 at 5:37 So, for four people we would need sandwich in 4-dimensional space? ;) – VividD Jan 14 '14 at 5:38 Well imposing the ratios is just as difficult (if not more, what with all the crumbs) than just requiring one of the three to divide fairly. Furthermore even imposing ratios doesn't solve the problem because some parts of the sandwich may be mouldy... – user21820 Jan 14 '14 at 5:52 You are assuming much too much about the 'uniformity' of the value ascribed to areas of the sandwich. – jwg Jan 14 '14 at 13:14 For more than two, the moving knife is a nice solution. Somebody takes a knife and moves it slowly across the sandwich. Any player may say "cut". At that moment, the sandwich is cut and the piece given to the one who said "cut". As he has said that is an acceptable piece, he believes he has at least$\frac 1n$of the sandwich. The rest have asserted (by not saying "cut") that is it at most$\frac 1n\$ of the sandwich, so the average available is now at least their share. Recurse.

-
Note that this is not an envy-free division but just called a proportional division. In fact there is an easy solution for that that doesn't require a moving knife (en.wikipedia.org/wiki/Proportional_%28fair_division%29). Some people will not think a moving knife algorithm is fair because the one moving the knife may move slightly after someone says "Cut!". –  user21820 Jan 14 '14 at 5:43
Nice! You used the invisible hand of the market to cut the sandwich. –  user Jan 14 '14 at 10:29
@user One could build a machine and everyone gets a button. Not exactly ideal for a student flat, unless they are engineering students... –  user1729 Jan 14 '14 at 11:29
@user1729 Engineering students would design the machine to ensure accurate proportioning to start with, you'd only need one button to start the machine (and to stop it, for safety reasons). –  JAB Jan 14 '14 at 12:55
@user1729 then your boss is not an engineer. He just thinks he is. –  John Jan 14 '14 at 18:14

## protected by Asaf KaragilaJan 15 '14 at 9:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.