(copied from [math.SE][1])

BACKGROUND: A cake has to be divided among 3 people with possibly different tastes, such that each person receives a single connected piece, and no person prefers another person's piece. In other words, no participant should end up being *envious* of any other participant. Symbolically, let $\ v_{jk}\ $ be the value of the $k$-th piece to participant $\ j\ $. We would like:

$$\forall_{j=1\ 2\ 3}\ \ \ v_{jj}\ \ =\ \ \max(v_{j1},\ v_{j2},\ v_{j3})$$

This problem was unsolved for several tens of years, until [Stromquist (1980)][2] suggested the following division protocol:

> A referee moves a sword from left to right over the cake, hypothetically
> dividing it into a small left piece and a large right piece. 
> Each player holds a knife over what he considers to be the midpoint of
> the right piece. As the referee moves his sword, the players continually
> adjust their knives, always keeping them parallel to the sword.
> When any player shouts "cut", the cake is cut by the sword and by
> whichever of the players' knives happens to be the middle one of the three.

> The player who shouted "cut" receives the left piece. He must be satisfied,
> because he knew what all three pieces would be when he said the word.
> Then the player whose knife ended nearest to the sword, if he didn't 
> shout "cut", takes the centerpiece; and the player whose knife was farthest
> from the sword, if he didn't shout "cut", takes the right piece. The 
> player whose knife was used to cut the cake, if he hasn't
> already taken the left piece, will be satisfied with whatever piece is left over. 
> If ties must be broken - either because two or three players shout 
> simultaneously or because two or three knives coincide - they may be
> broken arbitrarily.

It is clear that, if all players play truthfully (according to their own value function), the resulting division is indeed envy-free. My question is: what happens if two players play untruthfully, against their own interest - can they make the third player envious?

In most protocols for cake-cutting among $\ n\ $ participants, the answer is "no", i.e., every player that plays truthfully is guaranteed to receive an envy-free share, regardless of what the other players do. For example, consider the classic protocol for 2 players: "I cut, you choose". I (the cutter) have to cut the cake to two pieces that I consider to be of equal value, but, even if I cut the cake in a very strange manner to two very unequal pieces (even against my own interest), *you* still have a safe strategy - you just pick the piece that you consider to be more valuable, and you are guaranteed to feel no envy. In other words, the cut-and-choose protocol (and most other cake-cutting protocols) is *safe* for truthful players.

So, my question is: is Stromquist's procedure indeed safe for truthful players? I.e. does it guarantee that every single player playing by the rules feels no envy, regardless of what the other players do?


  [1]: http://math.stackexchange.com/questions/916884/stromquists-3-knives-procedure
  [2]: http://dx.doi.org/10.2307/2320951