Introduction

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?

Match the Arrivals

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">Four advertisers (A B C D) each have one ad slot. Search queries arrive <b>one at a time</b> and must be assigned <b>immediately</b> to a relevant, still-free advertiser — or skipped forever. You are the matcher. Maximize matches, then compare with the hindsight optimum and the RANKING algorithm.</p>
<div class="slots" id="slots"></div>
<div class="arrival" id="arrival">Press <b>Start</b> to receive the first query.</div>
<div class="choices" id="choices"></div>
<div class="score" id="score">Your matches: 0</div>
<div class="btns">
  <button id="start" type="button">Start / Reset</button>
  <button id="opt" type="button" class="ghost">Show hindsight optimum</button>
  <button id="rank" type="button" class="ghost">Run RANKING ×2000</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Online bipartite matching. Advertisers A,B,C,D each have one slot. Queries arrive one at a time; each lists the advertisers it's relevant to and must be matched on arrival (or skipped). The hindsight optimum (offline) can rearrange everything; the online matcher cannot see the future. RANKING fixes a RANDOM rank over the advertisers and always matches an arriving query to its lowest-ranked free option; in expectation it matches at least (1 - 1/e) ≈ 63% of the optimum (Karp, Vazirani & Vazirani, 1990) — the best any online algorithm can do.
const ADV = ['A','B','C','D']; const nR = 4;
// adj[query] = relevant advertiser indices. q1,q2 are broad; q3 needs A, q4 needs B.
const ADJ = [[0,1,2,3],[0,1,2,3],[0],[1]];
const nL = ADJ.length;

// Offline hindsight optimum via augmenting paths (Kuhn's algorithm).
function maxMatching(adj){
  const matchR = new Array(nR).fill(-1);
  function tryK(l, seen){ for(const r of adj[l]){ if(seen[r]) continue; seen[r]=true;
    if(matchR[r]===-1 || tryK(matchR[r], seen)){ matchR[r]=l; return true; } } return false; }
  let c=0; for(let l=0;l<nL;l++){ const s=new Array(nR).fill(false); if(tryK(l,s)) c++; } return c;
}
// RANKING: lowest-ranked free relevant advertiser.
function ranking(rank){ const used=new Array(nR).fill(false); let c=0;
  for(let l=0;l<nL;l++){ let b=-1; for(const r of ADJ[l]) if(!used[r] && (b===-1||rank[r]<rank[b])) b=r;
    if(b!==-1){ used[b]=true; c++; } } return c; }

let step, used, matched;
const $ = id => document.getElementById(id);

function drawSlots(){ const s=$('slots'); s.innerHTML='';
  ADV.forEach((a,i)=>{ const d=document.createElement('div');
    d.className='slot'+(used[i]?' taken':'');
    d.innerHTML = a + '<small>'+(used[i]?'matched':'free')+'</small>'; s.appendChild(d); }); }

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

function start(){ step=0; used=new Array(nR).fill(false); matched=0;
  drawSlots(); $('score').textContent='Your matches: 0'; setStatus('',''); next(); }

function next(){ const ch=$('choices'); ch.innerHTML='';
  if(step>=nL){ $('arrival').textContent='No more queries arrive.';
    setStatus(fmt('You matched %matched% of %maxMatching% (hindsight optimum). Reveal it or run RANKING below.', { matched: matched, maxMatching: maxMatching(ADJ.map(a=>a.slice())) }), matched>=3?'ok':'bad'); return; }
  const fits = ADJ[step];
  $('arrival').textContent = fmt('Query q%step%%v% arrives — relevant to: %map%', { step: step, v: 1, map: fits.map(i=>ADV[i]).join(', ') });
  fits.forEach(i=>{ const b=document.createElement('button');
    b.textContent=fmt('Give to %v%', { v: ADV[i] }); b.disabled=used[i];
    b.onclick=()=>{ used[i]=true; matched++; drawSlots();
      $('score').textContent=fmt('Your matches: %matched%', { matched: matched }); step++; next(); }; ch.appendChild(b); });
  const skip=document.createElement('button'); skip.className='ghost'; skip.textContent='Skip query';
  skip.onclick=()=>{ step++; next(); }; ch.appendChild(skip);
}

function showOpt(){ const o=maxMatching(ADJ.map(a=>a.slice()));
  setStatus(fmt('Hindsight optimum = %o% matches (q1→C, q2→D, q3→A, q4→B). A naive grab of A then B for the first two queries leaves q3 and q4 with nothing — only 2 matches.', { o: o }),
    'ok'); console.log('Hindsight optimum =', o); }

function runRanking(){ const T=2000; let sum=0; const dist={};
  for(let t=0;t<T;t++){ const perm=[0,1,2,3];
    for(let i=3;i>0;i--){ const j=Math.floor(Math.random()*(i+1)); [perm[i],perm[j]]=[perm[j],perm[i]]; }
    const rank=new Array(nR); perm.forEach((adv,pos)=>rank[adv]=pos);
    const c=ranking(rank); sum+=c; dist[c]=(dist[c]||0)+1; }
  const avg=sum/T, opt=maxMatching(ADJ.map(a=>a.slice()));
  setStatus(fmt('RANKING over %T% random ranks: average %avg% of %opt% (%round%% of optimum), far above the (1−1/e)≈63% worst-case floor. Distribution: %map%', { T: T, avg: avg.toFixed(2), opt: opt, round: Math.round(100*avg/opt), map: Object.keys(dist).sort().map(k=>k+'→'+(100*dist[k]/T).toFixed(0)+'%').join(', ') }),'ok');
  console.log('RANKING avg', avg.toFixed(3), 'opt', opt, 'dist', dist); }

$('start').onclick=start;
$('opt').onclick=showOpt;
$('rank').onclick=runRanking;
used=new Array(nR).fill(false); matched=0; step=nL; drawSlots();
Result
Console

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

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

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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