An algorithm for super envy-free cake division
type: Item
instance of: scholarly article
title: An algorithm for super envy-free cake division
zbMATH Open document ID: 0948.28006
author: William A. Webb
published in: Journal of Mathematical Analysis and Applications
publication date: 2000-11-14T00:00:00Z
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)].
Mathematics Subject Classification ID: 28B05
Mathematics Subject Classification ID: 91B32
Mathematics Subject Classification ID: 05A18
zbMATH DE Number: 1389242
zbMATH Keywords: cake division
zbMATH Keywords: fair division
zbMATH Keywords: envy-free partition
zbMATH Keywords: nonatomic probability measures
MaRDI profile type: Publication
full work available at URL: jmaa.1999.6581
OpenAlex ID: W1989218403
cites work: Game-theoretic algorithms for fair and strongly fair cake division with entitlements
cites work: Super envy-free cake division and independence of measures
cites work: On the possibilities for partitioning a cake
cites work: Preference Relations and Measures in the Context of Fair Division
cites work: An Envy-Free Cake Division Protocol
cites work: On envy-free cake division
cites work: Q4338900
cites work: Old and new moving-knife schemes
cites work: A moving-knife solution to the four-person envy-free cake-division problem
cites work: How to Cut A Cake Fairly
cites work: A note on cake cutting
cites work: A Note on the Fair Division Problem
cites work: Q3981356
cites work: Approximating fair division with a limited number of cuts
cites work: Extensions of cut-and-choose fair division
cites work: Q4940018
cites work: Sur la division pragmatique
cites work: How to Cut a Cake Fairly
cites work: Sets on which several measures agree
cites work: How to cut a cake fairly using a minimal number of cuts
cites work: Dividing a cake fairly
cites work: A note on the cake-division problem
DOI: 10.1006/JMAA.1999.6581
description: scientific article; zbMATH DE number 1389242