Incentives in matching markets: Counting and comparing manipulating agents by Bonkoungou and Nesterov

 Here's a paper that caught my eye in the current issue of Theoretical Economics, Volume 18, Issue 3 (July 2023)

Incentives in matching markets: Counting and comparing manipulating agents by Somouaoga Bonkoungou and Alexander Nesterov

Abstract: Manipulability is a threat to the successful design of centralized matching markets. However, in many applications some manipulation is inevitable and the designer wants to compare manipulable mechanisms to select the best among them.  We count the number of agents with an incentive to manipulate and rank mechanisms by their level of manipulability. This ranking sheds a new light on practical design decisions such as the design of the entry-level medical labor market in the United States, and school admissions systems in New York, Chicago, Denver, and many cities in Ghana and the United Kingdom.

"First, we consider the college admissions problem where both students and schools are strategic agents (Gale and Shapley (1962)) and schools can misreport their preferences as well as their capacities. We show that when all manipulations (by students as well as by schools) are considered, the student-proposing Gale–Shapley (GS) mechanism has the smallest number of manipulating agents among all stable matching mechanisms (Theorem 1). Dubins and Freedman (1981) and Roth (1982) show that this mechanism is not manipulable by students. This result was one of the main arguments in favor of its choice for the NRMP. However, it also has the largest number of manipulating schools among all stable mechanisms (Pathak and Sönmez (2013)). Our result still supports its choice when all strategic agents are considered. What is more, it is still the best choice even when schools can only misreport their capacities, but not their preferences. All these conclusions carry over to the general model where, in addition, students face ranking constraints: although the student-proposing GS mechanism is now manipulable by students, it is still the least manipulable mechanism.

"Second, we consider the school choice problem (Abdulkadiroglu and Sönmez ˘ (2003)) where students are the only strategic agents and also face ranking constraints. Historically, many school choice systems have used the constrained immediate acceptance (Boston) mechanism, but over time shifted toward the constrained student proposing GS mechanisms and relaxing the constraint. We demonstrate that the number of manipulating students (Theorem 2) weakly decreased as a result of these changes."