2017/03/27 by Erel Segal-Halevi, Segal-Halevi, Erel, Balázs R. Sziklai +2 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic and Environmental Valuation #FOS: Computer and information sciences #Game Theory and Voting Systems #cs.GT
paper · pdf · doi:10.48550/arxiv.1703.08928
Submitted version. arXiv admin note: substantial text overlap with arXiv:1510.05229
openalex publication_date 2017/03/27 · arxiv created 2017/06/01 · arxiv updated 2017/06/05 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
In the classic cake-cutting problem (Steinhaus, 1948), a heterogeneous resource has to be divided among n agents with different valuations in a proportional way --- giving each agent a piece with a value of at least 1/n of the total. In many applications, such as dividing a land-estate or a time-interval, it is also important that the pieces are connected. We propose two additional requirements: resource-monotonicity (RM) and population-monotonicity (PM). When either the cake or the set of agents changes and the cake is re-divided using the same rule, the utility of all remaining agents must change in the same direction. Classic cake-cutting protocols are neither RM nor PM. Moreover, we prove that no Pareto-optimal proportional division rule can be either RM or PM. Motivated by this negative result, we search for division rules that are weakly-Pareto-optimal --- no other division is strictly better for all agents. We present two such rules. The relative-equitable rule, which assigns the maximum possible relative value equal for all agents, is proportional and PM. The so-called rightmost-mark rule, which is an improved version of the Cut and Choose protocol, is proportional and RM for two agents.