An algorithm for super envy-free cake division

DOI10.1006/JMAA.1999.6581MaRDI QIDQ1961037zbMATH OpenOpenAlexFDO

Authors William A. Webb

Publication date 14 November 2000

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

Full work available at URL https://doi.org/10.1006/jmaa.1999.6581

zbMATH Keywords

cake divisionenvy-free partitionfair divisionnonatomic probability measures

Mathematics Subject Classification ID

Partitions of sets (05A18) Vector-valued set functions, measures and integrals (28B05) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Review text

Let \(\mu_1,\dots,\mu_n\) be nonatomic probability measures on a set \(X\). A partition of \(X\) into subsets \(X_1,\dots,\) \(X_n\) is called super envy-free if \(\mu_i(X_i)>1/n\) for each \(i\) and \(\mu_i(X_j)<1/n\) whenever \(j\neq i\). \textit{J. B. Barbanel} showed [J. Math. Anal. Appl. 197, No. 1, 54-60 (1996; Zbl 0857.90019)] that a super envy-free allocation exists if and only if the measures are linearly independent. This paper gives a finite algorithm for finding a super-envy-free allocation if it exists. The number of steps required depends on the measures. As initially presented, the algorithm assumes the availability of a ``witness to the independence of the measures -- that is, sets \(A_1,\dots,A_n\) that make \((\mu_i(A_j))\) non-singular. With additional assumptions, the required witness can be found as part of the finite algorithm. This paper is the authority for section 10.4 in the book ``Cake-cutting algorithms. Be fair if you can, by \textit{J. Robertson} and \textit{W. Webb} [A. K. Peters, Natick, Massachusetts (1998)].

Recommendations

• Super envy-free cake division and independence of measures
• scientific article; zbMATH DE number 1409181
• How to cut a cake with a Gram matrix
• An Envy-Free Cake Division Protocol
• On finding an envy-free Pareto-optimal division

Cites work

• A moving-knife solution to the four-person envy-free cake-division problem
• A note on cake cutting
• A note on the cake-division problem
• A Note on the Fair Division Problem
• An Envy-Free Cake Division Protocol
• Approximating fair division with a limited number of cuts
• Dividing a cake fairly
• Extensions of cut-and-choose fair division
• Game-theoretic algorithms for fair and strongly fair cake division with entitlements
• How to Cut a Cake Fairly
• How to Cut A Cake Fairly
• How to cut a cake fairly using a minimal number of cuts
• scientific article; zbMATH DE number 21741 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 1409181 (Why is no real title available?)
• Old and new moving-knife schemes
• On envy-free cake division
• On the possibilities for partitioning a cake
• Preference Relations and Measures in the Context of Fair Division
• Sets on which several measures agree
• Super envy-free cake division and independence of measures
• Sur la division pragmatique

Cited in

(8)

• A comparison of formulations and solution methods for the minimum-envy location problem
• How to cut a cake with a Gram matrix
• Super envy-free cake division and independence of measures
• Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm
• Meta-Envy-Free Cake-Cutting Protocols
• Envy-free division of discrete cakes
• Fairer than fair: sharp bounds for connected super-proportional cake cutting
• Envy-free cake cutting: a polynomial number of queries with high probability

This page was built for publication: An algorithm for super envy-free cake division

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