Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
Level: BSc, MSci, MSc
Title: Cake cutting
Supervisor:

Dr Felix Fischer

Research Area: Combinatorics
Description:

Cake cutting serves as a metaphor for the division of a heterogeneous, divisible good, the cake, among a set of interested parties. For two participants the simple procedure where one participant cuts the cake into two pieces she values equally and the other chooses one she prefers is envy-free, meaning that neither participant prefers the other's piece to her own. Envy-free allocations with a polynomial number of cuts in fact exist for any number of participants with continuous valuation functions, but a procedure for constructing an allocation with a bounded number of cuts was not known until very recently.
Further Reading:
  • N. Alon, Splitting necklaces, Advances in Mathematics 63 (1987) 247–253.
  • H. Aziz, S. Mackenzie, A discrete and bounded envy-free cake cutting protocol for any number of agents, in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, 2016. 416–427.
  • A. D. Procaccia, Cake cutting algorithms, in Handbook of Computational Social Choice, Edited by F. Brandt, V. Conitzer, U. Endriss, J. Lang and A. D. Procaccia, Cambridge Univ. Press, New York, 2016. 311–330.
Key Modules:
MTH6109 Combinatorics (useful, but not essential)
MTH716U/MTHM007 Measure Theory and Probability (useful, but not essential)
Other Information:
Current Availability: Yes