Matching Markets

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.

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

<!-- {{c_html_intro}} -->
<div class="hint-box">{{hint_para}}</div>
<div class="market-wrap">
  <table id="val-table" class="val-table">
    <thead>
      <tr>
        <th>{{th_buyer}}</th>
        <th>{{th_good}} A</th>
        <th>{{th_good}} B</th>
        <th>{{th_good}} C</th>
        <th>{{th_demands}}</th>
      </tr>
    </thead>
    <tbody id="val-body"></tbody>
    <tfoot>
      <tr class="price-row" id="price-row">
        <td>{{th_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">{{status_initial}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-auto" type="button">{{btn_auto}}</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; 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; }
/* {{c_css_cell_colors}} */
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; }

// Code not found

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 - 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.

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.

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

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.