Introduction

Every day, billions of ad slots sell in milliseconds, medical residents match hospitals, and kidney donors are paired with recipients — all without a human auctioneer setting each price by hand. These are matching markets: systems that pair one side of a market with the other and find prices at which supply meets demand.

The idea is old. In the 1870s, Léon Walras imagined a fictional auctioneer calling out prices until every market cleared simultaneously — no unsold goods, no unsatisfied buyers at the going price. We now call such a vector a Walrasian equilibrium, and we know it exists for a broad class of markets (Arrow–Debreu, 1954).

What changed in the late twentieth century is that we needed to compute these equilibria fast enough to run ad auctions ten million times a day. That shift from existence to computation is the heart of algorithmic market design — and the subject of this article.

Watch Prices Clear

Below is a small market with 3 goods and 4 buyers. Each buyer has a value for each good, and there is one unit of each good available. The current prices start low — too low, so multiple buyers want the same good at once (excess demand).

<!-- Market clearing demo — buyers demand the good with highest surplus; prices adjust until cleared -->
<div class="hint-box">Each buyer demands the good giving the highest surplus (value − price). <b>Green</b> = matched; <b>red</b> = contested. Prices adjust until every good has at most one buyer.</div>
<div class="market-wrap">
  <table id="val-table" class="val-table">
    <thead>
      <tr>
        <th>Buyer</th>
        <th>Good A</th>
        <th>Good B</th>
        <th>Good C</th>
        <th>Demands</th>
      </tr>
    </thead>
    <tbody id="val-body"></tbody>
    <tfoot>
      <tr class="price-row" id="price-row">
        <td>Price</td>
        <td id="p0">0</td>
        <td id="p1">0</td>
        <td id="p2">0</td>
        <td></td>
      </tr>
    </tfoot>
  </table>
</div>
<div id="status" class="status">Prices start at 0 — press Step or Auto to adjust.</div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-auto" type="button">Auto</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the matching-markets-clearing demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint-box { font-size: .85rem; color: #444; margin-bottom: .7rem; line-height: 1.5; }
.market-wrap { overflow-x: auto; margin-bottom: .6rem; }
.val-table { border-collapse: collapse; width: 100%; min-width: 280px; font-size: .9rem; }
.val-table th, .val-table td { border: 1px solid #cdd9e3; padding: .35rem .55rem; text-align: center; }
.val-table th { background: #e8eef3; color: #1d3557; font-weight: 700; }
.val-table td:first-child { font-weight: 600; text-align: left; }
/* Green = demanded by exactly one buyer; Red = contested (multiple buyers want it) */
td.demanded { background: #d4edda; font-weight: 700; }
td.contested { background: #f8d7da; }
td.surplus-zero { color: #888; }
.price-row td { background: #1d3557; color: #fff; font-weight: 700; }
.price-row td:first-child { text-align: left; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.5em; margin-bottom: .5rem; }
.status.cleared { color: #0a7d33; }
.status.adjusting { color: #b25000; }
.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] ?? ''));
// Tatonnement: raise prices of over-demanded goods, lower prices of under-demanded goods
// Three goods available in the market (one unit each)
const GOODS = ['A', 'B', 'C'];
// Buyer valuations matrix [buyer][good] — each cell is willingness-to-pay
// Row = buyer, Col = good. Chosen so clearing prices are A=3, B=5, C=4.
const VALUES = [
  [8, 5, 3],
  [4, 9, 6],
  [7, 3, 8],
  [5, 7, 4]
];
const BUYER_NAMES = ['Buyer 1', 'Buyer 2', 'Buyer 3', 'Buyer 4'];
let prices = [0, 0, 0];
let autoTimer = null;
let stepCount = 0;

// Each buyer demands the good with highest non-negative surplus (value minus price)
function computeDemands() {
  const demands = [];
  for (let b = 0; b < VALUES.length; b++) {
    let bestSurplus = -Infinity;
    let bestGoods = [];
    for (let g = 0; g < GOODS.length; g++) {
      const surplus = VALUES[b][g] - prices[g];
      if (surplus > bestSurplus && surplus >= 0) { bestSurplus = surplus; bestGoods = [g]; }
      else if (surplus === bestSurplus && surplus >= 0) { bestGoods.push(g); }
    }
    // Tie-break by lowest index (first good wins ties)
    demands.push(bestGoods.length > 0 ? bestGoods[0] : -1);
  }
  return demands;
}

// Market clears when every good has at most one buyer demanding it
function isCleared(demands) {
  const count = [0, 0, 0];
  for (const d of demands) { if (d >= 0) count[d]++; }
  return count.every(c => c <= 1);
}

function renderTable(demands) {
  const tbody = document.getElementById('val-body');
  tbody.innerHTML = '';
  // Count how many buyers demand each good to detect oversubscription
  const demandCount = [0, 0, 0];
  for (const d of demands) { if (d >= 0) demandCount[d]++; }
  for (let b = 0; b < VALUES.length; b++) {
    const tr = document.createElement('tr');
    const nameTd = document.createElement('td');
    nameTd.textContent = BUYER_NAMES[b];
    tr.appendChild(nameTd);
    for (let g = 0; g < GOODS.length; g++) {
      const td = document.createElement('td');
      const surplus = VALUES[b][g] - prices[g];
      td.textContent = surplus >= 0 ? `${VALUES[b][g]} (${surplus >= 0 ? '+' : ''}${surplus})` : `${VALUES[b][g]} (${surplus})`;
      // Color-code cells: green = sole demander, red = contested
      if (demands[b] === g) {
        td.className = demandCount[g] > 1 ? 'contested' : 'demanded';
      } else if (surplus === 0) {
        td.className = 'surplus-zero';
      }
      tr.appendChild(td);
    }
    const demTd = document.createElement('td');
    demTd.textContent = demands[b] >= 0 ? GOODS[demands[b]] : '—';
    tr.appendChild(demTd);
    tbody.appendChild(tr);
  }
  // Refresh displayed prices in the footer row
  for (let g = 0; g < GOODS.length; g++) {
    document.getElementById('p' + g).textContent = prices[g];
  }
}

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

// One tatonnement step — adjust prices then re-check
function step() {
  const demands = computeDemands();
  if (isCleared(demands)) {
    renderTable(demands);
    setStatus('Market is already cleared.', 'cleared');
    stopAuto();
    return;
  }
  // Raise price of over-demanded goods (+1), lower price of under-demanded goods (-1, floor 0)
  const demandCount = [0, 0, 0];
  for (const d of demands) { if (d >= 0) demandCount[d]++; }
  for (let g = 0; g < GOODS.length; g++) {
    if (demandCount[g] > 1) prices[g]++;
    else if (demandCount[g] === 0 && prices[g] > 0) prices[g]--;
  }
  stepCount++;
  const newDemands = computeDemands();
  renderTable(newDemands);
  if (isCleared(newDemands)) {
    setStatus(i18nFmt('Cleared in %steps% step(s)! Every good has at most one buyer.', { steps: stepCount }), 'cleared');
    stopAuto();
    document.getElementById('btn-step').disabled = true;
  } else {
    setStatus(i18nFmt('Step %step%: prices adjusted, market not yet clear.', { step: stepCount }), 'adjusting');
  }
}

function stopAuto() {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
  document.getElementById('btn-auto').textContent = 'Auto';
  document.getElementById('btn-auto').disabled = false;
}

function toggleAuto() {
  if (autoTimer) {
    stopAuto();
  } else {
    document.getElementById('btn-auto').textContent = 'Stop';
    autoTimer = setInterval(() => { step(); }, 600);
  }
}

function reset() {
  stopAuto();
  prices = [0, 0, 0];
  stepCount = 0;
  const demands = computeDemands();
  renderTable(demands);
  setStatus('Prices start at 0 — press Step or Auto to adjust.', 'adjusting');
  document.getElementById('btn-step').disabled = false;
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-auto').addEventListener('click', toggleAuto);
document.getElementById('btn-reset').addEventListener('click', reset);

// Initial render — show starting state with all prices at 0
reset();
Result
Console

Press Step to run one round of the tatonnement process: prices of over-demanded goods rise by 1, prices of under-demanded goods fall by 1 (but never below 0). Press Auto to watch it converge on its own. When every good has at most one interested buyer — or none — the market clears.

Notice that each buyer's demand is simply the good that gives the highest surplus v−pv - p (value minus price). When two goods tie, the buyer is indifferent; the demo breaks ties by index. Clearing is always reached in a finite number of steps for this type of market.

The Real Complexity

How hard is it to find clearing prices, really?

  • Existence: Arrow and Debreu proved in 1954 that a competitive equilibrium exists whenever goods are divisible and preferences are convex. For discrete goods the story is subtler — existence is not always guaranteed.
  • Gross substitutes: Kelso and Crawford (1982) identified a condition — gross substitutes — under which prices can be raised one good at a time without destroying equilibrium for other goods. Under this condition a simple ascending auction converges to Walrasian prices in polynomial time. The tatonnement you just watched is essentially this.
  • Complementarities break everything: when buyers want bundles (good A and good B together), finding clearing prices can fail to exist, and even approximately finding a good allocation is NP-hard. This is the Combinatorial Auction problem.
  • PPAD and beyond: for more general exchange economies, finding Nash-style equilibria lands in the complexity class PPAD — believed to be hard but not NP-complete. Even verifying that a proposed price vector clears every market simultaneously is in P (just check supply equals demand for each good), but finding one can be intractable.

The bottom line: clearing is easy when goods are substitutes and hard when they are complements. The gross-substitutes condition is the algorithmic dividing line that makes ad auctions tractable and combinatorial spectrum auctions a genuine challenge. Compare with assignment, where bipartite matching finds an optimal allocation in polynomial time without any price computation at all.

Where It Matters

The clearing-price idea shows up everywhere a price or assignment must reconcile competing wants:

  • Online ad auctions: Google and Meta run generalized second-price auctions billions of times per day. Under gross substitutes these clear in microseconds — the entire economy of the web runs on this single algorithmic fact.
  • Medical residency matching: the National Resident Matching Program uses the Gale–Shapley deferred-acceptance algorithm (no prices, just preference lists). It finds a stable matching — a price-free equilibrium — in O(n2)O(n^2) steps. Alvin Roth and Lloyd Shapley won the 2012 Nobel Prize in Economics for this work.
  • Kidney exchange: chains of donor–recipient pairs are assembled so that no pair would prefer to swap with someone else. This is a combinatorial matching problem solved nightly on real patient data.
  • Spectrum auctions: governments sell radio spectrum in packages. Bidders want complements (contiguous frequencies), making this a combinatorial auction — computationally hard, but practical heuristics (the FCC's clock auction) work well enough.

See also max matching for the pure graph-theory version, where no prices appear and the goal is simply the largest set of compatible pairs.

Conclusion

Matching markets reveal a beautiful fault line in economics and computation: when goods are substitutes, a simple price-raising process finds equilibrium in polynomial time, powering every ad auction on the internet. When goods are complements, existence of clearing prices can fail, and finding even a good allocation becomes NP-hard.

That line — gross substitutes versus complementarities — is not just a curiosity. It determines which markets can be automated and which require human judgment, heuristics, or approximation. The next time you see an ad while browsing, remember: a tiny tatonnement just ran in the cloud and cleared a miniature economy in your name.

For a pure algorithmic perspective with no prices at all, explore max matching — the graph-theory twin of everything discussed here.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/matching-markets-clearing/Content licensed under CC BY-NC 4.0.