
## 10 Related Work

There is an extensive literature on fair division and cake cutting procedures. See, for instance, [2] for an introduction. There has, however, been considerably less work on fair division problems similar to those considered here.

Thomson considers a generalization of fair division problems where the number of players may increase [7]. He explores from an axiomatic perspective whether **it is possible to have** a procedure in which players' allocations are monotonic (i.e. their values do not increase as the number of players increase) combined with other common properties like weak Pareto optimality.

Cloutier et al. **consider a different generalization of the cake cutting problem in which the**
number of players is fixed but there are multiple cakes [5]. This can model situations where, for example, players wish to choose shifts across multiple days. Note that this problem can be reduced to multiple single cake cutting problems unless the players' valuations across cakes are linked (e.g. you prefer the same shift each day compared **to different shifts).**
A number of authors have studied distributed mechanisms for fair division (see, for example, [4]). In such mechanisms, players typically agree locally on deals to exchange some of the goods in their possession. The usual goal is to identify conditions under which the system converges to a fair or envy free allocation.

## 11 Conclusions

We have proposed an online form of the cake cutting problem. This permits us to explore the concept of fair division when players arrive and depart during the process of dividing a resource. It can be used to model situations, such as on the internet, when we need to divide resources asynchronously. There are many possible future **directions for this work.** One extension would be to indivisible goods. Another extension would be to undesirable goods (like chores) where we want as little of them as possible. In addition, it would be interesting to consider variants of the online cake cutting problem where players have information about the valuation functions of the other players.

## Acknowledgements

NICTA is funded by the Department of Broadband, Communications **and the Digital Economy, and the Australian Research Council.**

## References

[1] S.J. Brams, M.A. Jones, and C. Klamler. Better ways to cut a cake. **Notices of the AMS**,
53(11):1314–1321, 2006.

[2] S.J. Brams and A.D. Taylor. **Fair Division: From cake-cutting to dispute resolution**.

Cambridge University Press, Cambridge, 1996.

[3] Y. Chen, J.K. Lai, D.C. Parkes, and A.D. Procaccia. Truth, justice, and cake cutting.

In Proceedings of the 24th National Conference on AI**. Association for Advancement of** Artificial Intelligence, 2010.

[4] Y. Chevaleyre, U. Endriss, and N. Maudet. Distributed fair allocation of indivisible goods. Working paper, ILLC, University of Amsterdam, 2009.