2018/12/19 by Erel Segal-Halevi, Segal-Halevi, Erel
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1812.08150
openalex publication_date 2018/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the classic problem of fair cake-cutting, a single interval ("cake") has to be divided among n agents with different value measures, giving each agent a single sub-interval with a value of at least 1/n of the total. This paper studies a generalization in which the cake is made of m disjoint intervals, and each agent should get at most k sub-intervals. The paper presents a polynomial-time algorithm that guarantees to each agent at least min(1/n, k/(m+n-1)) of the total value, and shows that this is the largest fraction that can be guaranteed. The algorithm simultaneously guarantees to each agent at least 1/n of the value that the agent can get without partners to share with. The main technical tool is envy-free matching in a bipartite graph. Some of the results remain valid even with additional fairness constraints such as envy-freeness. Besides the natural application of the algorithm to simultaneous division of multiple land-estates, the paper shows an application to a geometric problem -- fair division of a two-dimensional land estate shaped as a rectilinear polygon, where each agent should receive a rectangular piece.