Fair Cake Division


The theory of Fair Division addresses the fundamental problem of allocating goods among agents with equal entitlements but distinct preferences. Here, the resources can be (1) divisible like water/land, (2) indivisible like courses in universities, property settlements or (3) indivisible resources with money like electronic frequency allocation. In this talk, I will, in particular focus on the classic cake-cutting problem that provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. I will present some of the recent results that complements the existential (and non-constructive) guarantees and various hardness results by way of developing efficient (approximation) algorithms for cake division. I will also talk about a recent result that identifies a broad class of cake division instances that essentially admits a polynomial time algorithm to compute fair and efficient allocations.

The Speaker

Nidhi Rathi is an Integrated PhD student at the Department of Mathematics, Indian Institute of Science (IISc). She started her research as a PhD scholar under the guidance of Prof. Siddharth Barman (Dept. of Computer Science and Automation, IISc) and Prof. Mrinal K. Ghosh (Department of Mathematics, IISc). She is a recipient of the prestigious IBM PhD fellowship 2020. Her main area of research is Algorithmic Game theory. In particular, she is interested in exploring the computability of equilibria and fair resource allocations under various settings, and hence, developing algorithms with provable fairness guarantees. She was one of the invited speakers in ACM summer school on Algorithmic Game theory held at IIT Gandhinagar in the summer of 2019.