(copied from math.SE)

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\ $ (the values for each player are based on a continuous measure). 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) 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.

Note that all knives are visible to all players.

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?

EDIT: Here is the problematic scenario I had in mind when asking.

Suppose there are two evil players - Kunning (K) and Liar (L), who want to hurt the good player Marge (M). Initially K and L put their knives close to the sword (S), like this:

```
|----------SKL------M--------|
```

Now Marge knows that if she remains quiet, she will get the piece between L and the right border, which is larger than the piece to the left of S, so she remains quiet. But then L moves his knives *discontinuously* to the right, like this:

```
|----------SK------LM--------|
```

And at the same moment, K shouts "cut". Now the piece to the right of L is smaller than the piece to the left of S, so Marge should shout "cut" now, but there is 50% chance that the protocol will give the piece to the left of S to K, who shouted at the same time, and Marge will envy him.

This scenario is possible only if L is not truthful. Why? Because a cake is assumed (as usual) to be non-atomic - the value of every subset of zero length is zero. Hence the value to the left of the sword is a continuous function of time, and the middle point of the part to the right of the sword is also a continuous function of time. But, if a player is not truthful, he may decide to make the position of his knife a discontinuous function.

So my more specific question is: is my description of the above scenario correct? If it is, how can the procedure be corrected? Maybe by requiring that the location of each knife is a continuous function of time?

EDIT 2: In second reading, I see that Stromquist indeed mentioned that "the players **continually** adjust their knives".

Question. Thus the whole issue is about the players which act funny :-) $\endgroup$ – Włodzimierz Holsztyński Sep 10 '14 at 10:54