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

## 2020/08/30

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.