Cake-cutting with different entitlements: how many cuts are needed?

DOI10.1016/J.JMAA.2019.123382MaRDI QIDQ2325916zbMATH OpenOpenAlexWikidataFDO

Authors Erel Segal-Halevi

Publication date 4 October 2019

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

connected componentsasymmetric agentsunequal sharesland divisionfair cake-cutting

Mathematics Subject Classification ID

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

Abstract: A cake has to be divided fairly among $n$ agents. When all agents have equal entitlements, it is known that such a division can be implemented with $n-1$ cuts. When agents may have different entitlements, the paper shows that at least $2n-2$ cuts may be necessary, and $O(nlog(n))$ cuts are always sufficient.

Recommendations

• How to cut a cake fairly using a minimal number of cuts
• scientific article; zbMATH DE number 21741
• scientific article; zbMATH DE number 1962847
• Approximating fair division with a limited number of cuts
• Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond

Cites work

• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 5240213 (Why is no real title available?)
• Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm
• Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
• Extensions of cut-and-choose fair division
• Game-theoretic algorithms for fair and strongly fair cake division with entitlements
• Ramsey partitions of integers and fair divisions
• Sets on which several measures agree

Cited in

(10)

• Mind the gap: cake cutting with separation
• Picking sequences and monotonicity in weighted fair division
• Efficient Fair Division with Minimal Sharing
• Fair division is hard even for amicable agents
• Disproportionate division
• Weighted fair division of indivisible items: a review
• Fair multi-cake cutting
• Keep your distance: land division with separation
• Fair cake-cutting among families
• How to divide a cake when people have different metabolism?

This page was built for publication: Cake-cutting with different entitlements: how many cuts are needed?

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