Matching when the arrivals are shuffled

Matching as they arrive set out the online version of Hall’s problem. Applicants arrive one at a time, each qualified for some of the posts; each must be given a free post it is qualified for or turned away, at once and for good. Any rule that never turns away an applicant who could be placed matches at least half as many as the best assignment made with hindsight. An adversary who knows the rule and chooses the order of arrivals can hold it to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post — the rule called RANKING, of Karp, Vazirani and Vazirani — and the guarantee rises to $1 - 1/e$, about 63%, which no online rule can beat against an adversary.

All of that assumed the adversary controls the order. In most real settings it does not. Search queries, riders requesting cars and patients arriving at a clinic come in an order nobody arranged, and a natural model is that the order is random — every ordering equally likely — even if the graph itself is as unfavourable as possible. That essay ended by naming this as the open case. This essay measures what changes. The answer has a surprise in it: shuffling the arrivals and shuffling the posts are the same thing, seen from opposite sides.

Where the adversary’s half came from #

The graph in the figure is the one the adversary uses. Arrivals and places are numbered 1 to 8; arrival $t$ is qualified for place $t$ and every place after it. Arrival 1 can take anything, arrival 8 only place 8. The best assignment gives each arrival the place with its own number and matches all eight.

The rule in the figure is a fixed greedy rule: each arrival takes the free place furthest down the list it is qualified for. In the adversary’s order, top row first, arrival 1 takes place 8, arrival 2 takes place 7, and so on. By the time arrival 5 comes, the four places it could use are gone, and so are those of everyone after it: four of eight matched. The early arrivals, the ones with many options, used up exactly the places the later arrivals, with few options, needed.

That is the whole mechanism. An adversary’s power lies in sending the flexible arrivals first, so the rule spends the scarce places on people who could have gone anywhere. A random order cannot be arranged that way. In the right-hand panel, arrival 6, whose only options are places 6 to 8, happens to come second and is served before the flexible arrivals have used them up; five are matched. Some of the picky arrivals come early, and the rule’s mistakes cost less.

The plainest rule, shuffled #

How much less can be measured on the same graph at every size.

In the adversary’s order the greedy rule matches exactly half at every size. In random order, with the same rule and the same bad list of places, it matches 0.668 at 8 a side and 0.633 at 256, falling towards $1 - 1/e \approx 0.632$. Gagan Goel and Aranyak Mehta proved in 2008 that this is a floor on every graph: greedy in random order, with any fixed ranking of the places, matches at least $1 - 1/e$ of the best, in expectation, on every bipartite graph. And the triangle shows the floor is reached.

The second curve in the figure is RANKING in the adversary’s order — the result of the previous essay — and it lies exactly on top of the first. That is not a coincidence about this graph. The two procedures are the same procedure.

Two sides of one procedure #

RANKING takes the arrivals in their order and gives each its best-ranked free place, the ranking random. Random-order greedy takes the arrivals in a random order and gives each its best-ranked free place, the ranking fixed. Each has one random ordering and one fixed one, but on different sides of the graph. The remarkable fact is that the sides can be exchanged.

Run the procedure as usual: arrivals in their order, each taking the best-ranked free place. Now run it the other way: let the places “arrive” in order of their rank, and give each the earliest-arriving free applicant it could serve. The two procedures produce exactly the same matching — not the same size, the same edges — in the example drawn and in every one of 2,000 random graphs tried, with random orders and rankings. The reason is stability. Suppose every arrival prefers places in the order of the one ranking, and every place prefers arrivals in the order they arrive. Then there is exactly one matching in which no arrival and place that could be paired would both rather be with each other than with their partners — a stable matching, with every preference read off a single list on each side — and each of the two procedures produces it: whoever chooses first in either procedure is getting its favourite remaining partner, and nobody it passes over could have done better with it. The matching does not know which side was doing the choosing.

So random-order greedy with a fixed ranking of the places is RANKING with the sides exchanged: the random order of the arrivals plays the part of the random ranking, and the fixed ranking of places plays the part of the arrival order. Every guarantee proved for one is a guarantee for the other. That is how Goel and Mehta got their floor: the $1 - 1/e$ that Karp, Vazirani and Vazirani proved for RANKING against any order becomes $1 - 1/e$ for greedy in random order against any ranking. And the triangle, which is the adversary’s worst case for one, is the worst case for the other. It is the same proof, and in both versions the constant comes from the same calculation: the chance that a shuffle leaves something undisturbed, which is where $e$ enters every problem of this kind.

Order, not the rule, was doing the damage #

The averages hide how unusual the adversary’s order is.

On the 16-a-side triangle the greedy rule averages 10.4 of 16 in random order, 64.8% of the best. An order as bad as the adversary’s, matching only 8, turned up in 90 of 20,000 shuffles, under half a per cent of the time; most orders match 10 or 11. The rule is the same in every one of them, and so is the graph. What separated the half from the two-thirds was the order alone.

That is the practical message of the random-order model. A rule that looks dangerous in the worst case can be very safe when nobody is arranging the input, and the measure of how safe is a statement about a distribution over orders rather than about a single worst order. The same shift underlies the secretary problem, where a decision maker facing candidates in random order can pick the best with probability $1/e$ — and facing an adversary’s order could do no better than chance — and the prophet problems of half of what an oracle takes, where a random order raises what a single threshold can guarantee. Random order is the weakest assumption about the world that still takes the adversary’s main weapon away.

Two arrivals, worked by hand #

The smallest case shows every effect at once. Take two arrivals and two places: arrival 1 is qualified for both places, arrival 2 only for place 2. The best assignment matches both. Let the fixed greedy rule prefer place 2 whenever it has the choice — the bad preference, since place 2 is the one arrival 2 needs.

In the adversary’s order arrival 1 comes first, takes place 2, and arrival 2 is turned away: one matched, half the best. In random order there are two orders, equally likely. If arrival 1 comes first the same thing happens and one is matched. If arrival 2 comes first it takes place 2, the only place it can use, and arrival 1 then takes place 1: both matched. The average is one and a half, three quarters of the best — the value the search figure reports at $k = 2$ for greedy in random order.

Now shuffle the preference too, as RANKING does. Half the time the ranking prefers place 1, and then arrival 1 never takes the scarce place and both are always matched. Half the time it prefers place 2, and the arrival order decides as before, averaging one and a half. Together that is $(2 + 1.5)/2 = 1.75$ of 2, seven eighths — again exactly the value in the figure.

The calculation also shows why the shares fall as the graph grows. With two arrivals, a random order puts the picky arrival first half the time. With many arrivals, each picky arrival competes with every flexible arrival that might come before it and take one of its few places, and the chance that its places survive until it arrives shrinks with every competitor. In the limit the surviving share of places obeys the same kind of equation as the share of a shuffled pack left out of place, and settles at a constant with $e$ in it rather than at nought: each new competitor removes a fixed share of what is left, never all of it.

Shuffling both sides #

If one shuffle — of the arrivals or of the places — is worth $1 - 1/e$, two shuffles should be worth more, and they are. The top curve of the triangle figure is RANKING with the arrivals also in random order: 0.796 at 8 a side, 0.895 at 256, and still rising. The triangle is hard for one kind of randomness at a time; it is not hard for both.

The general question is how much the two shuffles together guarantee on the worst graph. Mohammad Mahdian and Qiqi Yan proved in 2011 that RANKING in random order matches at least 0.696 of the best on every graph, and Chinmay Karande, Aranyak Mehta and Pushkar Tripathi found graphs on which it matches only about 0.727. The truth is somewhere in that interval of three hundredths, and nobody knows where.

Why the second shuffle helps is clear from the two-arrival case. The two shuffles repair different weaknesses. A random ranking protects against a bad preference among places — a rule that habitually spends the scarce place first — and a random order protects against a bad sequence of arrivals. On the triangle each weakness alone is enough to drag the rule down to $1 - 1/e$, because the triangle is built to exploit exactly one of them at a time: give it a good preference and a bad order, or a good order and a bad preference, and the result is the same. A graph that defeats both shuffles at once has to make the scarce places hard to protect whichever way the randomness falls, and such graphs are harder to build. The graphs that come closest to the upper end of the interval are larger and more intricate than the triangle, built so that the flexible and the picky arrivals are interleaved and neither a lucky order nor a lucky ranking, on its own, saves the scarce places; finding graphs that do still better is half of the open problem.

The worst cases can be hunted directly on small graphs, where every arrival order and every ranking can be tried.

The exact computation is expensive — at $k = 5$ each graph needs $120 \times 120 = 14{,}400$ runs, every order against every ranking — but it leaves no sampling error. The lowest shares found are 0.875, 0.824, 0.805 and 0.798 for RANKING in random order, and 0.750, 0.722, 0.698 and 0.685 for greedy in random order. At every size, for both rules, the worst graph found was the triangle itself. Small graphs are kinder than the limit: both columns are still well above their asymptotic floors at five a side, and approach them slowly. Exhaustive search on graphs this small cannot locate RANKING’s true worst case inside its band, which is part of why the interval has stayed open: the graphs that push the ratio towards 0.727 are large and structured, and the proofs that hold it above 0.696 need an analysis of how the two random orderings interact that no one has yet made tight.

Where random order is the right model #

Online matching was first studied for job markets, and its largest application has been the allocation of advertisements to search queries: each query arrives, is eligible for some advertisers, and must be assigned immediately. Queries are not chosen by an adversary, but nor are they independent draws from a fixed distribution — their mix changes over the day. The random-order model sits between: it assumes only that the order in which a fixed set of queries arrives is uniformly random, so the guarantee holds whatever the set is.

The results here say how much that assumption buys. For the simplest rule, greedy with any fixed preference among places, it buys the move from $\tfrac12$ to $1 - 1/e$. For RANKING it buys the move from $1 - 1/e$ to at least 0.696. Both are guarantees on the worst graph; on typical graphs the shares are much higher, as the spread figure suggests. In practice the gap between the worst case and the observed performance is large, and the theorems are valued less for their numbers than for saying which rules cannot be made to fail badly.

There is a cost hidden in the second shuffle. RANKING needs its random ranking chosen before any arrival, so it is a randomised rule, and its guarantee is in expectation over its own coin flips. Random-order greedy needs no coins at all: the randomness is supplied by the world. When the arrival order really is random, the plain greedy rule gets RANKING’s adversarial guarantee for free.

What Hall’s condition becomes online #

The theorem that started this sequence, one bottleneck and nothing else, says that a perfect matching exists unless some group of applicants has too few posts between them. Offline, the best matching is found by a search whose failure certifies the bottleneck. Online, the bottleneck can be created by the rule itself, by spending a scarce post on a flexible applicant. The adversary’s half is the cost of doing that at every step; the random order’s $1 - 1/e$ is the cost of doing it only when the flexible applicant happens to come first, and the calculation of how often that happens — a share of the places surviving to the arrivals that need them — is where every constant in this subject comes from.

Still open: closing the interval #

The open question is the one the band in the last figure shows. RANKING in random order matches at least 0.696 of the best and at most about 0.727 on the worst graphs, and which number is right — or whether the answer is some third constant with a description as clean as $1 - 1/e$ — is not known. Closing the interval would need either a better graph, built from the structure of the known hard instances, or a sharper analysis of how a random order and a random ranking interact, which the existing proofs handle with a relaxation that is known to be loose.

Beyond it the random-order model raises its own versions of every problem the adversarial model has. When places can be used several times, when edges carry weights, or when places as well as applicants arrive over time, the best guarantees in random order are known only within ranges, and for several of these it is not known whether any rule beats the greedy one. And there is a question about the model itself: real arrival orders are neither adversarial nor uniformly random, and how much of the random-order guarantee survives an order that is random but slightly biased — by time of day, by a few correlated arrivals — is being worked out, so far only for particular forms of bias.