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.
- Preferences: Typically assumed to be iid from a fixed distribution. Popular distributions are
- Deterministic (D): students share a common ranking of schools.
- Uniform (U): student lists are drawn uniformly at random.
- Popularity-based (P): lists are generated by sampling without replacement from a fixed distribution over schools.
- Quality-based (Q): utility of student \(s\) for school \(h\) is \(q_h + v_{sh}\), where the \(v_{sh}\) are iid.
- General (G): lists drawn iid from an arbitrary distribution.
- Priorities: Same as for student preferences.
- School Seats:
- (C): Each school has C seats.
- (G): No assumptions.
Often, these three parameters suffice to describe the setting.1 However, in some cases there are other important assumptions to specify. For example:
- Market Imbalance: In queueing theory, the ratio of the arrival rate to service rate (“utilization”) is an important parameter. The analog in matching theory is the ratio of students to seats, which I propose to denote by \(\rho\).
- List Length: Many papers assume complete lists (C), which I propose to use as the “default.” Other possibilities include:
- (B): Bounded.
- (M): Memoryless (geometric).
- (D): Deterministic.
- (ER): Erdos-Renyi compatibility graph (list length follows Binomial distribution)
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) | |
| U/U/C/B | ||
| 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 | |
| Ashlagi,Kanoria,Shi | ||
| Liu, Pycia (2016) | ||
| Lee, Yariv | ||
| Lee (2017) |
Knoblauch: Marriage matching and gender satisfaction
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).↩