Abstract:
The classic cake-cutting problem provides a model for addressing fair allocation of a divisible resource (metaphorically, the cake) among agents with distinct preferences. Envy-free (fair) cake divisions with contiguous pieces are known to exist under mild conditions, but it is computationally hard to find them. In this talk, I will present two of my recent results which complements these existential (and non-constructive) guarantees by developing polynomial-time approximation algorithms and by identifying computationally tractable instances for fair cake division. First, I will discuss an efficient algorithm for finding a cake division whose envy is multiplicatively bounded by 1/3. Moving forward, I will present a result that develops efficient cake-cutting algorithms to find envy-free divisions for a broad class of valuations (that satisfies the monotone likelihood ratios property). In particular, our algorithmic result holds when the agents’ valuations are induced by linear translations of any log-concave function, such as Gaussian, exponential, linear, or binomial.
Joint work with Siddharth Barman, Eshwar Ram Arunchaleswaran and Rachitesh Kumar
