third player places a value of 2 units on [0, 1 6
], 0 units on each of [ 16
,
1 3
] and [ 13
,
2 3
], and 4 units on [ 23
, 1]. As before, we suppose that k **= 2 (i.e. at any one time, two players are watching**
the knife). The first player calls "cut" and departs with the slice [0, 1 3
]. The second player calls "cut" and departs with the slice [ 13
,
2 3
], leaving the third player with the slice [ 23
, 1].

On the other hand, if the third player arrives ahead of the second player then the value of the cake allocated to them drops from 4 units to 2 units. Hence the procedure is not order monotonic. ♥

## 8 Online Mark-And-Choose

A possible drawback of both of the online cake cutting procedures proposed so far is that the first player to arrive can be the last player to depart. What if we **want a procedure in** which players can depart soon after they arrive? The next procedure has such a property. Players will depart as soon as the next player arrives (except for the last player to arrive who takes whatever cake remains). However, the new procedure **is no longer sequential. It** may not allocated cake from one end. In addition, the new procedure does not necessarily allocate continuous slices of cake.

In the online mark-and-choose procedure, the first player to arrive marks the cake into n **pieces. The second player to arrive selects one piece to give to the first player who then**
departs. The second player then marks the remaining cake into n − **1 pieces and waits for**
the third player to arrive. The procedure repeats in this way until the last player arrives. The last player to arrive selects which of the two halves marked by the penultimate player should be allocated to the penultimate player. The last player then takes whatever remains.

Running Example:. Consider again the example in which there are three players, **the first**
player values only [
1 2
, 1]**, the second player values only** [
1 3
, 1]**, and the third player values only**
[0, 3 4
]**. If we operate the online version of the mark-and-choose procedure, the first player will**
arrive and mark the cake into 3 equally valued pieces: [0, 2 3
], [
2 3
,
5 6
]**, and** [
5 6
, 1]**, The second**
player then arrives and selects the least valuable piece for **the first player to take. In fact,** both [
2 3
,
5 6
] and [
5 6
, 1] **are each worth** 14 of the total value of the cake to the second player.

They will therefore choose between them arbitrarily. Suppose the second player decides to give the slice [
2 3
,
5 6
] **to the first player. Note that the first player assigns this slice with** 13 of the total value of the cake. This leaves behind two sections of cake: [0, 2 3
] and [
5 6
, 1].

The second player then marks what remains into two equally valuable pieces: the first is the interval [0, 7 12 ] **and the second contains the two intervals** [
7 12 ,
2 3
] and [
5 6
, 1]**. The third player**
then arrives and selects the least valuable piece for the second player to take. The first piece is worth 7 12 **of the total value of the cake to the third player. As this is over half the total**
value, the other piece must be worth less. In fact, the second **piece is worth** 14 of the total value. The third player therefore gives the second piece to the second player. This leaves the third player with the remaining slice [0, 7 12 ]**. It can again be claimed that everyone is happy**
as the first players received a "fair"' proportion of the cake **that was left when they arrived,** whilst both the second and third player received an even greater proportional value.

This procedure again has the same desirable properties as the online **version of the**
cut-and-choose and moving knife procedures.

Theorem 5. **The online mark-and-choose procedure is forward proportional, immediately**
envy free, weakly truthful, surjective, and scale invariant. However, it is not proportional,
(forward) envy free, equitable, (weakly) Pareto optimal, truthful, order monotonic or sequential.

Proof: **Any player marking the cake will divide it into slices of equal value (for fear that**
they will be allocated one of the less valuable slices). Similarly, a player selecting a slice for 8