I often find myself explaining stable matching to researchers who have little background in matching, but are familiar with queueing theory. Through these conversations, I have come to realize that there are a lot of parallels between queueing and matching!
This is the first of several blog posts that will present an extended analogy between these fields. It describes the advantages and disadvantages of several several classes of models (deterministic, stochastic, and fluid limit) that have been used for both queueing and matching. The final section alludes to a new type of matching model, which I believe has many advantages over traditional approaches.
My meta-goals for these posts are to (i) help queueing theorists understand the current state of the matching literature, and (ii) suggest to matching theorists that there may be a lot to learn from queueing theory (which I view as the more developed field).
Deterministic Finite Models
For decades, most matching research studied deterministic models (this book offers a fairly comprehensive survey of early work).
The advantage of this approach is that it doesn’t require any assumptions on student preferences or school priorities. This makes it possible to prove very general results. For example, adding a student to a matching market always weakly hurts every other student.
One drawback of this approach is that with weaker assumptions come weaker conclusions. If we ask “How much does the addition of a new student hurt others?”, there is no good answer. In some cases, adding a student might not displace anyone else; in others, it has a dramatic effect (as I discuss in more detail in this blog post). For any given preference profile we can answer this question, but specifying a full preference profile is cumbersome: the input is too high dimensional for clean insights.
In queueing, the analogous approach would be to specify each individual arrival time and service time. Again, we could derive a few general results (i.e. adding a new customer weakly hurts all others), but we would quickly run out of interesting things to say. Tellingly, few queueing papers work with deterministic models.
Stochastic Models + Asymptotics.
Instead, queueing is traditionally studied using stochastic models, in which arrival and service processes are described by a few parameters. Additionally, most analysis focuses on steady-state outcomes (that is, the average experience of a large number of customers). Jointly, these modeling choices enable insightful analysis of each parameter’s effect on metrics such as the average waiting time. One of the most celebrated insights is that wait time “blows up” as utilization approaches one: small changes in arrival rate can have a dramatic effect on average waiting times.1 2
The analogous approach in matching theory is to study markets where preferences and priorities are drawn randomly, and to study outcomes as the number of students and seats grow. This approach was pioneered by Don Knuth in this monograph, but was slow to catch on. Recently, however, it has become ubiquitous in the matching literature.3
Although stochastic models offer the advantage of clean insights, they often require strong assumptions in order to maintain tractability. In queueing, it’s common to assume Poisson arrivals and exponential service times. Over decades, these assumptions have gradually been relaxed, but analysis of “realistic” queueing systems (i.e. nonstationary arrivals, or queueing networks) remains beyond reach. Analyses of random matching markets frequently assume that preferences and priorities are uniformly random, or identical.
Fluid Models
Queueing theory moved beyond restrictive assumptions by using fluid limits. In essence, these models ignore stochasticity, replacing arrival and service times with their expected values. This is much more tractable than stochastic analysis, and can be shown to provide a good approximation in certain cases (i.e. in systems with a high arrival rate and many servers). Fluid models of queueing are extremely widely used.
By comparison, fluid matching models are in their infancy. Eduardo Azevedo and Jacob Leshno wrote a beautiful paper which uses a fluid model to predict school cutoff scores (that is, the lowest priority student accepted to each school). This model remains tractable with complex preferences and priorities. Just as fluid models of queueing accurately approximate stochastic models with high arrival and service rates, their fluid matching model provides a good approximation of outcomes in random matching markets where many students match to each school.
In general, however, the approximation is far from perfect. Because fluid models ignore stochasticity, they tend to make predictions that are much more optimistic than those from the corresponding stochastic models. For example, fluid models of queueing predict no waits if the service rate exceeds the arrival rate, and the fluid matching model predicts that every student will get their first choice if student preferences are uniformly distributed and the number of seats exceeds the number of students.
Furthermore, their model cannot quantify the uncertainty facing students in the stochastic model. This is shown in the left panel of Figure 1, which displays their model’s predicted cutoff score alongside the empirical distribution of realized cutoff scores. Unless school capacities are very large, cutoff scores vary significantly, and cannot be described by a single number. Hence, students with priority scores just above their predicted cutoff have a significant chance of being rejected.
A New Modeling Approach
I’ve recently been working on a new model of stable matching, which incorporates stochasticity, but retains much of the tractability of Azevedo and Leshno’s fluid model.4 Whereas their model predicts a deterministic cutoff score, mine predicts the full distribution of cutoff scores, shown in Figure 1.5 However, now isn’t the time to go into details about this new model – I’ll save that for a future post.
Figure 1: The distribution of cutoff scores required for admission in the setting considered by Azevedo and Leshno. On the left, simulation results from Azevedo and Leshno (2016). The blue line shows the empirical average cutoff score, with the red lines representing the \(5^{th}\) and \(95^{th}\) percentile of the empirical distribution. Their model predicts a deterministic cutoff score, shown by the black dotted line. This does not capture the uncertainty in cutoffs, which is significant unless capacities are large. My proposed model of stable matching predicts the distribution of cutoff scores: the right panel shows the average, \(5^{th}\) percentile and \(95^{th}\) percentile of the predicted distribution.
This idea is the focus of the “Managing Waiting Times” unit of my MBA Operations Management class.↩
The third post in this series explores an analogous finding for matching markets.↩
In queueing, stochastic analysis is so common that it was helpful to develop a shorthand (known as Kendall’s Notation) for specifying assumptions. I believe that the matching literature may have reached this point: the second post in this series proposes analogous notation for matching markets.↩
Independently, Ton Dieker has been developing a somewhat analogous model for queueing. His QPlex software uses this model to estimate transient outcomes in queueing networks. I hope that he manages to write up and share a document sharing more details soon!↩
Results are for the following setting. \(20 C\) students compete for spots at 10 colleges, each with capacity \(C \in \{1, 5, 10, 25, 50, 100, 200\}\). Students have uniformly random preferences over colleges. Each student’s priority score at each college is the average of the student’s quality (drawn U[0,1]) and an idiosyncratic match value (drawn U[0,1] across student-college pairs). The quality terms introduce (imperfect) correlation in colleges’ assessment of students. Each realization of preferences and priorities induces a minimum “cutoff score” required for admission to each college. Figure 1 shows the distribution of these cutoff scores.↩