Near Exact and Envy Free Cake Division

A division of a cake \(X = X_1 \cup \cdots \cup X_n\) among \(n\) players with associated probability measures \(\mu_1, \ldots, \mu_n\) on \(X\) is said to be:

(a) exact in the ratios of \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_j)} { \mu_1(X)} = \alpha_i / (\alpha_1 + \cdots + \alpha_n)\)

(b) \(\epsilon\)-near exact in the ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(|\frac{\mu_i(X_i)}{\mu_1(X_1)} + \cdots +\frac {\alpha_j}{\alpha_1 + \cdots + \alpha_n}| < \epsilon\)

(c) envy free in ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_i)}{\mu_i(X_j)} \geq \frac{\alpha_i}{\alpha_j}\).

A moving knife exact division is described for two players and it is shown there can be no finite exact algorithm for \(n \geq 2\) players. A bounded finite \(\epsilon\)-near exact algorithm is given which is used to produce a finite envy free, \(\epsilon\)-near exact algorithm.