Chapter 17. The Assignment Problem

Market clearing prices, the Hungarian method, and the ascending-price LLP algorithm.

This page: LLP forms. View classical forms »

The assignment problem

Given $n$ bidders and $n$ items with valuations $v[b, i]$, find an assignment (perfect matching) and a price vector $C[1..n]$ such that every bidder is assigned to a most-preferred item at the given prices. Equivalently, find the minimum market clearing price vector: the smallest prices such that the preferred-items graph (edges to items maximizing $v[b, i] - C[i]$) contains a perfect matching.

Overdemanded sets

A set $J$ of items is overdemanded if the set of bidders who prefer items in $J$ is strictly larger than $|J|$. By Hall's theorem, a perfect matching exists iff no overdemanded set exists. The LLP formulation uses overdemand as the forbidden predicate.

LLP-Assignment

The forbidden/advance statement of the market clearing price predicate. A set $J$ of items is forbidden when it is inclusion-minimal with $|O_G(J)| > |J|$ — an overdemanded set, found by alternating-path reachability from a bidder left unmatched by a maximum matching of the tight-edge graph, the standard witness for a violated Hall's condition. The advance then raises every item of $J$ by one shared amount $\delta$: the smallest gap, over the bidders demanding into $J$, between a bidder's best surplus and their best surplus using an item outside $J$. That single batched raise has the same effect as the whole run of unit raises it replaces, because the demand graph does not change until one of those bidders first acquires a demanded item outside $J$.

No index is forbidden exactly when no overdemanded set remains, which by Hall's theorem is exactly when the demand graph admits a perfect matching. The matching $M$ is therefore read off that graph once the fixpoint is reached, rather than tested for on every iteration.

Assumption: the number of bidders equals the number of items. With more bidders than items no perfect matching can exist, so some set stays overdemanded however high its prices go and the fixpoint is never reached — the program does not terminate. The program does not check this; supply a square valuation matrix.

Time complexity: $O(n^2)$ advances in the worst case (each item's price rises at most $n$ times), each requiring an $O(nm)$ matching pass to find the current overdemanded set.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[j]$ represents and the negation of the forbidden clause from the matching .llp source.