An Analogy Between Matching and Queueing, Part II: Kendall Notation for Matching

Nick Arnosti


There is a growing literature on random matching markets, and it can be difficult to keep track of the assumptions made by each paper. In queueing theory, Kendall’s notation offers a convenient shorthand. For example, an M/D/1 queue is one where arrivals are Memoryless (exponentially distributed inter-arrival time), service times are Deterministic, and there is 1 server. The goal of this post is to propose analogous notation for matching theory.

There are three key inputs to the Deferred Acceptance algorithm: student preferences, school priorities, and school capacities. Let’s discuss several commonly studied cases for each.

Often, these three parameters suffice to describe the setting.1 However, in some cases there are other important assumptions to specify. For example:

The existing theory of simple matching markets therefore provides accurate predictions about the nature and direction of changes to be anticipated in these matches if the existing NRMP algorithm were replaced by the new algorithm. However the theory offers little guidance as to the magnitude of the changes to be expected, and for this purpose, computational experiments on the data of past matches were also needed.

Paper Setting Result
Wilson (1972) U/G/1, \(\rho <= 1\)
Knuth (1976,1997) U/G/1/C, \(\rho <= 1\) Avg Rank \(\leq H_n\) (Theorem 4)
Pittel (1989) U/U/1/C, \(\rho = 1\) Avg Rank is \(O(\log(n))\)
Knoblauch (2009) U/G/1/C, \(\rho = 1\) Avg Rank is \(O(\log(n))\)
Ashlagi, Kanoria, Leshno (2016) U/U/1/C State results for \(\rho > 1\)
Ashlagi, Kanoria, Leshno (2016) U/D/1/C State results for \(\rho > 1\)
Ashlagi, Nikzad, Romm U/U/C/C Vanishing number of top \(k\) choices (Main Theorem, Proposition 3.1).
U/D/C/C Constant fraction get top \(k\) choice. (Main Theorem, Proposition 3.2)
Ashlagi, Nikzad
Kanoria, Min, Qian (2020) U/U/1/B
Marx, Schummer
Paper Setting Result
Knuth, Motwani, Pittel (1990) U/U/1/C, \(\rho = 1\) Number of Stable Partners \(\approx \log(n)\) whp
Pittel (1992) U/U/1/C, \(\rho = 1\) Number of Stable Partners \(\approx \log(n)\) whp
Roth, Peranson (1999) U/U/1/B, \(\rho = 1\) Number of Stable Partners \(\approx 1\) (Simulations in Section VI)
Immorlica, Mahdian (2005) P/G/1/B Fraction with \(> 1\) stable partner \(\rightarrow 0\). (Theorem 3.1)
Kojima, Pathak (2009) P/G/G/B Fraction with \(> 1\) stable partner \(\rightarrow 0\).
Paper Setting Result
Che, Tercieux (2018) Q/Q/1/G
Che, Tercieux (2019) Q/Q/1/G
Liu, Pycia (2016)
Lee, Yariv
Lee (2017)

Knoblauch: Marriage matching and gender satisfaction

  1. One limitation of this classification scheme is that it cannot describe correlation between preferences and priorities. This seems acceptable, as theoretical models rarely incorporate such correlation (despite its likely prevalence in practice).