In traditional economic analyses, markets allocate resources efficiently by setting prices so that supply equals demand. But what happens in cases where there is supply and demand, but no prices? For example, how should new doctors seeking jobs be assigned to hospitals seeking new doctors? Or how should altruistic organ donors be matched to fortunate recipients with whom they’re deemed a match? Economists refer to these scenarios as “matching markets,” and offer an entire subfield dedicated to finding practical solutions to challenges such as these.
Economists David Gale and Lloyd Shapley laid the groundwork for stable matching theory with their 1962 paper “College Admissions and the Stability of Marriage.” Through a process of reporting ranked preferences, they showed, it is always possible to find a stable matching arrangement between two groups. By “stable,” Gale and Shapley mean that there can be no pair that would rather be paired with one another over their current partners (such would be referred to as a “blocking” pair), and no one can remain unmatched who could be matched without forming a blocking pair.
Gale and Shapley’s matching algorithm was the template used two decades later by economist Alvin Roth in his investigation of the market for doctors in the United States. Roth has spent much of his career developing the practical implications of the Gale-Shapley algorithm, which today is used to inform matching markets including high school choice programs, organ donor pairing, and the National Resident Matching Program (NRMP). In 2012, Lloyd Shapley and Alvin Roth were awarded the 2012 Nobel Prize in Economic Sciences for their contributions related to stable matching (Gale passed away in 2008).
A key reason that market designers continue to turn to the Gale-Shapley approach (also referred to as deferred acceptance, or DA) is because it is strategyproof. In theory, participants’ best bet to gain an optimal match is to report their preferences honestly. However, these theoretical benefits might not be realized in practice. For example, if participants do not understand or trust that the algorithm is strategy proof, they may still misreport their preferences. Or they may try to reduce their uncertainty about their match by entering into informal agreements with agents on the other side of the market to “rank each other first.” This paper tests the practical impacts of DA through a randomized controlled trial covering workers in the United States Army who are matched to positions, or units, using DA.
Army officers rotate units within the Army roughly every three years. The U.S. Army’s Human Resources Command coordinates officer rotations in an annual matching market that includes over 14,000 officers to be matched across roughly 500 units. In 2019, the authors worked with the Army to randomly assign a subset of markets to a treatment group where officers and units were matched using a deferred acceptance algorithm. The remainder were assigned to a control group where officers and units were matched according to the Army’s traditional process, which involves career managers manually making match decisions using officer and unit preferences without the aid of any specific algorithm.
The authors analyze the impacts of their experiment using data on retention within the Army, which proxies for officer satisfaction; officers’ evaluation reports and promotions, which measure officer performance; and survey evidence on truthful preference reporting, which reflects whether DA is strategy proof for officers. They find the following:
- Officer-proposing DA reduces attrition in the first post-match year by 16.7% compared to the control group. However, the authors rule out more than a 10% reduction in attrition by the end of participants’ second year.
- The officer-proposing DA algorithm had no effect on performance evaluations and promotions. Matching with DA had little impact on the probability that an officer receives the highest possible performance evaluation, that an officer is promoted to the next rank, or on officers’ promotion board percentile ranking relative to other officers considered for promotion.
- Although matching with DA increased truthful preference reporting, many officers matched by DA still misreport their true preferences. In a survey administered three weeks before the marketplace closed, officers in DA markets were 10% more likely to report always submitting their true preferences than officers in the control group. However, in a post-market survey administered when officers learned of their matches, only 69% of officers stated that they truthfully reported their top choice, with no statistically significant difference between the treatment and control groups.
- Communication and coordination of preferences may limit the benefits of DA in matching markets where each side actively ranks the other. In both DA and control markets, roughly 45% of matches are “first-to-first” pairings— that is, a match where an officer has ranked a job listing as their first choice and where the unit has ranked the same officer as their first choice for that particular listing. The authors show that this is very unlikely due to correlated preferences between officers and units, suggesting that officers deviate from their true preferences to achieve a first-to-first pairing.
This is the first randomized controlled trial that measures the impact of matching workers to jobs using deferred acceptance. Consistent with survey evidence from the NRMP, the authors find evidence of communication and coordination of preference reports across the two sides of the market. The authors hypothesize that this coordination is more common in settings where there is regular correspondence across sides, and less likely to occur in matching applications where communication across sides is either uncommon or unnecessary, such as school choice markets where schools’ rankings of students are based on lotteries, test scores, or distance rules. Despite modest impacts on retention and performance, DA is still beneficial to the Army because it is straightforward to implement and easy for officers and units to navigate. In part because of these benefits, the Army adopted DA for all markets in the years following the experiment.