Stromquist's 3 knives procedure

Question

(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".

Answer 1

Edit: The below does rely on the assumption that knives move continuously, see the comments.

I think the procedure is "safe": Each player can guarantee not to envy either of the others by following the suggested protocol. I am assuming that the rules are that players must keep their knives to the right of the sword. Intuitively, the straightforward proof of envy-freeness, following, does not use that the other players are playing truthfully (they can be playing arbitrarily).

Suppose a player "Marge" wants to guarantee herself an envy-free piece. Marge follows the suggested strategy: She keeps her knife at her perceived midpoint of the section to the right of the sword, and yells "cut" if at any point she prefers the piece left of the sword to both other pieces that will result.

If neither of the other players ever yell cut, then eventually Marge will yell cut and get an envy-free allocation. So the players can only disrupt her by yelling cut before she does. However, since she has not yet yelled cut, Marge must prefer one of the other two resulting pieces to the left piece. So we just need to check that, when one of the other players yells cut, Marge will get her more-preferred piece between the center and the right.

If her knife was the one used to cut, then since she was following protocol, she is indifferent between the center and right pieces (preferring both to the left piece), and she gets one of them, so she is not envious.

If her knife was not used to cut, then either it is nearest to the sword or it is farthest from the sword. Suppose her knife is nearest to the sword. Then she gets the center piece. But because her knife is located to make her indifferent between (a) the section between the sword and her knife and (b) the section between her knife and the rightmost edge, and because she gets section (a) and more besides, she prefers the center piece that she gets to the right piece. The analogous argument works if her knife is farthest from the sword.

...

I would guess that there is another argument which says that any strategic disruptive player could be simulated by an honest player with a certain preference, implying that it would be sufficient to show the protocol is envy-free, when players are truthful, for all possible preferences.