Prices the bidders raise

A price for every person and task proved that an assignment is the best one without comparing it to any other. Put a number on each person and each task so that no pair’s two numbers add to more than what the pair is worth; if the pairs actually used add up exactly, nothing can beat them. The numbers are a certificate, and the certificate is short.

That essay found its prices by searching, and it named, in a sentence, a different way of finding them — the way a market finds prices, by letting people bid. This essay follows that sentence to the end. The method is Dimitri Bertsekas’s auction algorithm of 1979, and it is interesting less as a procedure than as a demonstration: a certificate of optimality can be produced by nothing more than self-interested bidding, provided each bid is made slightly more aggressive than self-interest alone would make it.

The setting is turned round from costs to values, because bidding is about wanting things. Each of $n$ people — call them bidders — puts a whole-number value $a_{ij}$ on each of $n$ objects, and the aim is an assignment of one object to each bidder that makes the total value as large as possible. The prices start at zero.

One bid, spelled out #

A bid is a small, local computation that one bidder can make alone. Take bidder A at the start. Prices are all zero, so the net value of each object — its value to A minus its price — is just A’s valuation: $8, 2, 6, 5$. The best is object 1, at $8$. The second best is object 3, at $6$.

A takes object 1 and raises its price. By how much? By the amount that would make A exactly indifferent between object 1 and object 3 — the margin, $8 - 6 = 2$ — plus a small extra increment $\varepsilon$. Here $\varepsilon = 1/5$, so the price of object 1 rises by $11/5$. At the new price, object 1 is worth $8 - 11/5 = 29/5$ to A, still at least as good as object 3’s $6$ minus $\varepsilon$.

This is the whole rule, and it is worth seeing why it is the right one. The margin is the most A would pay to keep object 1 rather than settle for object 3, so raising the price by exactly the margin extracts A’s full willingness to pay. The extra $\varepsilon$ is what makes the auction move: without it, prices can rise by nothing at all, and — as the price war below shows — the auction can go round in circles for ever.

Then the next unassigned bidder does the same. If they want an object someone already holds, they take it and the previous holder becomes unassigned again, with the object’s price now higher. In the opening figure, C outbids B for object 3 at the third bid, B moves on to object 4, D takes object 1 from A, and so on for twelve bids until every bidder holds something and nobody wants to move.

What the prices know when the bidding stops #

When the auction ends, each bidder holds an object whose net value is within $\varepsilon$ of the best net value available to them at the final prices. That is true at the moment each bid is made — the raise was chosen to make it so — and it stays true, because later bids only raise the prices of other objects, which can only make the held object look better by comparison.

That condition is ε-complementary slackness, and it is a certificate with a known tolerance.

The argument is the same one the certificate essay used, with an error term. For any assignment whatever, each bidder’s value for the object they get is at most their best net value plus that object’s price. Summing over bidders, every assignment’s total is at most the sum of the best net values plus the sum of all prices — here $133/5$. The auction’s own assignment gets each bidder within $\varepsilon$ of their best net value, so it is within $n\varepsilon$ of that bound. The auction’s answer is at most $n\varepsilon$ below the best possible.

And now a one-line argument turns an approximation into an exact answer. The values are whole numbers, so every assignment’s total is a whole number. If $n\varepsilon < 1$ — that is, $\varepsilon < 1/n$ — then the auction’s total is less than one below the best, and a whole number less than one below another whole number is equal to it. With four bidders and $\varepsilon = 1/5$, the certificate says the answer is within $4/5$ of the best, and so it is the best.

The bound in the figure is even tighter than that argument needs: the gap between what was won and what the prices allow is $3/5$, less than the $4/5$ the rule guarantees.

A coarse increment, and a wrong answer #

The integrality argument needs $\varepsilon$ small. Take it large and the certificate loosens, and the auction can stop at an assignment that is not the best.

The failure is instructive because every individual bid was reasonable. With an increment of $1$, each bidder is allowed to settle for an object up to one unit worse than their best, and four bidders each settling for slightly less can add up to an assignment two units worse overall. Here C ends up with the object nobody wanted, because by the time C had to choose, the prices of the objects C valued had been pushed past the point where C could afford them with a whole unit of slack in every bid.

Following C through the log shows how it happens. C first wants object 3, which it values at 7, and takes it cheaply. Then A and B, who both value object 3 highly, push its price to 8 in two bids; D and A fight over object 1 and push it to 7; and when C is displaced for the last time, every object it values has a price within a unit of its value, so every object C values is now priced above what it is worth to C, and object 2 — worth nothing, and priced at nothing — has become C’s best. The prices overshot because each bid added a whole unit on top of the margin; with a smaller increment they would have stopped rising before C was priced out.

Nothing about the procedure is broken. It has answered a different question — find an assignment within $n\varepsilon$ of the best — and answered it correctly. Asking for an exact answer means asking for an increment below $1/n$.

The price war #

Why not take $\varepsilon = 0$ and let each bid extract exactly the margin? Because ties.

Suppose three bidders all value objects 1 and 2 at $10$ and object 3 at nothing. The first bidder takes object 1; its margin over object 2 is zero, so the price does not move. The second takes object 2, same thing. The third wants object 1 or 2 equally, takes object 1 from the first bidder, and raises its price by — nothing. The first bidder, now unassigned, sees objects 1 and 2 at price zero and takes object 2 from the second. And so on. Nobody ever turns to object 3, because objects 1 and 2 are always worth ten at a price of zero.

With a positive increment, each steal raises a price by $\varepsilon$, and after enough steals the two coveted objects cost enough that object 3, at price zero, is as good. The war ends when the prices of objects 1 and 2 have risen by about $10$ — which takes about $10/\varepsilon$ bids, each moving a price by $\varepsilon$. That is the straight line in the figure.

This is the real cost of a small increment. The auction is exact when $\varepsilon < 1/n$, but the number of bids it takes can grow in proportion to the size of the values divided by $\varepsilon$ — which, with $\varepsilon$ near $1/n$, is proportional to $n$ times the largest value. On tables where many bidders want the same few objects, that is slow.

The trade the increment makes #

The two effects pull in opposite directions, and one table shows both at once.

Large increments end quickly and may end wrong. Small ones end right and slowly. The standard remedy, also Bertsekas’s, is ε-scaling: run the auction with a large increment, keep the final prices, shrink $\varepsilon$ by a constant factor, and run again from those prices, repeating until $\varepsilon < 1/n$. Each run starts with prices that are nearly right, so it only has to settle small disagreements, and the total work comes down to a bound polynomial in $n$ and in the logarithm of the largest value — the same kind of bound the best alternatives have.

The pattern of the lower chart — a staircase rather than a smooth rise — also says something about where the effort goes. On a small table most increments produce the same sequence of choices and differ only in how much each price moves. The number of bids jumps when a smaller increment makes some bidder’s net values tie differently, or makes a price war last longer before it resolves. On the price-war table every halving of $\varepsilon$ roughly doubles the bids; on a table without heavy competition, shrinking $\varepsilon$ costs almost nothing.

Three hundred tables #

The guarantee is a theorem, but a theorem about a procedure is worth checking against the procedure, and this one is cheap to check: a five-by-five table has only $120$ assignments, so the best can be found by listing them all.

Two things show in the histogram. The bound $n\varepsilon$ is a worst case, and a loose one in practice: a coarse auction usually finds the best assignment anyway, and when it misses, it misses by a unit or two, not by five. And the fine auction’s perfect record is not luck — the integrality argument forbids anything else — but it is reassuring to see a theorem about whole numbers and increments hold on three hundred tables it knew nothing about. The tables are small enough that every one of the $120$ assignments was valued, so each of the three hundred verdicts compares the auction with the true best rather than with another method’s answer — which is the only kind of check that could catch a mistake in the argument rather than confirm a shared one. And the shortfalls cluster at one for a reason the certificate explains: a coarse auction misses only when two or more bidders each settle for slightly less at the same time, and on random tables that is uncommon.

An auction is a proposal that can be rejected #

The shape of the bidding will be familiar to anyone who has met deferred acceptance, the algorithm behind stable matching. There, unmatched people propose to their favourite remaining choice; a choice holds on to the best proposal so far and rejects the rest; the rejected propose again. Here, unassigned bidders bid for their favourite object at current prices; an object is held by its latest bidder and the previous holder is displaced; the displaced bid again. In both, the process runs until nobody is unmatched, and in both the result has a property that no pair of participants can improve on by going off on their own.

The resemblance is a theorem rather than a coincidence. Gabrielle Demange, David Gale and Marilda Sotomayor described in 1986 an ascending auction whose prices rise only on over-demanded objects, and showed that it reaches the smallest market-clearing prices; deferred acceptance is the special case where values are replaced by rankings and prices cannot move. The auction here is a close cousin — its increments are larger than theirs, which is what makes it fast, and its final prices are market-clearing within $\varepsilon$ rather than the smallest.

Those final prices also have a fairness property that has nothing to do with total value. At prices where every bidder holds an object within $\varepsilon$ of their best, nobody envies anybody else’s object-and-price pair by more than $\varepsilon$: if they preferred it, they would have bid for it. That is the property a rent nobody envies demands of a division of rooms among housemates, with one extra constraint the auction does not impose — there, the prices must add up to a fixed rent. Envy-free prices always exist; forcing them to sum to a given total is what needed Sperner’s lemma.

The same prices from the other side #

The certificate the auction produces is the certificate the prices for every person and task produced by a different route — a set of object prices and bidder profits that make every used pair tight and no pair over-tight. The Hungarian method builds such prices from the other direction, lowering a person’s price or raising a task’s until a complete assignment of tight pairs exists.

Two differences make the auction the method of choice in some settings. It is local: a bid needs only the bidder’s own values and the current prices, not the whole table. So bids can be made by many bidders at once, on many machines, and the method spreads across a network in a way the Hungarian method’s global adjustments do not. And it is incremental: if one value changes after the auction has finished, the old prices are a good starting point and only the bidders affected need to bid again.

The interpretation is the reason the prices mean anything outside the algorithm. At the end of the auction every bidder holds an object they would not trade for any other at the posted prices, within $\varepsilon$ — which is what an economist calls a competitive equilibrium. The prices clear the market, and the fact that market-clearing prices certify the best assignment is the economic reading of linear-programming duality. That reading goes further, into which of the many clearing price vectors the buyers or the sellers would prefer, and it is the subject of the prices nobody can break away from.

What the bid log cannot show #

Every figure above is a small table, decided exactly, and small tables hide the auction’s weaknesses. The number of bids on a table of a thousand bidders depends on how the values are arranged far more than on the size of the table, and the tables that make the auction slow — many bidders wanting the same objects, with values close together — are exactly the ones a four-by-four table cannot exhibit. The price war is the only honest picture of that here, and it is an extreme case built to be one.

The figures also run the Gauss–Seidel version, in which one bidder bids at a time. The version in which all unassigned bidders bid at once, and each object goes to the highest bidder, is the one that parallelises, and its behaviour is similar but not identical: bidding rounds replace single bids, and a round can resolve several conflicts at once. Nothing here measures it. And every table drawn is bipartite — bidders on one side, objects on the other — which is what makes the prices a complete certificate; once the pairs can form odd cycles the same bidding has no integrality to rely on, and fractional corners appear.

And the pictures show nothing about the proof that ε-scaling gives a polynomial bound. That argument is about how far prices can be from their final values at the start of each scaled run, and it is an inequality, not a picture.

Still open: how few bids the hard tables need #

The auction’s correctness is settled and so is its worst case up to constant factors: with ε-scaling, the number of bids is bounded by a polynomial in $n$ times the number of scaling phases. What is not settled is the gap between that worst case and practice. On random tables the auction is typically far faster than its bound, the price wars that drive the bound are rare, and there is no sharp theory of when a table will provoke one.

The question of which assignment method is fastest has moved recently and not settled. In 2022 an algorithm for minimum-cost flow running in almost-linear time in the size of the network was announced, which in principle solves the dense assignment problem in about the time it takes to read the table. It is a theoretical landmark and not a practical method: its constants and its construction are far from anything used on real tables, where the auction, the Hungarian method and their descendants still do the work. Whether a method as simple as bidding can come close to that bound, and what the right measure of a table’s difficulty for an auction is, are open.