Introduction

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(n3)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.

Watch the Auction

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.

<!-- Auction algorithm demo — agents bid on objects, prices rise, optimal assignment emerges -->
<p class="hint">Four agents bid on four objects. Each cell shows the agent's value for that object. Prices rise when agents compete. The auction ends when every agent holds an object and no one wants to switch.</p>
<div id="matrix-wrap">
  <table id="matrix" aria-label="Value matrix — agents vs objects"></table>
</div>
<div id="prices-row" class="prices-row" aria-label="Current object prices"></div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout and color-coding for the bidding simulation */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Auction algorithm (Bertsekas, 1979) — simplified integer epsilon version */

/* Value matrix: VALUES[i][j] = value agent i gets from object j */
const VALUES = [
  [8, 5, 3, 7],
  [6, 9, 4, 2],
  [3, 6, 8, 5],
  [5, 4, 7, 9]
];
const N = VALUES.length;

/* Global auction state */
let prices, assignment, ownerOf, done, running, timer;

function initState() {
  /* Reset all state to the start of the auction */
  prices = new Array(N).fill(0);
  assignment = new Array(N).fill(-1);
  ownerOf = new Array(N).fill(-1);
  done = false;
  running = false;
  clearTimeout(timer);
}

/* Render the value matrix, highlighting the current bidder and winner */
function renderMatrix(bidder, newObj, lostAgent) {
  const tbl = document.getElementById('matrix');
  tbl.innerHTML = '';
  const header = tbl.insertRow();
  header.insertCell().textContent = '';
  for (let j = 0; j < N; j++) {
    const th = document.createElement('th');
    th.textContent = 'Obj ' + (j + 1);
    header.appendChild(th);
  }
  for (let i = 0; i < N; i++) {
    const row = tbl.insertRow();
    const lbl = document.createElement('th');
    lbl.textContent = 'Agent ' + (i + 1);
    row.appendChild(lbl);
    for (let j = 0; j < N; j++) {
      const td = row.insertCell();
      const net = VALUES[i][j] - prices[j];
      td.textContent = VALUES[i][j];
      if (assignment[i] === j) {
        td.className = 'val assigned';
      } else if (bidder === i && newObj === j) {
        td.className = 'val bidding';
      } else if (lostAgent === i && assignment[lostAgent] === -1 && bidder !== -1) {
        td.className = 'val outbid';
      } else {
        td.className = 'val';
      }
      /* Show net value (value minus current price) in tooltip */
      td.title = i18nFmt('Net value (value minus price) = %net%', { net: net });
    }
  }
}

function renderPrices() {
  /* Render current prices as chips below the matrix */
  const row = document.getElementById('prices-row');
  row.innerHTML = '';
  for (let j = 0; j < N; j++) {
    const chip = document.createElement('div');
    chip.className = 'price-chip';
    chip.innerHTML = '<span>Obj ' + (j + 1) + '</span>' + prices[j].toFixed(1);
    row.appendChild(chip);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

/* Advance the auction by one bidding round */
function auctionStep() {
  if (done) return;

  /* Find the first unassigned agent (the bidder for this round) */
  let bidder = -1;
  for (let i = 0; i < N; i++) {
    if (assignment[i] === -1) { bidder = i; break; }
  }

  if (bidder === -1) {
    /* All agents assigned — auction complete */
    done = true;
    renderMatrix(-1, -1, -1);
    renderPrices();
    /* Build the result summary */
    let total = 0;
    const pairs = [];
    for (let i = 0; i < N; i++) {
      total += VALUES[i][assignment[i]];
      pairs.push(i18nFmt('Agent %agent% → Obj %obj%', { agent: i + 1, obj: assignment[i] + 1 }));
    }
    setStatus(i18nFmt('Auction complete — total value: %total%', { total: total }), 'ok');
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    return;
  }

  /* Find the best and second-best object for this bidder by net value */
  let bestObj = -1, bestNet = -Infinity, secondNet = -Infinity;
  for (let j = 0; j < N; j++) {
    const net = VALUES[bidder][j] - prices[j];
    if (net > bestNet) { secondNet = bestNet; bestObj = j; bestNet = net; }
    else if (net > secondNet) { secondNet = net; }
  }

  /* Raise the price by (bestNet - secondNet + epsilon) to outbid the current owner */
  const eps = 1;
  const raise = bestNet - secondNet + eps;
  prices[bestObj] += raise;

  /* Evict the previous owner of the chosen object (if any) */
  const prev = ownerOf[bestObj];
  let lostAgent = -1;
  if (prev !== -1) { assignment[prev] = -1; lostAgent = prev; }

  ownerOf[bestObj] = bidder;
  assignment[bidder] = bestObj;

  renderMatrix(bidder, bestObj, lostAgent);
  renderPrices();

  const msg = lostAgent !== -1
    ? i18nFmt('Agent %bidder% outbids Agent %prev% on Obj %obj% (new price: %price%)', { bidder: bidder + 1, obj: bestObj + 1, prev: lostAgent + 1, price: prices[bestObj].toFixed(1) })
    : i18nFmt('Agent %bidder% bids on Obj %obj% (new price: %price%)', { bidder: bidder + 1, obj: bestObj + 1, price: prices[bestObj].toFixed(1) });
  setStatus(msg, 'busy');
}

function stepOnce() {
  if (done) return;
  auctionStep();
}

function runAll() {
  if (done || running) return;
  running = true;
  document.getElementById('btn-step').disabled = true;
  document.getElementById('btn-run').disabled = true;

  function tick() {
    if (done) { running = false; return; }
    auctionStep();
    timer = setTimeout(tick, 420);
  }
  tick();
}

function reset() {
  clearTimeout(timer);
  initState();
  renderMatrix(-1, -1, -1);
  renderPrices();
  setStatus('Press Step or Run to start the auction.', 'info');
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
}

document.getElementById('btn-step').addEventListener('click', stepOnce);
document.getElementById('btn-run').addEventListener('click', runAll);
document.getElementById('btn-reset').addEventListener('click', reset);

/* Initialize on load */
reset();
Result
Console

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 Real Complexity

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

  • Brute force: n!n! ways to assign nn agents to nn objects. For n=20n = 20 that is over 2×10182 \times 10^{18} permutations — completely hopeless.
  • Hungarian algorithm (Kuhn–Munkres, 1955): O(n3)O(n^3) time, the first polynomial solution. Based on augmenting paths and dual variables.
  • Auction algorithm (Bertsekas, 1979): also O(n3)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(n2log⁡(nC))O(n^2 \log(nC)) time where CC 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/assignment-auction-algorithm/Content licensed under CC BY-NC 4.0.