Cake cutting, balanced hypergraphs and topology

Cake cutting, balanced hypergraphs and topology

-
Eli Berger, University of Haifa

The problem of "envy-free" cake cutting deals with n agents who need to share r cakes between them, where cake number i is sliced into a_i slices. For each agent, each possible slicing, and each choice of one slice from each cake, this choice is defined to be either "acceptable" or "unacceptable" for this agent. We ask questions such as whether it is always (under some natural assumptions) possible to choose a slicing of the cakes and assign an acceptable set of slices for each of the agents, or alternately to m of the agents, where m \le n is some given number. This turns out to be linked to the problem of finding a matching in hypergraphs known as balanced r+1-partite hypergraphs, which in turn is linked to the notion of topological connectivity of the matching complex of r-partite hypergraphs. In my talk, I will show how these notions are related, and how these methods are used to generalize some known results and prove some new ones.

This is joint work with Ron Aharoni, Joseph Briggs, Erel Segal-Halevi and Shira Zerbib.