





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。