# Online Cake Cutting Toby Walsh

## Abstract

We propose an online form of the cake cutting problem. This models situations where players arrive and depart during the process of dividing a resource. We show that well known fair division procedures like cut-and-choose and the **Dubins-Spanier moving** knife procedure can be adapted to apply to such online problems. We propose some desirable properties that online cake cutting procedures might possess like online forms of proportionality and envy-freeness, and identify which properties are in fact possessed by the different online cake procedures.

## 1 Introduction

Congratulations. Today is your birthday so you take a cake into the office to share with your colleagues. At tea time, people slowly start **to arrive. However,** as some people have to leave early, you cannot wait for everyone to arrive before you start sharing the cake. How do you proceed fairly?

This is an example of what we call an online **cake cutting problem. Most previous studies**
of cake cutting procedures have assumed that all the players are **available at the time of** the division. Here, players arrive and depart (either with their cake **or perhaps after they** have eaten their cake) as the cake is being divided. Such online problems occur in the real world as in our birthday example, but also on the internet where agents are often connecting asynchronously.

Online cake cutting poses some new challenges. On the one hand, the **online aspect of**
such problems makes fair division more difficult than in the offline case. How can we ensure that a player does not envy another player when we may have to distribute cake to the second player before the first player is present (and we can hope to determine information about their valuation function)? On the other hand, the online aspect of such problems may make fair division easier than in the offline case. If players don't see cake that has already been distributed before they arrive, perhaps they do not envy it?

## 2 Online Cake Cutting

As is common in the literature [2], we will often assume that each player **is risk averse so** they maximize the minimum value of the cake that they will receive, regardless of what the other players do. A risk averse player will not choose a strategy that could yield more value if it also entails the possibility of getting less value. We will also usually assume that each player is ignorant of the value functions of the other players. **We disuss relaxing these** assumptions in the conclusions.

We formulate cake cutting as dividing the unit interval between the different players, where each player has a (typically additive and continuous) valuation **function on the intervals that they are allocated. We do not suppose that players assigns the same value**
to the whole cake. Although we can normalize the valuation functions, we shall see that is not necessary as all the cake cutting procedures are scale invariant**. Depending on the** application, we may demand that players receive a continuous slice of **cake or some union** of slices.