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 [1] and simplified and extended by Aziz. [2]
The undercut procedure requires only the following weak assumptions on the people:
It is not assumed that agents have responsive preferences.
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:
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.
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. [2] Suppose each agent is entitled to a fraction of the items, with being the other agent. Then, the definition of an almost-equal-cut (for agent ) should be changed as follows:
In the original publication, [1] 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.
Alice | George | |
---|---|---|
w | 9 | 1 |
x | 8 | 4 |
y | 7 | 3 |
z | 6 | 2 |
However, the generation phase has several disadvantages: [2]
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 [1] and simplified and extended by Aziz. [2]
The undercut procedure requires only the following weak assumptions on the people:
It is not assumed that agents have responsive preferences.
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:
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.
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. [2] Suppose each agent is entitled to a fraction of the items, with being the other agent. Then, the definition of an almost-equal-cut (for agent ) should be changed as follows:
In the original publication, [1] 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.
Alice | George | |
---|---|---|
w | 9 | 1 |
x | 8 | 4 |
y | 7 | 3 |
z | 6 | 2 |
However, the generation phase has several disadvantages: [2]