Splitting a sandwich and not feeling deceived

Question

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

---

Yesterday, I was 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. I thought, 'What if 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.

Answer 1

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 A2₁.

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

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

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

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.

Answer 17

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.

Answer 18

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.

Answer 19

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.

Answer 20

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

Answer 21

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.

Answer 22

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.

Answer 23

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