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

DOI10.1016/J.JMAA.2019.123382zbMATH Open1426.91149arXiv1803.05470OpenAlexW2789960275WikidataQ127406512 ScholiaQ127406512MaRDI QIDQ2325916FDOQ2325916

Authors: Erel Segal-Halevi 

Publication date: 4 October 2019

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

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.

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

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

zbMATH Keywords

connected componentsasymmetric agentsunequal sharesland divisionfair cake-cutting

Mathematics Subject Classification ID

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

Cites Work

• Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
• Title not available (Why is that?)
• Title not available (Why is that?)
• Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm
• Sets on which several measures agree
• Title not available (Why is that?)
• Ramsey partitions of integers and fair divisions
• Extensions of cut-and-choose fair division
• Game-theoretic algorithms for fair and strongly fair cake division with entitlements

Cited In (10)

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

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)