On the computability of equitable divisions

On the computability of equitable divisions

0.00 Avg rating0 Votes
Article ID: iaor20125788
Volume: 9
Issue: 4
Start Page Number: 249
End Page Number: 257
Publication Date: Nov 2012
Journal: Discrete Optimization
Authors: ,
Keywords: game theory
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.