DIKUL - logo
E-viri
Recenzirano Odprti dostop
  • On the computability of equ...
    Cechlárová, Katarína; Pillárová, Eva

    Discrete optimization, November 2012, 2012-11-00, Letnik: 9, Številka: 4
    Journal Article

    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 ε>0 finds, in a finite number of steps, a simple division such that the values assigned to players differ by at most ε>0.