An algorithm for super envy-free cake division (Q1961037)

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)].