Matching workers who will not wait

The classical theory of assignment begins with the whole table. The cheapest way to pair workers with jobs reads all the costs and then computes; prices that clear the market can be adjusted in rounds until everyone is content. Many real allocations have to be made without the table. A shopper arrives and the page has a moment to show one advertisement. A driver opens the app. A kidney is available tonight. Each arrival shows what it would accept, and it must be served or lost before the next arrival is known.

So here is the plainest version. There are $n$ jobs, known in advance. Workers arrive one at a time. Each worker shows which jobs would suit, and the rule must immediately give that worker one free suitable job or send that worker away, and neither decision can ever be revised. The score is the number matched, against the largest number that could have been matched with full knowledge.

In 1990 Richard Karp, Umesh Vazirani and Vijay Vazirani answered this with a theorem whose exact constant has been reproved half a dozen ways, and whose algorithm is a sentence long. Choose a random order of the jobs before anyone arrives, and always give each worker the first free suitable job in that order. That rule achieves $1 - 1/e$, about 63.2%, and nothing can beat it.

Half is automatic and half is the limit of a fixed rule #

Any rule that never turns away a worker who has a free suitable job gets at least half of the best matching. Take the best matching with hindsight. Each pair in it has a worker and a job. When that worker arrived, either the job was still free, in which case the rule matched the worker to something, or the job had been taken, in which case some worker has already used it. In either case the pair has at least one end used by the rule. Each match the rule makes uses one worker and one job, and so it can account for at most two pairs. So the rule’s matches are at least half of the best.

The figure shows why that cannot be improved by any rule that is fixed in advance. The market is upper triangular: worker 1 suits every job, worker 2 suits all except the first, worker 3 all except the first two, and so on, with the last worker suiting only the last job. With hindsight, worker $i$ takes job $i$ and everyone is matched. But a rule that is fixed is predictable, and an adversary who knows it can name the jobs so that its first choice is always the one that will be most wanted later. In the figure the rule gives each worker the last suitable job, and half the workers later find nothing. Job labels are arbitrary, so that is what an adversary can make any deterministic rule do. So without randomness the answer is exactly one half.

Randomness, drawn at the wrong moment #

The obvious repair is to choose at random. At each arrival, give the worker a free suitable job chosen evenly among them. On the triangle that works well, and it would be natural to expect this to be the answer. It is not, and the failure is instructive, because it distinguishes two things that sound the same.

Consider a market in two blocks. There are $m$ workers who arrive first, each of whom suits one job of their own and also all $m$ jobs of a second block; and $m$ workers who arrive later, each suiting exactly one job in that second block. With hindsight everyone can be matched: the first group take their own jobs and the second group take theirs. Under a fresh random choice, each early worker sees one job of their own among $m + 1$ possibilities and very probably takes one from the second block. By the time the second group arrive, the block is almost exhausted and most of them find nothing. The figure records the share matched: 0.6959 with four workers, 0.5846 with twenty and 0.5026 with two thousand, heading steadily to exactly one half.

Now use one order, drawn before anything happens. Every early worker now consults the same list. The list has the workers’ own jobs mixed through the block jobs, and any worker whose own job comes earlier in the list than all the free jobs of the block takes it. As the early workers take block jobs, those are the ones nearest the top of the list, and a job from the block lower down has a smaller and smaller chance of being preferred. The workers’ own jobs start winning. The share settles at about 0.685, at two thousand workers and much the same at a few hundred.

So the two rules use the same quantity of randomness, in the sense that each could be made to look like a fair choice at a given arrival, and they behave completely differently. Drawing a fresh choice at each step is independent of everything earlier, and it spends jobs evenly. Drawing once correlates the choices across the whole run: jobs that are near the top of the list get used, and so a job far down the list is preserved by everyone at once. That correlation is what the theorem pays for. The same remark applies to many other arrangements with a mixture of early and late demand, and it is why the method is called RANKING.

The triangle, computed exactly #

The triangle has a remarkable feature: on it the two random rules give the same expectation, and they give the worst value of all.

The table has been computed in two separate ways. For one fixed order, every one of the $n!$ orders of the jobs was tried at each size to eight workers. For the fresh choice, there is an exact recursion on how many of the still-suitable jobs have been used. At two workers both give $3/2$, at three $13/6$, at four $2.79167$, at eight $5.32121$. They agree in all the digits shown, and this is not a coincidence. In the triangle a worker’s suitable free jobs are interchangeable: the only thing that matters about any of them is that they are free and in range, and whichever one goes, the remaining picture is a shuffled copy of the same one. So choosing by a fixed list and choosing afresh pick the same distribution over futures.

The limit comes from a short differential equation. Measure time $t$ as the fraction of workers who have arrived and let $u(t)$ be the fraction of jobs that are still in range and already used. The job leaving range at each step is used with chance $u/(1-t)$. Each match adds 1 to $u$, so $u' = 1 - u/(1 - t)$ while any free job remains, and the solution is

$$u(t) = -(1 - t)\ln(1 - t).$$

Free jobs in range are $(1 - t) - u(t) = (1 - t)\big(1 + \ln(1 - t)\big)$, which reaches nought at $\ln(1 - t) = -1$, that is at $t = 1 - 1/e$. After that point no arriving worker finds anything: the jobs they could use have all been spent. Every worker up to that time was matched and every worker after was not. The share is $1 - 1/e$, and the recursion at a hundred thousand workers gives 0.632124 against the exact 0.632121.

Why no rule can do better #

The upper bound is now a two-sentence argument, once the interchangeability is noticed. Suppose the job labels of the triangular market are shuffled uniformly at random, and suppose this is known to a rule of any kind, deterministic or randomised, however clever. When a worker arrives, the rule sees a set of labels; the one job that would be most useful later (the one for this worker’s own position) is hidden among them, and by symmetry it is equally likely to be any of the free suitable jobs. So every rule picks the valuable job with exactly the same chance, and the whole distribution of the score is the same for every rule that always matches when it can. The limiting share is the $1 - 1/e$ just computed.

So on this random market no rule beats $1 - 1/e$, and hence on the worst market for any rule the same must hold. This trick, moving the randomness out of the algorithm and into the input, is a form of the minimax principle, usually attributed in computer science to Andrew Yao. It is a duality in which rule and adversary are the two players of a game whose value is exactly $1 - 1/e$, where the rule’s mixed strategy is RANKING and the adversary’s is the shuffled triangle.

The fact that the constant comes out as $1 - 1/e$ deserves a comment, as $1/e$ has appeared before in the same kind of context. It is the chance of picking the best candidate when interviewing them one at a time, where the same irrevocable decisions against an unknown future appear. The same $e$ occurs in random derangements, which is the probability that a shuffle moves everything. It is the natural constant for “each of $n$ things has a chance about $1/n$ of being hit by each of $n$ events”, which is what online allocation under uncertainty keeps coming down to. Other problems in this family, like the prophet’s guarantee of half, have a different constant because the thing that is hidden is a value rather than a place.

Why one order holds everywhere #

That the rule achieves $1 - 1/e$ on every market, and not just on the triangle, is the harder half. The original paper’s proof had an error, found and repaired decades later, and the modern proof is a single swap argument, due to Benjamin Birnbaum and Claire Mathieu and to Gagan Goel and Aranyak Mehta in 2008.

Assume a perfect matching exists. Let $x_t$ be the probability that the job at position $t$ in the random order is taken. Fix a job $j$, at position $t$, and let $w$ be the worker matched to it in the perfect matching. Suppose $j$ is not taken in the run. Then when $w$ arrived, $j$ was free, so $w$ must have taken something earlier in the list, at a position before $t$. And here is the swap: moving a single job in the order changes the run in a controlled way, so that this conclusion holds regardless of where $j$ was placed. So the event that $j$ is free at position $t$ implies that $w$ is matched at a position before $t$, and those events can be compared across the $n$ possible positions of $j$ to produce a single inequality:

$$1 - x_t \le \frac{1}{n}\sum_{s \le t} x_s.$$

The chance that the job at position $t$ goes untaken is at most the average chance that the first $t$ positions are used. In the continuous limit, with equality, this is $1 - x(t) = \int_0^t x(s)\,ds$, whose solution is $x(t) = e^{-t}$. The area under that curve is exactly $1 - 1/e$.

The figure measures this on the triangle with 400 workers. The chance a job is taken falls smoothly from 0.977 at the front of the list, through 0.592 in the middle and 0.383 at the back, and it lies on $e^{-x}$ throughout. That is the sign that the inequality is an equality on this instance, and that the triangle is really the worst case rather than merely a bad one. The rule’s guarantee and the triangle’s ceiling are the same curve.

A later proof makes the connection to prices and their dual explicit. Nikhil Devanur, Kamal Jain and Robert Kleinberg gave in 2013 a proof by linear programming: pay a job in position $t$ the price $e^{t - 1}$ when it is used, and charge the worker the remainder. The worker and job totals form a feasible point of the dual of the matching programme, scaled by $1 - 1/e$, and that bounds the optimum directly. The random order has become a random price list, with the job at the top of the list being cheap, so it goes first. It is the same observation that made the market prices clear an assignment, now used when bidders arrive one at a time and the list of prices is fixed in advance.

One run, and what the rule knows #

The rule has essentially no memory, which is the last thing worth seeing about it. It does not record the arrivals, it does not count anything or estimate anything, and it has no idea that a worst case has a name.

In this run seven of the twelve workers are matched. The shaded region shows what is suitable, shrinking down the rows as jobs leave the range. The taken squares run from left to right as the front of the list is used up, and the workers who come late find only used jobs in their short ranges. Reading down a column, a job at the left is taken early and a job at the right often stays free. Those are the bars of the previous figure seen in one instance.

The instance also suggests why worst-case analysis has such a pessimistic flavour. The triangle is a highly unusual market. Almost all the jobs are wanted by many workers, but the demand becomes concentrated, and a job’s being desirable late is invisible early. Most real markets are nothing like that.

On random markets, with each worker–job pair suitable independently, both rules are well above the guarantee. They are close to each other, and hardest to tell apart when the market is moderately dense. The lowest shares of the best matching are near 0.85, at about three or four suitable jobs per worker, and rise on both sides: sparse markets are easy because almost any match is right, and dense markets are easy because plenty of jobs remain. The market that matches the theorem has to be carefully built.

Where this has been used #

The reason the problem was revived is a business. Aranyak Mehta, Amin Saberi and the Vazirani brothers, in 2005, took a version in which the jobs are advertisers with budgets and the workers are search queries. In this AdWords problem, the naive method of giving each query to the highest bidder has a guarantee of one half, and a bidder’s remaining budget should discount their bid by a factor $1 - e^{\text{spent fraction} - 1}$. This has the same form as the price above. It achieves $1 - 1/e$ again, and the constant turned up in the economics of an industry.

The other refinement is arrival order. When an adversary chooses the order, the triangle applies. When the workers arrive in random order, RANKING is known to do better: Mohammad Mahdian and Qiqi Yan proved at least 0.696 in 2011, and Chinmay Karande, Aranyak Mehta and Pushkar Tripathi showed that no analysis of it can exceed 0.727. Between those numbers the truth is unknown. And when the input is drawn from a known distribution, as the prophet problems assume, better than $1 - 1/e$ is possible again, with a chain of papers pushing the constant up through values such as 0.73.

What is computed and what is cited #

The computed parts of this essay cover the triangle in detail and the two-block market by simulation. On the triangle, the fixed-order rule was evaluated by every order up to eight workers, and the agreement with the exact recursion for the fresh choice was tested digit by digit. The large-$n$ values come from a mean-field version of that recursion, exact in the limit, with a difference from $1 - 1/e$ on the order of the rounding at $n = 100{,}000$. The curve $e^{-x}$ is not fitted: it comes from the inequality.

The two-block shares are simulations, using up to 4,000 runs at small sizes and 60 at the largest, so their last digit has an error of a few units. The random-market figure rests on 40 markets per density, again with sampling error. The proof of the swap argument was stated in outline and was not checked by any computation, nor were any of the cited constants above 0.632, such as 0.696 and 0.727, and the error in the original paper’s analysis is taken from the published corrections.

Still open: how much better random arrivals are #

In the adversarial model the answer is complete: $1 - 1/e$ for matching with an adversary and any kind of rule. As soon as the adversary has less power, the exact constant disappears. What is the best guarantee when workers arrive in random order? The upper bound for any rule is around 0.823, and RANKING’s guarantee lies between 0.696 and 0.727. Neither end looks tight, and it is not even known whether RANKING is the best rule in that setting.

The gap has a clear technical origin. Under random arrivals both the workers and the jobs are shuffled, so two orders are random at once and the simple swap argument has to control both. The analysis that produces 0.696 uses a factor-revealing linear programme, with a value computed rather than derived. So the exact constant, if a clean one exists, has not shown itself. It is much like the difference between one lottery over assignments and two in the offline theory, where a second source of chance changes the structure of the problem rather than the arithmetic.

When the randomness was drawn #

The same amount of chance gives one half or $1 - 1/e$ depending on when it is drawn. Choosing afresh at each arrival spreads the risk evenly and falls to one half on the two-block market, at 0.5026 by two thousand workers. Drawing one order in advance makes the whole run agree about which jobs to spare. The chance a job is used then falls as $e^{-x}$ along the list and the share cannot fall below 0.632. On the shuffled triangle every rule scores exactly the same, so no rule can do better.

This is the same structure as the prices in the classical assignment problem. A price list is a commitment made once, which is what stops one early decision from draining the whole market. In the offline problem it can be adjusted in rounds to clear the market exactly; in the online problem it has to be chosen blind, at random, and the $1/e$ is the cost of the blindness.