The undercut procedure is a procedure for fair item assignment between two people. It provably finds a complete envy-free item assignment whenever such assignment exists. It was presented by Brams and Kilgour and Klamler and simplified and extended by Aziz.
Contents
Assumptions
The undercut procedure requires only the following weak assumptions on the people:
Main idea
The undercut procedure can be seen as a generalization of the divide and choose protocol from a divisible resource to a resource with indivisibilities. The divide-and-choose protocol requires one person to cut the resource to two equal pieces. But, if the resource contains with indivisibilities, it may be impossible to make an exactly-equal cut. Accordingly, the undercut procedure works with almost-equal-cuts. An almost-equal-cut of a person is a partition of the set of items to two disjoint subsets (X,Y) such that:
Procedure
Each person reports all his almost-equal-cuts. There are two cases:
To prove the correctness of the procedure, it is sufficient to prove that in the Hard case, an envy-free allocation does not exist. Indeed, suppose there exists an envy-free allocation (X,Y). Since we are in the Hard case, (X,Y) is not an exactly-equal cut. So one person (e.g. George) strictly prefers Y to X, while the other person (Alice) weakly prefers X to Y. If (X,Y) is not an almost-equal-cut for Alice, then we move some items from X to Y, until we get a partition (X',Y') that is an almost-equal-cut for Alice. Alice still weakly prefers X' to Y'. By the monotonicity assumption, George still strictly prefers Y' to X'. This means that (X',Y') is not an almost-equal-cut for George. But in the Hard case, both agents have the same set of almost-equal-cuts - a contradiction.
Run-time complexity
In the worst case, the agents may have to evaluate all possible bundles, so the run-time might be exponential in the number of items.
This is not surprising, since the undercut procedure can be used to solve the partition problem: assume both agents have identical and additive valuations and run the undercut procedure; if it finds an envy-free allocation, then this allocation represents an equal partition. Since the partition problem is NP-complete, it probably cannot be solved by a polynomial-time algorithm.
Unequal entitlements
The undercut procedure can also work when the agents have unequal entitlements. Suppose each agent
Generation phase
In the original publication, the undercut procedure is preceded by the following generation phase:
The undercut procedure described above is then executed only on the contested pile.
This phase may make the division procedure more efficient: the contested pile may be smaller than the original set of items, so it may be easier to calculate and report the almost-equal-cuts.
However, the generation phase has several disadvantages:
- It might make the procedure miss a possible envy-free allocation. For example, suppose there are four items and their valuations are as in the adjacent table. The allocation that gives {w,z} to Alice and {x,y} to George is envy-free. Indeed, it can be found by the bare undercut procedure, since the partition ({w,z}, {x,y}) is an almost-equal-cut for Alice but not for George, and George would accept this partition. But with the generation phase, initially Alice gets w and George gets x and the other items {y,z} are put in the contested pile, and there is no envy-free allocation of the contested pile, so the procedure fails.
- It requires the people to select their "best item" without knowing what other items they are going to receive. This relies on an assumption that the items are independent goods. Alternatively, it relies on a responsiveness assumption: if, in a bundle, an item is replaced by a better item, then the resulting bundle is better (it is closely related to weakly additive preferences).
- It does not work when the agents have unequal claims.
- It relies on sequential allocation, which is susceptible to strategic manipulation.