A price for every person and task

Finding the cheapest assignment of $n$ people to $n$ tasks by comparing every possibility means comparing $n!$ of them, which is impossible past about fifteen people. Every practical method avoids the comparison, and the interesting question is not how it searches but how it knows when to stop.

The answer is that a cheapest assignment comes with a certificate, and the certificate is a list of $2n$ numbers.

The certificate #

Attach a number $u_i$ to each person and $v_j$ to each task, subject to one rule:

$$u_i + v_j \le c_{ij} \quad \text{for every pair}.$$

Read the numbers as prices: $u_i$ is what person $i$ is paid and $v_j$ what task $j$ is worth, and the rule says no pair is priced above what it actually costs. Nothing yet says the numbers are useful, or that any interesting ones exist; the rule is a constraint and the next paragraph is what makes satisfying it worth anything.

Now the observation that does everything. Take any assignment $\sigma$. Its cost is $\sum_i c_{i\sigma(i)}$, and since each term is at least $u_i + v_{\sigma(i)}$,

$$\sum_i c_{i\sigma(i)} \ \ge\ \sum_i u_i + \sum_i v_{\sigma(i)} \ =\ \sum_i u_i + \sum_j v_j.$$

The right-hand side does not depend on $\sigma$ at all — every assignment uses every task once, so the $v$ terms are the same sum however they are permuted.

So the total of the prices is a lower bound on every assignment’s cost. And if some assignment’s cost equals that total, no assignment can be cheaper, and the search is over.

Why the bound is achievable #

A lower bound is only useful if it is tight, and here it always is. That is the duality theorem for this problem: the largest total of feasible prices equals the smallest cost of an assignment.

The reason is the previous rung. The assignment problem is a linear program whose corners are whole; linear programs have duals; and linear programming duality says the optimum of a program equals the optimum of its dual, with no gap. The dual of the assignment problem is precisely “maximise $\sum u_i + \sum v_j$ subject to $u_i + v_j \le c_{ij}$”.

So the certificate exists because the relaxation is exact, and the relaxation is exact because of Birkhoff. The two rungs are one argument.

Complementary slackness, which says where the answer is #

Duality gives more than a number. If an assignment and a set of prices have equal totals, then every inequality used by the assignment must be tight:

$$u_i + v_{\sigma(i)} = c_{i\sigma(i)} \quad \text{for every } i.$$

That follows immediately — the chain of inequalities above is an equality overall, so each of its terms is an equality.

That is complementary slackness, and it turns the certificate into a search rule. Given a set of prices, only the tight pairs can be used by an optimal assignment, so the search is restricted to the graph of pairs where $u_i + v_j = c_{ij}$. If that graph has a perfect matching, the matching is optimal and the prices prove it.

If it does not, the prices are not yet the best ones, and the failure says how to improve them: Hall’s theorem identifies a set of people whose tight tasks are too few, and raising their prices — and lowering the corresponding tasks’ — adds a tight pair without breaking any inequality.

That is the Hungarian algorithm. Alternate between finding a matching in the tight graph and adjusting prices when it fails, and both the assignment and its certificate are produced together.

Its cost is worth a sentence. Each price adjustment adds at least one tight pair, the matching grows by at most one person at a time, and the whole thing terminates in $O(n^3)$ operations — against the $n!$ of enumeration, which at twenty people is the difference between eight thousand operations and a number with nineteen digits. The algorithm’s speed comes from never enumerating anything, and the certificate is why it does not have to.

The chain of reasoning is worth setting out in one place because it is easy to lose. Birkhoff says the relaxation’s corners are whole. Therefore the relaxation’s optimum is a whole assignment, so the relaxation and the original problem have the same answer. Linear programming duality says the relaxation’s optimum equals its dual’s. Therefore the dual’s optimum equals the cheapest assignment’s cost, which is the existence of a tight certificate.

Every step is standard and the composition is what makes the assignment problem the textbook case. Take away the integrality and the last equality still holds, but it is about a fractional object; take away the duality and the certificate has nothing to be tight against.

What a certificate is worth #

Three things, and only the first is about speed.

Checking is cheaper than solving. Verifying a certificate is $n^2$ comparisons and two sums; producing it is $n^3$ work. So a result can be handed to somebody who does not trust the computation and verified independently, which is a completely different kind of guarantee from “the program said so”. The gap widens with the problem: at a thousand people, verification is a million comparisons and the search it replaces is a number with two and a half thousand digits.

And it is robust to a bug. A program that finds the wrong assignment usually cannot produce prices that certify it, because the certificate has to satisfy $n^2$ inequalities and an equality. So the certificate is a self-check on the implementation, and checking it is standard practice in optimisation software.

It also prices the constraints. The dual variables answer a question the primal does not: how much would the answer improve if this person could take one more task, or if this task’s cost fell? That sensitivity information is often what the answer is wanted for — a planner usually cares less about the optimal schedule than about which resource is worth buying more of — and it arrives as a by-product of computing the schedule.

The economic reading, which is not a metaphor #

The prices have an interpretation that is exact rather than suggestive.

Suppose the tasks are auctioned and each person bids. Set $v_j$ as the price of task $j$ and let each person take the task maximising their surplus $c_{ij} - v_j$ — or, in the minimisation reading, the task whose cost less price is smallest. If every task is taken by exactly one person, the market clears.

A market-clearing price vector is exactly a set of dual variables, and the resulting allocation is exactly an optimal assignment. That is the content of the Shapley–Shubik assignment market, and it is why the same mathematics appears in matching markets, in auction design, and in the pricing of advertising slots.

The equivalence has a consequence worth stating on its own. Because the optimal assignment maximises total value and the prices clear the market, a competitive equilibrium in this setting is efficient — which is the first welfare theorem, holding here not as an idealisation but as an arithmetic identity, and provable in the five lines above. That is unusually concrete for an economic statement, and it is available because the underlying problem is a linear program with whole corners rather than because of any assumption about behaviour.

The connection runs both ways. The Hungarian algorithm’s price adjustments are an auction: raise the price of over-demanded tasks until demand spreads out. An implementation phrased that way — Bertsekas’s auction algorithm — is a genuinely different algorithm with the same certificate, and it parallelises where the Hungarian method does not.

Where it came from, and the name #

The algorithm is due to Harold Kuhn in 1955, and he named it after two Hungarian mathematicians — Kőnig and Egerváry — whose earlier theorems it rests on, rather than after himself.

Kőnig’s theorem, from 1931, says that in a bipartite graph the largest matching equals the smallest set of vertices covering all edges. Egerváry generalised it to weighted graphs in the same year, in Hungarian, in a paper Kuhn read in translation. Kuhn’s contribution was to turn Egerváry’s proof into a procedure.

The naming is worth noting because it is the opposite of the usual pattern. Most algorithms carry the name of whoever implemented them; this one carries the name of the country whose mathematicians proved the theorem it implements, chosen deliberately by the implementer.

There is a postscript that arrived much later. In 2006 it emerged that Jacobi had described essentially the same method in a posthumous paper of 1890, written in Latin, more than sixty years before Kuhn. The algorithm was published, forgotten, and rediscovered, which is a common enough fate and unusually well documented here.

What it costs #

The certificate is not unique. Many price vectors certify the same assignment, and which one an algorithm produces is an artefact of the algorithm. So a claim about “the” shadow price of a constraint is only well posed when the dual optimum is unique, which it need not be.

Degeneracy is where the trouble is. When several assignments are cheapest, the tight graph has several matchings and the algorithm’s choice among them is arbitrary. That is harmless for the cost and matters when the assignment is used for something else — who gets which task is not a matter of indifference to the people involved, even when the total is the same — which is the next rung’s subject.

Finding the certificate needs the whole table. The prices are global objects: every one of them depends on every cost, so a single cost changing can change all $2n$ prices. That makes incremental re-solving awkward, and it is why systems that re-optimise continuously use the auction formulation, whose price adjustments are local.

And it does not survive extra constraints. Adding a requirement that two particular people not both be used breaks the structure entirely: the relaxation stops having whole corners, the duality gap opens, and the certificate no longer proves anything.

A worked check #

The certificate is small enough to verify by hand once, which is the whole point of it, so it is worth doing.

Take the hero figure’s table. The assignment marked uses one cell in each row and column, and its cost is the sum of those four numbers. Beside each row is a price and beneath each column another.

Check one: for every one of the sixteen cells, the row price plus the column price is at most the cell’s cost. Sixteen comparisons.

Check two: for the four cells the assignment uses, the two prices add to exactly the cost. Four comparisons.

Check three: the eight prices add to the assignment’s cost. Two sums.

That is twenty-two arithmetic operations, and having done them a reader knows — not on anybody’s authority — that no other assignment of the twenty-four possible is cheaper. The alternative check is to add up twenty-four assignments, and at size ten it would be three and a half million against thirty operations.

The asymmetry is the reason certificates matter, and it grows: verification is quadratic and enumeration is factorial.

What the pictures cannot show #

The prices are found by search here and by an algorithm in practice. The figure looks over small whole-number price vectors until it finds one whose total matches the optimum, which is exact and slow. The Hungarian algorithm constructs them in $n^3$ steps, and its construction is a sequence of adjustments no single table displays.

Nothing shows that the prices are the best possible. The certificate proves the assignment is optimal; that the prices are themselves an optimal solution of the dual is the same statement read the other way, and neither figure indicates that a larger total of prices is impossible. The two optimality claims are one fact and the picture carries only one of them.

The tight graph is not drawn. Each cell carries its cost and the sum of its two prices, so a reader can find the tight cells by comparing two numbers — and the graph they form, which is the object the algorithm searches, is not drawn as a graph anywhere.

The search for prices is not the algorithm and is drawn as though it were. The figure reports a price vector without indicating how it was found, and a reader could reasonably infer that finding one is easy. It is easy for the figure because the numbers are small; in general it is the whole computation.

And the lower bound applies to assignments that are not shown. The whole point of the certificate is that it bounds the cost of every one of the $n!$ possibilities without examining them. A figure can show the one that is optimal; the ones it is being compared against are exactly what nobody looks at.

Where the ladder goes next #

The next rung takes the non-uniqueness seriously: one table of shares can be written as two different lotteries, so a specification in terms of averages does not determine a procedure.

Named here as a debt: the auction algorithm, described above in a sentence, which is a genuinely different method producing the same certificate and is the one used when the computation has to be spread over many machines.

Also unwritten: the assignment game’s core, which is the set of price vectors on which no coalition can do better by breaking away, and which coincides with the set of optimal dual solutions. It is the same object this collection studies for other games arriving as a by-product of an algorithm.

Sideways, the failure that tells the prices how to move is Hall’s condition, the flow reading of the same problem is the max-flow min-cut theorem, and the integrality that makes the duality exact is the previous rung.

The same idea in three other places #

The pattern — an answer plus a checkable proof of optimality — is not particular to assignment, and recognising it elsewhere is the point of learning it here.

Max-flow and min-cut. A flow’s value is at most any cut’s capacity, by the same one-line inequality; a maximum flow comes with a cut of equal capacity, and the cut is its certificate. The bottleneck is the whole story is that pair.

Shortest paths. Dijkstra’s algorithm produces distances that satisfy the triangle inequality along every edge, and those distances certify that no shorter path exists — checkable by examining each edge once.

And primality. A number’s primality has a short certificate too, though a very different one: a witness that the multiplicative group has the right order. Nothing about the shape of the problem suggests it, and its existence is a theorem of Pratt’s.

What the three have in common is a pair of problems that bound each other. Wherever such a pair exists, an answer to one and an answer to the other with matching values prove each other, and the algorithm’s job becomes producing both at once rather than searching until it runs out of candidates.

The pattern’s limit is worth stating. For problems with no such pair — the travelling salesman among them — a tour can be exhibited and its optimality cannot be certified compactly, and that difficulty is exactly what the complexity classes are about.

What is worth carrying away #

The valuable output of an optimisation is not the answer but the proof that comes with it.

A cheapest assignment on its own is a claim. A cheapest assignment together with prices is a claim and its proof, checkable in $n^2$ comparisons by somebody who does not trust the program, the machine or the method. The second is a different kind of object, and producing it costs nothing extra because the algorithm builds it on the way.

The habit worth taking is to ask what a computation’s certificate would look like. If there is one, a correct answer can be recognised without being recomputed; if there is not, the only check on the answer is the program that produced it.