12 October 2007, Computational Social Choice Seminar, Ulle Endriss
The problem of fairly dividing a cake amongst two or more players has been recognised as a question of serious mathematical interest ever since the seminal work of Banach, Knaster and Steinhaus in the 1940s. Recently, people have also started investigating the complexity of cake-cutting (how many cuts are required to achieve a certain type of solution?), and there have been attempts to give logic-based models for cake-cutting problems that would allow us to formally verify the correctness of a proposed algorithm.
Over the coming months we expect to have a couple of talks on cake-cutting in the Computational Social Choice Seminar. This first talk will be a tutorial-style introduction to the field, where I will present some of the classical algorithms and discuss open problems. No specific background knowledge will be required to follow the presentation.