On the computability of equitable divisions

Let the cake be represented by the unit interval of reals, with players having private valuations expressed by nonatomic probability measures. The aim is to find a cake division which assigns to each of n players one contiguous piece (a simple division) in such a way that the value each player receives (by her own measure) is the same for all players and this common value is at least 1/n. It is known that such divisions always exist, however, we show that there is no finite algorithm to find them already for three players. Therefore we propose an algorithm that for any given epsilon > 0 finds, in a finite number of steps, a simple division such that the values assigned to players differ by at most epsilon > 0. (c) 2012 Elsevier B.V. All rights reserved.