Longer Lists Yield Better Matchings Conference: ; ;
Yuri Faenza and Aapeli Vuorinen, IEOR, Columbia University · 2025
Read Longer Lists Yield Better Matchings Conference: ; ; by Yuri Faenza and Aapeli Vuorinen, IEOR, Columbia University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06217.txt.
Introduction
Faenza and Vuorinen study matching markets where people rank only some of their options. Many real systems, such as school choice, ask for ranked lists, but in large markets nobody can rank every option. Their 2025 paper studies a simple rule where people pick in a fixed order, each taking the best school left on their list, with lists drawn at random.
The main result says that when students care most about getting any school on their list, longer lists leave every student at least as well off once the market is large. Schools also always gain from longer lists in this model. The authors also track how list length affects the rank of the school each student lands. They advise designing such markets with lists as long as is practical.
Catalog record
| CREATOR | Yuri Faenza and Aapeli Vuorinen, IEOR, Columbia University |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06217
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Longer Lists Yield Better Matchings Conference: ; ; Yuri Faenza and Aapeli Vuorinen, IEOR, Columbia University Abstract . Many centralized mechanisms for two-sided matching markets that enjoy strong theoretical properties assume that the planner solicits full information on the preferences of each participating agent. In particular, they expect that participants compile and communicate their complete preference lists over agents from the other side of the market. However, real-world markets are often very large and agents cannot always be expected to even produce a ranking of all options on the other side. It is therefore important to understand the impact of incomplete or truncated lists on the quality of the resultant matching. In this paper, we focus on the Serial Dictatorship mechanism in a model where each agent of the proposing side (students) has a random preference list of length d d , sampled independently and uniformly at random from n n schools, each of which has one seat. Our main result shows that if the students primarily care about being matched to any school of their list (as opposed to ending up unmatched), then all students in position i ≤ n i\leq n will prefer markets with longer lists, when n n is large enough. Schools on the other hand will always prefer longer lists in our model. We moreover investigate the impact of d d on the rank of the school that a student gets matched to. Our main result suggests that markets that are well-approximated by our hypothesis and where the demand of schools does not exceed supply should be designed with preference lists as long as reasonable, since longer lists would favor all agents. 1. Introduction One of the central objectives of theoretical research in matching markets is to design mechanisms and rigorously establish whether they, along with their outcomes, satisfy desirable properties. Depending on the specific market, the focus may be on concepts such as strategy-proofness, one- or two-sided optimality, or equilibria. These and other properties are often viewed as justifications for applying such mechanisms in practice, under the expectation that the valuable theoretical features will persist in the real world. However, in many applications, the assumptions that are necessary for such properties to hold may not be satisfied. For example, while in a static two-sided market one can compute a stable assignment efficiently, in real-world markets arising in public school allocation, a substantial number of agents often enter or leave the market after the first assignment has been decided (see for example ( Ashlagi et al. 2023 ) ). The goal of the central planner becomes therefore less well-defined and, depending on the mathematical formalization, may lead to computationally hard problems, see for example ( Bampis et al. 2023 ; Faenza et al. 2024 ; Faenza et al. 2025 ; Miyazaki and Okamoto 2019 ) . In this paper, we focus on one of the main restrictions encountered in real-world markets: imposing a limit on the maximum length of preference lists of agents. Such limits are common, for instance in school markets. While Gale and Shapley’s Deferred Acceptance algorithm ( Gale and Shapley 1962 ) assumes that students are allowed to list all schools they deem acceptable in their preference list, education departments traditionally impose a strict maximum limit on the number of schools an applicant may list 1 1 1 These include programs in Spain and Hungary ( Calsamiglia et al. 2010 ) , Australia ( Artemov et al. 2017 ) , as well as some cities in the United States. . This restriction is motivated by practical concerns such as the additional burden that acquiring more information poses to schools and students alike. However, the effects of restricting the length of preference lists are significant on the properties of the mechanism and of its outcome. For instance, while the original Deferred Acceptance mechanism is strategy-proof for the proposing side, its implementation with bounded-size lists leaves room for strategic behavior of students. This is not merely a theoretical concern, but has practical implications ( Calsamiglia et al. 2010 ) which are well known to central planners. For instance, until the school year 2024/2025, the Department of Education of New York City limited 2 2 2 This rule was changed for the school year 2025/2026, and applicants can now list as many schools as they want. the number of schools in student preference lists to 12 and suggested that the applicants be strategic by reserving some of the slots for “safe schools” (schools where the student has high priority, and as a result, a high probability of being accepted) ( DOE 2023 ) . When deciding the length of preference lists in a matching market, it is therefore essential to carefully balance practical concerns with the potential efficiency losses that can result from limiting information exchange. A correct estimation of the efficiency loss induced by short(er) lists can therefore guide a market designer in striking the right trade-off. 1.1. Our Contributions In this paper, we focus on the impact that the length of preference lists has on the quality of the output matching in the Serial Dictatorship mechanism for two-sided matching markets. In our theoretical model, we assume that the proposing side (students) have preference lists drawn uniformly at random and that the disposing side (schools) have only one seat (we later discuss how these assumptions can be relaxed in our computational experiments). The concept of “quality of a matching” can be defined in multiple ways; we mostly focus on the probability that a student will be matched to any school of their preference list as opposed to remaining unmatched. This is justified by the fact that if a student cannot be matched to any school of their preference list, they completely lose control on the school they are matched to (in many markets, such students are assigned a remaining seat arbitrarily at the whim of the central planner). This seems by far the worse outcome for a student. We moreover study the probability that a student is matched to their top k choices, a popular measure of quality of a matching 3 3 3 For instance, the National Resident Matching Program, while using the Deferred Acceptance algorithm, explicitly reports the number of applicants matched to their first choice ( NRMP 2023 ) , while the Boston Mechanism directly aims at maximizing the number of students matched to their first choice. . 1. Comparative analysis of balanced markets. In our model, the probability p_{i} that a student i is matched to any school is determined by two opposite drivers. On one hand, the longer the preference lists, the more schools will have been matched to students with priority higher than i , decreasing p_{i} . On the other hand, longer preference lists imply that a student has a larger list of acceptable schools, leading to an increase in p_{i} . Our main result is that under the Serial Dictatorship mechanism, when the number of schools n is large enough, the latter driver dominates for all students in positions i\leq n : that is, p_{i} increases with the length of lists. This is our Theorem 2.1 . In particular, if the demand of schools does not