Bhargav Narayanan, Rutgers University, presents this seminar.
A finite number of agents, each with their own measure of utility, would like to cut up a piece of cake amongst themselves. How efficiently can they do this? Almost everything one would like to know about this problem is known in the case where the agents all want a fair share of the cake. The more general problem where the agents have different claims to the cake is less well understood; in this talk, I shall present a new, efficient division procedure for the general problem that yields nearly optimal bounds. Along the way, we’ll take the scenic route through some algebraic topology and end up at some combinatorics.