Premium
Disproportionate division
Author(s) -
Crew Logan,
Narayanan Bhargav,
Spirkl Sophie
Publication year - 2020
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms.12368
Subject(s) - mathematics , division (mathematics) , conjecture , state (computer science) , fair division , construct (python library) , algebraic number , folklore , topology (electrical circuits) , combinatorics , discrete mathematics , algorithm , mathematical economics , arithmetic , computer science , mathematical analysis , art , literature , programming language
Abstract We study the disproportionate version of the classical cake‐cutting problem: how efficiently can we divide a cake, here [0,1], among n ⩾ 2 agents with different demandsα 1 , α 2 , ⋯ , α nsumming 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 ( n log 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 3 n − 4 cuts, and also give an effective algorithm to construct such a division. We additionally offer a topological conjecture that implies that 2 n − 2 cuts suffice in general, which would be optimal.