The theory of Fair Division addresses the fundamental problem of allocating goods among agents with equal entitlements but distinct preferences. The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with varied preferences. Classic results of Stromquist (1980) and Su (1999) show that envy-free (fair) cake divisions (with contiguous pieces) are guaranteed to exist under mild conditions. These strong existential results follow from fixed-point theorems and stand without an algorithmic counterpart.
In this talk, I will present two of the recent results that complements the existential (and non-constructive) guarantees and various hardness results either by developing polynomial-time approximation algorithms or by identifying computationally tractable instances for fair cake division. Our work identifies a broad class of cake division instances that essentially admits a polynomial time algorithm for computing fair and efficient allocations. In particular, our algorithmic result holds when (all) agents' valuations are induced either by linear translations of any log-concave function, Gaussian, exponential, linear, or binomial distributions.
Joint work with Siddharth Barman, Eshwar Ram Arunchaleswaran and Rachitesh Kumar.
