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

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.

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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