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.
Assumptions
The undercut procedure requires only the following weak assumptions on the people:
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 such that:
If any single item is moved from X to Y, then the person strictly prefers Y to X.
Procedure
Each person reports all his almost-equal-cuts. There are two cases:
Case 1: the reports are different, e.g., there is a partition that is an almost-equal-cut for Alice but not for George. Then, this partition is presented to George. George can either accept or reject it:
* George accepts the partition if he prefers Y to X. Then Alice receives X and George receives Y and the resulting allocation is envy-free.
* George rejects the partition if he prefers X to Y. By assumption, is not an almost-equal-cut for George. Therefore, there exists an item x in X such that George prefers to. George reports ; we say that George undercuts X. Since is an almost-equal-cut for Alice, Alice prefers to. Then George receives and Alice receives and the resulting allocation is envy-free.
Case 2: the reports are identical, i.e., Alice and George have exactly the same set of almost-equal-cuts. Then, the procedure asks them whether one of their almost-equal-cuts is an exactly-equal-cut. By the strict-monotonicity assumption, is an exactly-equal-cut, if-and-only-if both and are almost-equal-cuts. Therefore, in Case 2, Alice and George have the same set of exactly-equal-cuts. There are two sub-cases:
* Easy case: there exists an exactly-equal cut. Then one person receives X and the other receives Y and the division is envy-free.
* Hard case: there is no exactly-equal cut. Then the procedure returns and reports that "an envy-free allocation does not exist".
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. Since we are in the Hard case, is not an exactly-equal cut. So one person strictly prefers Y to X, while the other person weakly prefers X to Y. If is not an almost-equal-cut for Alice, then we move some items from X to Y, until we get a partition 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 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.
The undercut procedure can also work when the agents have unequal entitlements. Suppose each agent is entitled to a fraction of the items. Then, the definition of an almost-equal-cut should be changed as follows:
, and
For all x in X, the
Generation phase
In the original publication, the undercut procedure is preceded by the following generation phase:
While there are items on the table:
* Each person reports his/her best item.
** If the reports are different, then each person receives his/her best item.
** If the reports are identical, then the best item is put in a contested pile.
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.
Alice
George
w
9
1
x
8
4
y
7
3
z
6
2
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 to Alice and to George is envy-free. Indeed, it can be found by the bare undercut procedure, since the partition 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 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 does not work when the agents have unequal claims.
It relies on sequential allocation, which is susceptible to strategic manipulation.
