2019/09/16 by Logan Crew, Crew, Logan, Bhargav Narayanan +3 · 1 citation
Computer Science · Mathematics · #05D05 (Primary) #91B32 (Secondary) #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.AT #math.CO #msc:05D05 #msc:91B32
paper · pdf · doi:10.48550/arxiv.1909.07141
8 pages, submitted
arxiv created 2019/09/16 · arxiv updated 2019/09/17
We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here [0,1], among n agents with different demands α1, α2, …, αn summing to 1? When all the agents have equal demands of α1 = α2 = … = αn = 1/n, it is well-known that there exists a fair division with n-1 cuts, and this is optimal. For arbitrary demands on the other hand, folklore arguments from algebraic topology show that O(nlog n) cuts suffice, and this has been the state of the art for decades. Here, we improve the state of affairs in two ways: we prove that disproportionate division may always be achieved with 3n-4 cuts, and give an effective combinatorial procedure to construct such a division. We also offer a topological conjecture that implies that 2n-2 cuts suffice in general, which would be optimal.