
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, \dots, α_n$ summing to $1$? When all the agents have equal demands of $α_1 = α_2 = \dots = α_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 $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.
8 pages, submitted
Computational Geometry (cs.CG), FOS: Computer and information sciences, cake-cutting problem, Resource and cost allocation (including fair division, apportionment, etc.), disproportionate division, 05D05 (Primary), 91B32 (Secondary), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, Algebraic Topology (math.AT), Mathematics - Algebraic Topology, Combinatorics (math.CO)
Computational Geometry (cs.CG), FOS: Computer and information sciences, cake-cutting problem, Resource and cost allocation (including fair division, apportionment, etc.), disproportionate division, 05D05 (Primary), 91B32 (Secondary), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, Algebraic Topology (math.AT), Mathematics - Algebraic Topology, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
