Splitting a sandwich and not feeling deceived

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.

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.

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.