An Analogy Between Matching and Queueing, Part III: A Striking Correspondence

Nick Arnosti


Coming Soon!

... OR NOT.

Let's study a fluid model of an Erlang A queueing system. Agents arrive at rate \(\lambda\), depart at rate \(d\), and are serviced at rate \(\mu\). The fluid model predicts a queue length \(L\) satisfying \(Ld + \mu \geq \lambda\) with equality if \(L > 0\), implying \(L = (\lambda - \mu)_+/d\). By Little's Law, average time in system is

\[T = \frac{L}{\lambda} = \frac{(1 - \mu/\lambda)_+}{d}. \]

Now, let's study the Azevedo-Leshno fluid model with iid priorities. To match exponential departures, assuming that student list length follows a geometric distribution with mean \(1/q\) (so the probability of listing more than \(k\) schools is \((1-q)^k\)). Suppose that \(n\) students compete for \(m\) seats. If \(n \leq m\), then the model predicts that every school has a cutoff of zero (\(p = 1\)), so students experience no rejections. Otherwise, the success probability is set such that the expected number of students who match is \(m\). After summing a geometric series, we get the following consistency condition for \(p\): \[\frac{p}{1 - (1-q)(1-p)} = \frac{m}{n}.\] The average number of applications sent by each student is \(\frac{1}{1 - (1-q)(1-p)}\), and the average number of rejections experienced by students is \(\frac{1-p}{1 - (1-q)(1-p)}\). Using the consistency condition, solving for \(p\) and substituting, we see that the average number of rejections \(R\) is \[R = \frac{(1 - m/n)_+}{q}. \]

Note that the equations for average wait \(W\) and average rank \(R\) are exactly parallel, with number of students = arrival rate, number of seats = service rate, and average list length = average time to departure absent service.