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-Spec

The direct forbidden/advance statement of the market clearing price predicate: forbidden when item $j$ belongs to an inclusion-minimal overdemanded set $J$ (found by alternating-path reachability from an unmatched bidder, the standard witness for a violated Hall's condition); advance raises just that one item's price by a single unit. This genuinely uses a forbidden/advance rule, unlike the more efficient implementation below.

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-Assignment

A more efficient implementation of the same predicate that, when no perfect matching exists in the preferred-items graph, finds an inclusion-minimal overdemanded set $J$ (via the same alternating-path reachability as above) and raises every item in $J$ by one shared amount $\delta$ — the smallest gap, over bidders demanding into $J$, between that bidder's best surplus and their best surplus using an item outside $J$ — reaching the same minimum clearing price as LLP-Assignment-Spec in far fewer, larger steps. It is written as ordinary imperative code (an explicit matching loop, not a literal forbidden/advance rule), since the book presents it as the efficient procedural realization of the predicate above, not as a second forbidden/advance program.

Time complexity: $O(n^3)$ via the Hungarian / LLP fixpoint, where $n$ is the side length of the cost matrix.

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.