Disproportionate division

DOI10.1112/BLMS.12368MaRDI QIDQ5135364zbMATH OpenOpenAlexFDO

Authors Logan Crew, Bhargav P. Narayanan, Sophie Spirkl

Publication date 20 November 2020

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.07141

zbMATH Keywords

cake-cutting problem

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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 $alph{a}_1,alph{a}_2,dots,alph{a}_n$ summing to $1$? When all the agents have equal demands of $alph{a}_1=alph{a}_2=dots=alph{a}_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(nlogn)$ 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.

Recommendations

• scientific article; zbMATH DE number 21741
• Fair multi-cake cutting
• Extensions of cut-and-choose fair division
• \(N\)-person cake-cutting: there may be no perfect division

Cites work

• An Envy-Free Cake Division Protocol
• Better ways to cut a cake
• Cake-cutting with different entitlements: how many cuts are needed?
• Generalized sandwich theorems
• How to Cut a Cake Fairly
• How to Cut A Cake Fairly
• How to cut a cake fairly using a minimal number of cuts
• Sets on which several measures agree
• Simultaneous partitions of measures by \(k\)-fans
• Sur la division pragmatique

Cited in

(9)

• Picking sequences and monotonicity in weighted fair division
• Mind the gap: cake cutting with separation
• Disentangling disproportionality
• Fair multi-cake cutting
• Throw one's cake -- and eat it too
• Weighted fair division of indivisible items: a review
• Dividing a graphical cake
• Asymptotic analysis of weighted fair division
• Fairer than fair: sharp bounds for connected super-proportional cake cutting

This page was built for publication: Disproportionate division

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5135364)