In an online cake cutting problem, the players arrive in some given order. Players are allocated their cake and then depart. The order in which players depart can be fixed or can be change according to how they value the cake. For example, the player present who most values a cut slice of cake might be the next to depart. Alternatively, the player to depart might always be the player who arrived the longest time ago. We will assume that at least one player departs before the last player arrives (otherwise we can formulate this as an offline cake cutting procedure). To prevent trivial allocations, we also assume that at least one player receives some cake. However, we do not assume **that all players receive**
cake or that all the cake is allocated. Formally an online cake cutting problem is defined by a procedure which given the valuation functions of the players who are present in the room and the number of players who will take part in total either allocates some cake to one of the present players (who then departs) or indicates that we wait until the next player arrives. This can model both a fixed arrival and departure order, **as well as one in which**
the order depends on the valuation functions.

An important dimension of online cake cutting is what is known and by whom about the total number of players. For example, the total number of players might be known by all players. On the other hand, the players might only know a bound on the total number of players (e.g. you've invited 20 work colleagues to share your birthday cake but not all of them might turn up). However, there are several other **possibilities (e.g. certain**
players might have complete certainty about n **whilst others have complete uncertainty).**
In addition, an interesting generalization is when cake is being allocated before the total number of players is fixed.

## 3 Desirable Properties

What properties do we want from an online cake cutting procedure? **The literature on cake** cutting studies various notions of fainerness like proportionality and envy freeness, as well as various forms of strategy proofness. The generalization of cake **cutting to an online setting** gives rise to some natural extensions of these notions.

## 3.1 Proportionality

A cake cutting procedure is proportional iff each of the n **players assigns at least** 1n of the total value to their piece(s). Unfortunately, as we shall show, online cake cutting procedures cannot always be proportional. Suppose you only like icing. The problem is that you may not be able to prevent all the cake that is iced being distributed before you enter the room. We therefore consider weaker forms of proporitionality that are achievable. One more limited form of proportionality is that any player receives a fair proportion **of the cake that remains** when they arrive. A cake cutting procedure is forward proportional **iff each player assigns**
at least r n−k of the total value of the cake to their pieces where r **is the fraction of the total**
value assigned by the player to the (remaining) cake when they arrive and k **is the number**
of players who have already left at this point.

## 3.2 Envy Freeness

A stronger notion of fairness is envy freeness. A cake cutting procedure is envy free iff no player values another player's pieces more than their own. Note that envy freeness implies proportionality but not vice versa. With online cake cutting, envy freeness is also impossible to achieve in general. We therefore consider weaker forms of envy freeness that are achievable. A cake cutting procedure is forward envy free **iff no player values the pieces** of cake allocated to other players after their arrival more than their own. Players can,