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:
Each person has a weak preference relation on subsets of items. Each preference relation is strictly monotonic: for every set X {\displaystyle X} and item y ∉ X {\displaystyle y\notin X} , the person strictly prefers X ∪ y {\displaystyle X\cup y} to X {\displaystyle X} . It is not assumed that agents have responsive preferences.
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:
The person weakly prefers X to Y; If any single item is moved from X to Y, then the person strictly prefers Y to X (i.e., for all x in X, the person prefers Y ∪ x {\displaystyle Y\cup x} to X ∖ x {\displaystyle X\setminus 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 (X,Y) 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, (X,Y) is not an almost-equal-cut for George. Therefore, there exists an item x in X such that George prefers X ∖ x {\displaystyle X\setminus x} to Y ∪ x {\displaystyle Y\cup x} . George reports X ∖ x {\displaystyle X\setminus x} ; we say that George undercuts X. Since (X,Y) is an almost-equal-cut for Alice, Alice prefers Y ∪ x {\displaystyle Y\cup x} to X ∖ x {\displaystyle X\setminus x} . Then George receives X ∖ x {\displaystyle X\setminus x} and Alice receives Y ∪ x {\displaystyle Y\cup x} 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, (X,Y) is an exactly-equal-cut, if-and-only-if both (X,Y) and (Y,X) 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 (X,Y). Then one person (no matter who) 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 (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 i {\displaystyle i} is entitled to a fraction c i {\displaystyle c_{i}} of the items, with − i {\displaystyle -i} being the other agent. Then, the definition of an almost-equal-cut (for agent i {\displaystyle i} ) should be changed as follows:
… excerpt ends here. Continue reading the full article.
