The cake-cutting problem provides a model for addressing fair allocation of a divisible resource (metaphorically, the cake) among agents with distinct preferences. Classic results of Stromquist (1980) and Su (1999) show that envy-free (fair) cake divisions are guaranteed to exist under mild conditions. These strong existential results essentially follow from fixed-point theorems and stand without an algorithmic counterpart; Stromquist (2008) has shown that an envy-free cake division with contiguous pieces cannot be computed in bounded time.
In this talk I will present a result which complements these existential (and non-constructive) guarantees by way of developing efficient cake-cutting algorithms for a broad class of valuations. 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.
