Online Cake Cutting
We propose an online form of the cake cutting problem. This models situations where agents arrive and depart during the process of dividing a resource. We show that well known fair division procedures like cut-and-choose and the Dubins-Spanier moving knif
- PDF / 261,006 Bytes
- 14 Pages / 429.442 x 659.895 pts Page_size
- 32 Downloads / 197 Views
Abstract. We propose an online form of the cake cutting problem. This models situations where agents arrive and depart during the process of dividing a resource. We show that well known fair division procedures like cut-and-choose and the Dubins-Spanier moving knife procedure can be adapted to apply to such online problems. We propose some fairness properties that online cake cutting procedures can possess like online forms of proportionality and envy-freeness. We also consider the impact of collusion between agents. Finally, we study theoretically and empirically the competitive ratio of these online cake cutting procedures. Based on its resistance to collusion, and its good performance in practice, our results favour the online version of the cut-and-choose procedure over the online version of the moving knife procedure.
1 Introduction Congratulations. Today is your birthday so you take a cake into the office to share with your colleagues. At tea time, people slowly start to arrive. However, as some people have to leave early, you cannot wait for everyone to arrive before you start sharing the cake. How do you proceed fairly? This is an example of an online cake cutting problem. Most previous studies of fair division assume that all agents are available at the time of the division [Brams and Taylor, 1996]. Here, agents arrive and depart as the cake is being divided. Online cake cutting provides an abstract model for a range of practical problems besides birthday parties. Consider, for instance, allocating time on a large telescope. Astronomers will have different preferences for when to use the telescope depending on what objects are visible, the position of the sun, etc. How do we design a web-based reservation system so that astronomers can asynchronously choose observation times that is fair to all? As a second example, consider allocating space at an exhibition. Exhibitors will have different preferences for space depending on the size, location, cost, etc. How do allocate space when not all exhibitors arrive at the same time but those who have arrived want to start setting up immediately? Online cake cutting poses some interesting new challenges. On the one hand, the online aspect of such problems makes fair division more difficult than in the offline case. How can we ensure that agents do not envy cake already given to other agents? On the other hand, the online aspect of such problems may make fair division easier than in the offline case. Perhaps agents do not envy cake that has already been eaten before they arrive? R.I. Brafman, F. Roberts, and A. Tsouki`as (Eds.): ADT 2011, LNAI 6992, pp. 292–305, 2011. c Springer-Verlag Berlin Heidelberg 2011
Online Cake Cutting
293
2 Online Cake Cutting We assume that agents are risk averse. That is, they declare valuations of the cake that maximizes the minimum value of the cake that they receive, regardless of what the other agents do. This is a common assumption in cake cutting. For instance, Brams, Jones and Klamler (2006) argue: “. . . As is usual in the
Data Loading...
