Online Bipartite Matching

Imagine you run a search engine. Each second, a query arrives, and you must instantly show it an ad from an advertiser whose budget and targeting fit that query. You have to decide now — before the next query arrives, before you know what the rest of the day holds — and once an advertiser's slot is filled, it's gone.

This is online bipartite matching. On one side sit the advertisers (or servers, or doctors, or taxis); on the other, requests that show up one at a time. Each request must be matched to a compatible, still-available partner immediately and irrevocably, or dropped forever.

If you could see the whole day in advance, you'd compute the perfect matching with a classic offline algorithm. The catch is the future: commit a scarce advertiser to an early generic query and you may strand the only query that advertiser could have served later. How much do you lose by being forced to decide blind — and is there a smart way to decide?

Four advertisers each have one ad slot. Queries arrive one at a time and you must assign each to a relevant, still-free advertiser — or skip it. You can't go back. Try to match as many as you can.

<p class="hint">{{hint}}</p>
<div class="slots" id="slots"></div>
<div class="arrival" id="arrival">{{arrival_initial}}</div>
<div class="choices" id="choices"></div>
<div class="score" id="score">{{your_matches}}: 0</div>
<div class="btns">
  <button id="start" type="button">{{btn_start}}</button>
  <button id="opt" type="button" class="ghost">{{btn_opt}}</button>
  <button id="rank" type="button" class="ghost">{{btn_rank}}</button>
</div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.slots { display: flex; gap: 8px; margin: .4rem 0 .8rem; flex-wrap: wrap; }
.slot { width: 64px; height: 56px; border-radius: 10px; border: 1px solid #cdd9e3;
        background: #e8eef3; display: flex; flex-direction: column; align-items: center;
        justify-content: center; font: 700 18px ui-monospace, monospace; color: #1d3557; }
.slot small { font: 600 10px system-ui; color: #5a7088; margin-top: 2px; }
.slot.taken { background: #1d3557; color: #fff; border-color: #11243d; }
.slot.taken small { color: #9fb2c8; }
.arrival { font-size: 1rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.choices { display: flex; gap: .4rem; flex-wrap: wrap; margin: .5rem 0; }
.choices button { font: 700 14px ui-monospace, monospace; }
.score { font-size: 1rem; font-weight: 700; margin: .5rem 0; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
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: .4; cursor: not-allowed; }

// Code not found

Here's the trap. The first two queries fit everyone, so grabbing A then B feels harmless — but the last two queries can only go to A and B, and now those slots are spent: you finish with 2 matches when 4 were possible in hindsight. Press Show hindsight optimum to see it, then Run RANKING ×2000: the randomized algorithm picks a secret random priority over the advertisers and tends to keep the scarce ones free, averaging well above any naive grab.

The offline problem is easy: with the whole graph in hand, a maximum bipartite matching is found in polynomial time by augmenting paths (Hopcroft–Karp). The hard part is being online — and here the difficulty is measured not by running time but by the competitive ratio: the worst-case fraction of the hindsight optimum your algorithm can guarantee.

• Any deterministic algorithm is stuck at 1/2. An adversary watching your fixed rule can always feed arrivals that make you waste exactly half your potential — and no deterministic strategy does better.
• Randomness breaks the wall. In 1990 Richard Karp, Umesh Vazirani and Vijay Vazirani introduced RANKING: shuffle the advertisers into a secret random priority order once, then always match each arrival to the highest-priority free option it fits. In expectation, RANKING matches at least a 1 − 1/e ≈ 0.632 fraction of the optimum.
• That bound is optimal. They also proved a matching upper bound: no online algorithm — randomized or not — can beat 1 − 1/e in the worst case. RANKING is exactly as good as anything can be.
• Why 1 − 1/e? The same constant pops out of a balls-and-bins argument: a random priority spreads commitments so that, in expectation, only an $e$-fraction of the optimal matches are ever lost.

So this is not an open problem and not an intractable one — it is a solved problem with a beautiful, tight answer. Like the offline version it relates to maximum matching, but the "decide before you see the future" twist gives it a sharp, provable price.

"Commit to a match the instant a request arrives" describes an enormous slice of modern infrastructure, and online matching is its theory:

• Online advertising: the AdWords problem — assigning search queries to bidding advertisers under budgets — is the headline application, and the (1 − 1/e) analysis underpins real allocation algorithms serving billions of impressions.
• Ride-hailing and delivery: a rider or order appears and must be dispatched to a nearby free driver right away, without knowing who will request next.
• Load balancing: incoming jobs are routed to available servers on arrival, the classic "balls into bins" version of the same question.
• Organ and resource exchange: time-critical allocation where waiting to optimize globally is not an option.

Whenever the future is hidden and choices can't be taken back, the lesson is the same one this article makes playable: a dash of randomness can provably rescue most of what hindsight would have won.

Online bipartite matching turns a real anxiety — decide now, regret never — into a clean theorem. You can't match more than the hindsight optimum, and against a clever adversary a fixed rule loses half. Yet one secret random priority, the RANKING algorithm, claws back a provable 1 − 1/e of the best possible, and nothing can do better.

That is the quiet beauty here: unlike the puzzles tangled up with P vs NP, this one is fully solved. The next time an ad loads in milliseconds or a taxi appears around the corner, there's a 35-year-old coin flip making sure the system gives up as little as the laws of computation allow.