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

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 \ge \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\le 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.