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
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.
A proportional division of a cake can be achieved using the recursive halving algorithm in time O(n log n).
Several hardness results show that this run-time is optimal under a wide variety of assumptions.
In particular, recursive halving is the fastest possible algorithm for achieving full proportionality when the pieces must be contiguous, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even when the pieces are allowed to be disconnected.
The Edmonds–Pruhs protocol aims to provide an algorithm with run-time O(n) for this case.
The general scheme is as follows:[1] The algorithm guarantees that, with high probability, each partner receives at least half of one of his candidate pieces, which implies (if the values are additive) a value of at least 1/2an.
There are O(n) candidate pieces and O(n) additional divisions in step #5, each of which takes O(1) time.
In the latter case we just pick another piece of one of the remaining partners and continue.
If the implication graph contains no pair paths, then the selection algorithm just described returns a collection of n non-overlapping final pieces and we are done.
Now it remains to calculate the probability that the implication graph contains a pair path.
First, consider the special case in which all partners have the same value function (and hence the same collection of candidate pieces).
Note that this case is analogous to the balls into bins model.
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
Intersection can occur only between final pieces of different groups; hence the overlap in each point of the cake is at most 2.
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.
This model has found wide applications in areas such as load balancing.
Hence, it is reasonable that the cake model and the Edmonds–Pruhs protocol should have interesting applications in settings involving load balancing on unrelated machines.