Edmonds–Pruhs protocol

Edmonds–Pruhs protocol is a protocol for fair cake-cutting.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Edmonds–Pruhs protocol is a protocol for fair cake-cutting. Its goal is to create a partially proportional division of a heterogeneous resource among n people, such that each person receives a subset of the cake which that person values as at least 1/an of the total, where a\geq 10 is some sufficiently large constant.

It is a randomized algorithm whose running time is O(n) with probability close to 1. The protocol was developed by Jeff Edmonds and Kirk Pruhs, who later improved it in joint work with Jaisingh Solanki. \sum_k \frac{(2dn)!}{(2dn-k)!(an)^k} = O\left(\frac{1}{a^2}\right) By selecting d=1 and a sufficiently large, it is possible to make this probability as small as we want.

This is true even if we omit the semi-final selection phase (#3) and just take all quarter-final pieces as semi-final. Note that this case is analogous to the balls into bins model. It proves that, if d bins are picked randomly for each ball, then it is possible to select one bin for each ball such that the bins are all distinct (the maximum load is 1).

In the general cake model, where the value functions are different, the probabilities of the edges in the implication graph are dependent. but thanks to the semi-final selection phase, we can prove that the probability that the implication graph contains a pair path of length at least 3 is at most \frac{32 d^5}{a^2\cdot(a - 4 d^2)} . It remains to handle pair paths of length 2.

Unfortunately the probability of having such pair paths in the implication graph is not negligible. However, with high probability it is possible to partition the partners to two groups, such that in each group there is no pair path of length 2. Hence, we can run the final-piece-selection algorithm twice: once for each group.

Intersection can occur only between final pieces of different groups; hence the overlap in each point of the cake is at most 2. The probability that such a 2-partition is not possible is at most \frac{16 d^3}{a^3}+\frac{8d^2}{a^2} . By summing the above two expressions and setting d = 2, we get that the probability of failure is still O\left(\frac{1}{a^2}\right) .

Recall that a is the proportionality ratio - the more value we want to guarantee each partner, the more likely it is that the division will fail and we will have to start over at step #1. The same algorithm works also when the cuts are approximate, i.e., the partners do not know to mark pieces with exactly the same value; they might mark a piece with a value of p percent above or below the required value, where the exact error is picked at random.

The probability of removing a specific partner in each run is O\left(\frac{1}{n}\right) . The probability of removing a specific partner in both runs is O\left(\frac{1}{n^2}\right) . Hence the probability of failure is O\left(\frac{n}{n^2}\right)=O\left(\frac{1}{n}\right) , which goes to 0 when n increases, even when the partial proportionality ratio a is kept constant.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1323901672 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.