The Auction Algorithm

Imagine a hiring fair: three candidates and three open roles. Each candidate has a different value for each role. You want to assign everyone so the total value is as high as possible. This is the assignment problem, and it sits at the heart of logistics, scheduling, and machine learning.

The classical solution — the Hungarian algorithm (Kuhn, 1955) — works by augmenting paths in a bipartite graph. It is correct and runs in $O(n^3)$ time, but its logic feels abstract.

In 1979, Dimitri Bertsekas proposed a strikingly different approach: let the candidates bid. Each unassigned agent picks the role that gives it the best value at current prices, raises that role's price by a small amount $\varepsilon$, and takes the role from whoever held it. Evicted agents re-enter the auction. When no one wants to overbid, the auction is over — and the final assignment is optimal.

The insight is profound: market equilibrium and combinatorial optimality are the same thing. A price system that clears all competition is exactly a certificate of optimality for the assignment.

Below, four agents (rows) compete for four objects (columns). Each cell shows the value that agent gets from that object. Press Step to advance one bidding round, or Run to watch the auction complete automatically.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="matrix-wrap">
  <table id="matrix" aria-label="{{aria_table}}"></table>
</div>
<div id="prices-row" class="prices-row" aria-label="{{aria_prices}}"></div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
#matrix-wrap { overflow-x: auto; margin-bottom: .4rem; }
table { border-collapse: collapse; }
th { font-size: .78rem; font-weight: 600; padding: 4px 8px; color: #555; text-align: center; }
td { width: 56px; height: 44px; text-align: center; font: 700 16px ui-monospace, monospace;
     border: 1px solid #dce3ea; border-radius: 6px; position: relative; transition: background .25s; }
td.val { color: #1d3557; background: #f0f4f8; }
td.assigned { background: #0a7d33; color: #fff; }
td.bidding { background: #f4a261; color: #fff; }
td.outbid { background: #e63946; color: #fff; }
.prices-row { display: flex; gap: 6px; margin-bottom: .5rem; flex-wrap: wrap; }
.price-chip { font: 600 13px ui-monospace, monospace; background: #e8eef3; border: 1px solid #cdd9e3;
              border-radius: 6px; padding: 3px 10px; color: #1d3557; }
.price-chip span { font-weight: 400; color: #555; margin-right: 4px; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.busy { color: #c97b0f; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice how prices rise whenever two agents want the same object. An agent loses its current object when outbid, and must find a new one. The auction ends when every agent holds an object and no agent wants to switch — that is the optimal assignment.

The assignment problem is solved — not merely approximated. Here is what we know:

• Brute force: $n!$ ways to assign $n$ agents to $n$ objects. For $n = 20$ that is over $2 \times 10^{18}$ permutations — completely hopeless.
• Hungarian algorithm (Kuhn–Munkres, 1955): $O(n^3)$ time, the first polynomial solution. Based on augmenting paths and dual variables.
• Auction algorithm (Bertsekas, 1979): also $O(n^3)$ in the worst case. But it operates on prices, not graph paths, and is naturally parallelizable — many agents can bid simultaneously.
• The equivalence theorem: Bertsekas proved that when the auction terminates, its price vector is a dual certificate of optimality — identical in spirit to the dual solution of the Hungarian algorithm. The market and the graph algorithm are two faces of the same mathematical truth.
• Epsilon-scaling: by starting with a large $\varepsilon$ and halving it, the algorithm runs in $O(n^2 \log(nC))$ time where $C$ is the largest value, matching the best strongly polynomial bounds.

The assignment problem belongs to the class P — it is solvable in polynomial time, placing it firmly on the tractable side of the P vs NP divide. It is also a cornerstone of the theory of min-cost flow, of which assignment is a special case.

The assignment problem — and the auction algorithm — appear anywhere resources must be matched to needs optimally:

• Ride-sharing dispatch: every few seconds, platforms like Uber solve a massive assignment problem to pair riders with nearby drivers at minimum total cost.
• Ad auctions: online ad markets run generalized auctions in milliseconds to match advertisers to available impressions, balancing bids and relevance.
• Organ matching: kidney exchange programs use variants of matching algorithms to find compatible donor-recipient chains that maximize lives saved.
• Optimal transport: the Wasserstein distance in machine learning — used in generative models and distribution comparison — is fundamentally an assignment problem.
• Parallel computing: the auction algorithm's decentralized bidding structure maps naturally onto GPU and distributed systems, making it practical at scales where the Hungarian algorithm struggles.

Whenever you match workers to tasks, ships to ports, or pixels to palettes, you are solving assignment — and an auction, real or simulated, is one of the cleanest ways to do it.

Bertsekas' auction algorithm is a beautiful example of how economic intuition and mathematical rigor reinforce each other. A competitive market, left to adjust prices until no agent envies another's object, naturally produces the globally optimal assignment — the same result that took decades of combinatorial mathematics to derive by other means.

The next time you hail a ride, see a targeted ad, or benefit from an organ transplant, there is a good chance a descendant of this auction is quietly running behind the scenes, finding the best match in the time it takes to blink.