Matching as they arrive

Hall’s theorem and the augmenting-path search find the largest matching of a graph that is given all at once. Many matchings are not made that way. Riders request cars one at a time; advertisements must be placed as each page is loaded; patients arrive at a clinic and are assigned to whatever slot is free. The graph is revealed a vertex at a time, and each decision is final: the arriving vertex is matched to one of its free neighbours, or to nothing, before the next one appears.

This is online matching, and the right question about it is not whether it finds the best matching — it cannot, since it cannot see the future — but how close it is guaranteed to come. The answer has two thresholds, one half and $1 - 1/e$, and both are sharp.

Taking whatever is free #

The simplest rule is greedy: when a vertex arrives, match it to any free neighbour if one exists. Whatever the tie-breaking, greedy produces a maximal matching — one to which no edge can be added, since any edge with both ends free would have been taken when its online end arrived.

A maximal matching is always at least half as large as a maximum one. Take any edge of the maximum matching. If neither of its ends were matched by greedy, greedy could have added it, contradicting maximality — so every maximum-matching edge touches a greedy edge. A greedy edge has two ends, and each end belongs to at most one maximum-matching edge, so each greedy edge accounts for at most two of them. Hence the maximum matching has at most twice as many edges as the greedy one.

The figure’s greedy rule is deliberately a poor one — each arrival takes the last free place on its list — and it matches five of eight where eight were possible. The argument above guarantees at least four, and five is what it got. The argument is also a kind of certificate, of the sort the augmenting-path essay prized: the ends of the greedy edges form a set of vertices touching every edge of the graph, so the maximum matching can be no larger than twice the greedy one, and anyone holding the greedy matching can check the bound without ever finding the maximum.

Every fixed rule can be held to half #

The bound of one half is not merely what the argument proves; it is the truth for any deterministic rule.

The adversary’s construction is two vertices long. The first arrival is qualified for two places, and the rule — whatever it is — must pick one. The adversary, knowing the rule, then presents a second arrival qualified only for the place that was picked. The rule matches one; the best matching, which would have sent the first arrival to the other place, matches two. Repeating the gadget with fresh vertices holds the rule to exactly half on graphs of any size. Nothing about the rule’s cleverness helps: a rule that looks at degrees, or at how many other arrivals might want a place, or at anything else it can see, is still deterministic, and the adversary simply simulates it and builds the second arrival to fit.

The construction depends on the adversary knowing which place the rule will pick. That is the opening for randomness: a rule that flips coins cannot be anticipated, and the adversary must commit to the graph before the coins are tossed.

One shuffle, fixed in advance #

The obvious randomised rule is to give each arrival a uniformly random free neighbour. It helps on the two-vertex gadget — the second arrival is stranded only half the time — but there are graphs on which it does little better than one half in expectation. The rule that works is subtler, and it is due to Richard Karp, Umesh Vazirani and Vijay Vazirani in 1990.

RANKING: before anything arrives, shuffle the places into a uniformly random order — a ranking. Then give each arrival the free place on its list that ranks highest. The randomness is used once, at the start, and after that the rule is deterministic.

The triangular graph is the hard case. Arrival 1 can take any place, arrival 2 any place but the first, and so on, down to arrival 8, which can take only place 8. The perfect matching sends each arrival to its own number, but an online rule does not know that later arrivals are more constrained, and a random ranking will often send early arrivals to the high-numbered places that late arrivals needed. In the drawing the best-ranked places happen to be 8, 6 and 7, and they are taken by arrivals 1, 2 and 3, which could have gone anywhere; arrivals 6, 7 and 8 then find their lists exhausted.

1 − 1/e, measured #

How much does RANKING match on average, as the triangle grows?

On small triangles RANKING matches three-quarters or more; by 128 a side it matches 63.2%, within sampling error of $1 - 1/e = 0.6321\dots$ Karp, Vazirani and Vazirani proved two things about that number. First, on every bipartite graph, with every order of arrivals, RANKING matches at least $1 - 1/e$ of the maximum in expectation. Second, no online algorithm, deterministic or randomised, can guarantee more than $1 - 1/e + o(1)$ on the triangular graphs — so the triangle is the worst case, and RANKING is optimal.

On the triangular graph the uniformly random rule does equally well, as the figure shows, because on this graph the two rules are nearly the same thing: an arrival’s free places are a block of consecutive numbers, and a random ranking restricted to a block is a uniform choice from it. The difference shows up on other graphs, where RANDOM can be pushed down towards one half and RANKING cannot. A single shuffle, used consistently, is better than fresh randomness at every step, because it makes the choices of different arrivals correlated in a way that protects the places a later arrival will need.

What a single shuffle protects #

Why should a ranking fixed in advance beat a fresh random choice at every step? Consider a place that is wanted by many arrivals and a place wanted by only one. A fresh random choice treats them alike every time, and so is likely, sooner or later, to hand the rare place to somebody who could have gone elsewhere. A fixed ranking is still random, so the adversary cannot predict it; but it is consistent. If a rarely wanted place is ranked low, it is ranked low for everyone, and every arrival with an alternative takes the alternative. The place survives until the one arrival that needs it.

That consistency is what the charging argument measures. It lets the analysis say, for each edge of the best matching, that either its place was taken by somebody earlier — in which case that place’s rank was good and it earned its share — or it was still free when its arrival came, in which case the arrival itself was matched. Fresh randomness breaks the link between one arrival’s luck and the next, and with it the accounting.

Pouring instead of choosing #

There is a deterministic way to reach the same constant, if the matching is allowed to be fractional. Instead of giving an arriving vertex a single place, pour one unit of water into its neighbouring places, always into whichever is currently least full, until the unit is used up or every neighbour is full. This water-filling rule is deterministic, and on every graph it fills at least $1 - 1/e$ of what the best fractional matching could. Bala Kalyanasundaram and Kirk Pruhs proved the guarantee in 2000, for places that can each accept many units, and the least-full rule is the whole of the algorithm: it keeps every place’s level as even as the arrivals allow, so that no place is exhausted early by arrivals that had somewhere else to go.

Fractional matchings are not a cheat. When each place can serve many arrivals — an advertiser with a large budget, a server with many slots — assigning fractions is exactly the right model, and a fractional matching can be turned back into a lottery over whole matchings by the Birkhoff decomposition. What water-filling shows is that the randomness in RANKING is standing in for divisibility: the adversary can defeat any deterministic choice of one place, but it cannot defeat a deterministic rule that hedges by spreading its unit across all of them.

Where the constant comes from #

The constant $1 - 1/e$ appears here for a reason close to the one that makes it appear in the problem of derangements and the secretary problem: in each case a random order is being compared with a best one, and the chance that a particular good opportunity has already been used up by the time it is wanted comes out, in the limit, as a power of $e$.

The cleanest modern proof is a charging argument. Give each place a random number $y$ between 0 and 1 — equivalent to a random ranking — and imagine that when an arrival takes a place of number $y$, it pays $e^{y-1}$ to the place and keeps the rest of one unit for itself. The payments are chosen so that, for every edge of the best matching, the arrival and the place at its ends together expect to collect at least $1 - 1/e$, whatever else happens. Summing over the edges of the best matching then shows that RANKING’s total is at least $1 - 1/e$ times the best. The function $e^{y-1}$ is exactly what makes the guarantee the same for every edge, and its integral is where $1/e$ enters.

Karp, Vazirani and Vazirani’s original proof had a gap that went unnoticed for nearly two decades; it was repaired in 2008, and several short proofs followed, including the charging argument sketched here. The theorem itself was never in doubt; the episode is a reminder that a result can be widely used and correct long before its proof is.

One graph, many outcomes #

An expected share is an average, and the average hides a spread.

The outcomes cluster tightly around the mean: most rankings match 12 or 13 of 20, a few match 11 or 14, and the extremes are rare. The concentration is not an accident. Changing the rank of one place changes RANKING’s matching along a single alternating path, so it changes the matched count by at most one, and quantities with that property concentrate around their means by the same bounded-differences inequality that governs many other random counts. So the guarantee is not only an average; for large graphs it is very nearly what happens every time.

The spread is also a reminder of what the guarantee does not say. On any particular graph, some rankings do much better than $1 - 1/e$ and a few do somewhat worse than average; the theorem bounds the average over rankings, for the worst graph. An operator running the algorithm once on one day’s arrivals gets one draw from a distribution like this, and the tightness of the distribution is what makes the average a useful promise.

Advertisements, and the value of a slot #

The problem is not academic. When a search engine shows a page, it must choose, instantly, which advertiser’s advertisement to place in each slot, with advertisers arriving and budgets depleting over the day, and without knowing which queries are still to come. In 2005 Aranyak Mehta, Amin Saberi, Umesh Vazirani and Vijay Vazirani gave an algorithm for this budgeted version whose guarantee is again $1 - 1/e$, and the charging function that proves it is the same exponential. The generalisation adds weights and budgets; the obstruction — an adversary who knows which choices will be needed later — and the defence — commit to a random ordering of priorities in advance, or spread each decision across advertisers according to how much of their budgets remain — are the ones in the triangle. The budgeted algorithm is water-filling in disguise: an advertiser that has spent more of its budget is discounted, exactly as a fuller place receives less water.

In practice arrivals are rarely adversarial. If the arrival order is random rather than chosen by an adversary, RANKING does better — its guarantee rises above 0.69 — and if the arrivals are drawn from a known distribution, better still. How much better, exactly, is the subject of a large current literature.

What the figures cannot prove #

The ratio figure is a simulation of one graph family. It shows RANKING approaching $1 - 1/e$ on triangular graphs, which is the worst case. That no other graph does worse is Karp, Vazirani and Vazirani’s theorem, and no finite simulation over one family can show it.

The lower bound for every algorithm is a theorem about expectations. The claim that no online rule beats $1 - 1/e$ is proved by exhibiting a random distribution over triangular graphs — randomly relabelled — on which every deterministic rule does no better, and then applying a minimax principle. The figures show only RANKING’s side of that game.

Water-filling is described, not drawn. The fractional rule’s guarantee is stated in the text; no figure computes it, and its $1 - 1/e$ is a separate theorem about a separate algorithm that happens to share the constant.

The half-bound figure uses one bad rule on one graph. Its five-of-eight is an instance; the proof that every maximal matching is at least half a maximum one is the argument in the text, and the proof that no deterministic rule can do better is the two-vertex gadget, repeated.

Still open: when the arrivals are not adversarial #

For adversarial arrival orders the story is complete: one half for deterministic rules, $1 - 1/e$ for randomised ones, both tight. The open questions are about kinder models. When the arrivals come in a uniformly random order, RANKING’s exact guarantee is known to lie between about 0.696 and 0.727, and closing that interval is an open problem. When both sides of the graph arrive online, or edges have weights, or each place can be used several times, the best possible guarantees are known only within ranges, and in several cases it is not known whether any algorithm beats the simple greedy one.

There is also a question about how much randomness is needed. RANKING uses a random permutation — a great deal of randomness — and it is not known in general how few random bits suffice to beat one half by a given margin, or whether some structured, easily generated family of rankings is as good as a uniformly random one. For general graphs in which both sides arrive over time — riders and drivers both appearing and disappearing — even the right model is argued over, and the guarantees known are far below $1 - 1/e$.

The price of not knowing the future #

The best matching of a graph can be found efficiently when the graph is known. Revealed a vertex at a time, it cannot be found at all, and the question becomes how much of it can be guaranteed. Half, with any rule that never wastes an available edge; $1 - 1/e$, with a single random ordering decided before anything arrives; and no more, whatever the rule. The loss of $1/e$ — about 37% on the worst graphs — is the precise price of committing without seeing what comes next, and it is the same constant that governs when to stop looking for the best candidate in a stream, for much the same reason.

It is worth setting beside the secretary problem directly. There one candidate is chosen from a stream and the best rule succeeds with probability $1/e$; here many arrivals are matched and the best rule keeps $1 - 1/e$. Both numbers measure the same thing from opposite sides — what fraction of the value is lost, or kept, by a decision-maker who must act on each arrival before seeing the rest — and both are achieved by rules that commit early to a random reference point and then act consistently against it.