Matching Markets and the Boston Mechanism

June 20, 2018
posted in
written by TWS Partners

The study of matching markets has a long tradition in economics and is a major focus in the field of market design. Examples of matching markets are manifold, ranging from kidney exchange through to school selection and online dating. One common feature across most of these markets is that monetary payment is limited or infeasible.

Instead, people carry out transactions based on information. The focus of economic analysis is therefore set on developing systems to elicit people’s preferences and efficiently allocate a typically “heterogenous but indivisible good”.

Probably best known for his economic research on matching markets is economist Alvin E. Roth, co-recipient of the Nobel Prize in 2012. One of Roth’s protégés, Parag A. Pathak, has also effectively contributed to the analysis of matching mechanisms and putting economic matching theory to practice.

A prime example for this is the allocation of school places at Boston Public Schools. Up until 2005, the allocation of school places was based on the so-called “Boston mechanism”. As part of the mechanism students had to rank their school choices according to preference. Subsequently, as many students as possible would be matched with their first choices. Then, all remaining students would be matched with their second choice and so on.1 As a result, popular schools filled up quickly and there was a chance that students, who did not get their first choice, also failed to get their second or third choices as they were already filled up with students who had listed them as first choice. This induced some students to misrepresent their preferences to strategically manipulate the mechanism. In fact, some of the students’ parents gathered regularly prior to admission time to strategise and give advice to other parents, leading them to misrepresent their preferences. For example, they recommended to either list an unpopular school as first choice or “safe” second choice, to avoid having solely popular schools listed and risking not being assigned a place at all.2

To deal with this problem, Mr. Pathak proposed a mechanism that also asks students to list schools according to preference. Schools then assign first choices initially on a tentative basis. All students that are rejected in the first round are then tentatively assigned to their second choice, and so on. Only once all students are allocated to a school, is the assignment final. This way it is weakly optimal for all students to report their true preferences, regardless of what other students do.3

Despite the benefits of the mechanism proposed my Mr. Pathak, not everybody was happy with it. In particular, the group of parents that had previously been known to strategise, opposed the mechanism. Pathak and Sönmez (2004) present a theoretical explanation for this, where strategising students actually benefit from the Boston mechanism at the expense of more sincere students.4

The Boston mechanism was successfully replaced in 2005 and Mr. Pathak, who was recently awarded the 2018 John Bates Clark Medal, has since moved on to study other school matching mechanisms, such as New York High Schools and Chicago Exam Schools.

1 Find a more detailed description of the Boston mechanism in Abdulkadiroğlu et al. (2005).

2 As described in Pathak and Sönmez (2008). Abdulkadiroğlu et al. (2006) also find empirical evidence for the existence of strategic behavior of some of the students.

3 Find a more detailed description of the proposed mechanism in Abdulkadiroğlu et al. (2005).

4 For the derivation of this theoretical result see Pathak and Sönmez (2008).

SOURCES:

Abdulkadiroğlu, Atila, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. 2005. “The Boston Public School Match.” American Economic Review, 95 (2): 368-371.

Abdulkadiroğlu, Atila, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. 2006. “Changing the Boston School Choice Mechanism.” NBER Working Papers 11965.

Pathak, Parag A. and Tayfun Sönmez. 2008. “Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism.” American Economic Review, 98 (4): 1636-1652.