deferred acceptance

Who Gets What — and Why: The New Economics of Matchmaking and Market Design

by Alvin E. Roth  · 1 Jun 2015  · 282pp  · 80,907 words

matchings that I later discovered was equivalent to the one the doctors had adopted for the 1952 clearinghouse. Gale and Shapley called their version the deferred acceptance algorithm, and it eventually became the most important strain of the Penicillium mold for fixing failed matching markets—not least because they recognized that it

…

would undoubtedly have shared it with Lloyd and me if he had still been living. Gale and Shapley weren’t the first to discover the deferred acceptance algorithm, but they were the last: it was never lost again. Here’s how it works. I’ll describe the algorithm as though applicants and

…

these facts demonstrates that the matching is stable; it has no blocking pairs. This important bundle of simple ideas—a model of stable matching, the deferred acceptance algorithm, and the proof that it produces a stable matching for any preferences—was recognized with great fanfare—literal fanfares with actual trumpets—in Stockholm

…

out how to handle not only single applicants and couples but also a number of other “match variations” that weren’t gracefully handled by the deferred acceptance algorithm in its simplest form. (Some single doctors also needed to find two jobs to train for the specialties they wanted, and some hospitals needed

…

we had to produce stable matchings whenever possible. We also knew that any acceptable algorithm that could handle couples wouldn’t look just like the deferred acceptance algorithm; it would also have to track down and fix blocking pairs involving couples. We eventually developed a hybrid algorithm that has come to be

…

called the Roth-Peranson algorithm. It finds a preliminary matching of doctors to residency programs by starting with a deferred acceptance algorithm, which yields an outcome containing some blocking pairs. Then it tries to fix them one by one. For reasons I’ll return to when

…

I talk about school choice clearinghouses, Elliott and I reversed the deferred acceptance algorithm that I’ve just described and used one in which the applicants applied for jobs, starting with the one they preferred most, rather than

…

families would like them to go to. This is a problem for which my colleagues and I also helped design computerized clearinghouses based on the deferred acceptance algorithm. I’ll describe how that made it safe for families to reveal their true preferences for which schools they would like their children to

…

as much as those for whom they might have saved seats. That’s why, in the end, we suggested a computerized clearinghouse based on the deferred acceptance algorithm—that is, the same underlying algorithm that powers the medical Match. We believed its properties went a long way toward addressing New York City

…

popular school, which under the old system used to receive about 1,300 applicants for its 150 places, so in the first step of the deferred acceptance algorithm, it rejected all but its top 150 applicants. But since acceptance was now deferred, Beacon didn’t yet accept those kids who applied in

…

all with his chance of getting admitted there after his rejection by Townsend Harris. When students can list as many choices as they want, the deferred acceptance algorithm allows them to safely list schools in true order of preference; they won’t lose a place just because someone else applied earlier in

…

, which is mathematically related to the fact that most people get the same match at every stable matching.) For school choice, the fact that the deferred acceptance algorithm produces a stable outcome (one with no blocking pairs) also serves school principals well. To see why, imagine what might have happened if Zach

…

the previous chapter to demonstrate Gale and Shapley’s discovery that the final matching that results from the deferred acceptance algorithm is stable. Details, Details I made some simplifications in my explanation of how the deferred acceptance algorithm was adapted to fit New York school choice. It’s worth mentioning a few of these

…

advisers, and not all of our advice was adopted. (This is pretty typical of market design, by the way.) So, for example, in practice the deferred acceptance algorithm is actually run more than once. That’s because there are several specialized schools that form their preferences strictly on the basis of exam

…

students each receive two offers of admission even before the main round of the match is run. Their offers are determined by running the full deferred acceptance algorithm on all students’ submitted preferences and then running it again for all the other students after these select students have been placed. Another simplification

…

, although some of the problems there were different. Boston Public Schools also decided to replace its old school choice system with one based on a deferred acceptance algorithm. Recall from chapter 7 that Boston already had a computerized choice system in place, in which parents submitted a rank order of schools, but

…

apply, using the priority that each child had at each school only to break ties when more students applied than could be admitted. The new deferred acceptance algorithm still gave priority to parents who lived in a school’s walk zone or who had another child already attending a given school. And

…

have been modified incrementally, so that they now are somewhere in between immediate acceptance (as in Boston before we helped change the system there) and deferred acceptance (as in Boston and New York school choice today). There’s every reason to hope that in the coming decades, we’ll be able to

…

things are important. Xiaolin Xing and I studied the labor market for professional psychologists at a time when they tried to implement something like the deferred acceptance algorithm by telephone. It was too congested for them to get to a stable matching: trying to conduct all the steps of the

…

deferred acceptance algorithm through long chains of phone calls took too long. See A. E. Roth and X. Xing, “Turnaround Time and Bottlenecks in Market Clearing: Decentralized

…

): 368–71. [>] clearinghouses have been modified: For a description of Chinese college admissions, see Yan Chen and Onur Kesten, “From Boston to Chinese Parallel to Deferred Acceptance: Theory and Experiments on a Family of School Choice Mechanisms” (discussion paper, University of Michigan, 2013). 10. SIGNALING [>] is the candidate qualified: For signals about

…

an Old One” (Franklin), 200–201 Affordable Care Act, 224 Airbnb, 99–103, 116 algorithms Boston Public Schools, 122–28 computerized markets and, 225–26 deferred acceptance, 141–44 in Boston Public Schools system, 162–65 in New York school choice program, 155–61 for financial marketplaces, 82–89 Internet dating sites

…

–41 Coca-Cola, 25 coercion, 203, 208 coffee, 17–19 Coles, Peter, 244 college admissions, 5–6 acceptance rates in, 172 campus visits in, 178 deferred acceptance algorithm in, 141–43 early, 171–72 signaling in, 169, 170–73 strategic decision making in, 10 “College Admissions and the Stability of Marriage” (Gale

…

markets and, 200–201, 204–5 dating sites, Internet, 72, 169, 175–77, 179 D.C. Circuit Court, 95, 97 decision making. See strategic decisions deferred acceptance algorithm, 141–44 in Boston Public Schools system, 162–65 in New York school choice program, 155–61 Roth-Peranson hybrid of, 148–49 in

…

Scheibe, Susan, 38–39 school matching, 8, 165–67 Boston Public Schools, 11, 122–28, 162–65 in China, 165–66 constraints in, 158–61 deferred acceptance algorithm in, 157–61 inequality of schools and, 166–67 New York City school system, 8, 106–10, 112, 122, 153–61 parent preferences in

The Inner Lives of Markets: How People Shape Them—And They Shape Us

by Tim Sullivan  · 6 Jun 2016  · 252pp  · 73,131 words

a solution, and by the end of the afternoon an answer was in an envelope and on its way to Gale’s office in Providence. Deferred Acceptance at the Middle School Dance Together, the two mathematicians refined and wrote up Shapley’s response in a paper titled “College Admissions and the Stability

…

far enough down their lists that they’d rather just sulk on the sidelines than find themselves a partner). Gale and Shapley called it the “deferred acceptance” algorithm—deferred in the sense that each girl gets to keep a backup date but defers her acceptance of him until she’s had a

…

chance to see what other prospects might appear. What makes deferred acceptance so useful as a clearinghouse for dates and many other matching problems is its stability: once it’s run its course, there won’t be

…

this to be true? By definition, a boy would only want to trade his final match for someone who was higher on his list. Under deferred acceptance, he’s already tried his luck with every higher-ranked girl, and they’ve all rejected him. And why did they reject him? Because they

…

of matching students to schools in New York (or Paris or Shanghai or any one of the many other cities that use a variant on deferred acceptance to make school assignments). To fill their kindergarten slots, each principal submits to the superintendent an ordered list of her choice of students. (In practice

…

behind Gale and Shapley’s algorithm, in practice there’s no need for it. Once each market participant has submitted his or her list, the deferred acceptance algorithm takes care of the rest. Why magnify the awkwardness of adolescence through a real-life multiround popularity contest? If students go online to submit

…

harsh as it sounds, the pimple-faced kid with limited prospects is doing the best he can with what Gale and Shapley offer him. What deferred acceptance can ensure is that once the matches are set, no one wants to go outside the system in search of a better match—that was

…

exploding offers before they were done with their intro to anatomy course. These allocation problems all now have centralized clearinghouses, many designed with the basic deferred acceptance algorithm as their foundations. But that’s really all that Gale and Shapley provided: a conceptual framework that market designers have, for several decades now

…

, Tayfun Sönmez, had been hounding the city’s school board for years with proposals on how to improve student assignments using a match based on deferred acceptance. His overtures had been consistently ignored. That changed in 2003 when the Boston Globe ran a story, “School assignment flaws detailed: Two economists study problem

…

doesn’t require this sort of anxiety-filled overthinking is called “strategy-proof” and it had been shown decades earlier that Gale and Shapley’s deferred acceptance method satisfied this property. You can’t do any better than list your true school preferences and let the algorithm do the rest. To make

…

years of meetings, lobbying by all sides, presentation of proposals and counter-proposals, and yet more lobbying and politicking, Boston schools adopted a version of deferred acceptance in 2006. (The New York school system, which was much more desperately in need of change, had already adopted a

…

deferred acceptance–based system three years earlier.) Students listed up to six schools, in order of preference. The rankings that each school assigned to students were dictated

…

their kindergartners as well, could understand how it worked and the choices available to them. Did Shi throw the deferred acceptance baby out with the old school assignment bathwater? Not at all. Deferred acceptance is still the algorithm that governs the assignment of students to schools once they’ve submitted their rankings of each

…

. This is how science—and society—progresses. We make well-meaning attempts at socially improving innovations. Sometimes they work exactly as we had hoped: the deferred acceptance high school match in New York is still running today in essentially its original form. More often there are tweaks and adjustments along the way

…

camp, 8–9 customer feedback, 52, 74–75 Davis, Harry, 154, 157 Debreu, Gérard, 20, 24, 25, 32–33, 36–37 decentralized match, 139–140 deferred acceptance algorithm, 137–141, 145–149 Delmonico, Frank, 164 descending price auctions, 81–82 design, auction, 14, 101–102 Digital Dealing (Hall), 94 Discover card, 115

Markets, State, and People: Economics for Public Policy

by Diane Coyle  · 14 Jan 2020  · 384pp  · 108,414 words

markets Economist Al Roth won the Nobel Prize (along with Lloyd Shapley) for his work on algorithms for acceptance markets. The best known is the deferred acceptance rule, which can be used in applications ranging from school admissions to marriage markets. Suppose there is a set of men M (with a typical

…

prefers Priya to Rosie Rosie prefers Ajay to Bob Priya prefers Bob to Ajay there is one unique, stable matching (Rosie, Ajay), (Priya, Bob). The deferred acceptance algorithm starts by having each woman propose to the highest man in her ranking; the men can reject or tentatively accept the offer. Each rejected

…

. The theories also look at how to make sure the algorithms incentivize participants always to reveal their true preferences rather than to choose strategically. The deferred acceptance algorithm is not strategy proof, as the receiving party has an incentive to game it by turning down acceptable offers given the chance of getting

…

firms and death of inefficient ones in a market economy. Deadweight loss: The absolute loss of economic efficiency when a market is not perfectly competitive. Deferred acceptance: An algorithm for efficient matching of supply and demand in contexts such as job markets or dating markets. Edgeworth box: A tool for representing the

The Man From the Future: The Visionary Life of John Von Neumann

by Ananyo Bhattacharya  · 6 Oct 2021  · 476pp  · 121,460 words

a paper, in which they also showed that the method could be used to match applicants to colleges.32 Now known as the Gale-Shapley ‘deferred acceptance’ algorithm, the work was cited as part of the decision to award Shapley a share of the 2012 Nobel Memorial Prize in Economic Sciences, instantly

…

, 183–6 Alchian, Armen 206–7 Alcsuti, Lili 7, 14, 66 Alexander, James 68 algorithms and mathematical logic 28, 115, 179 matchmaking, see ‘Gale-Shapley deferred acceptance algorithm’ Monte Carlo 137 altruism 179–81, 316n82 Amazon 173, 179 American Institute of Physics 58 American Mathematical Society 77 Analog (science fiction magazine) 58

…

–1010, 109 Fuchs-von Neumann patent 99–100, 109 Gabor, Dennis 8 Galaxy Science Fiction (magazine) 231–2 Gale, David 177, 197, 202 Gale-Shapley deferred acceptance algorithm 178, 197 game theory xi, xii, 57, 141–8, 157–182 altruism 179–81 analysis of poker 148, 1646–8, 168 analysis of two

The Formula: How Algorithms Solve All Our Problems-And Create More

by Luke Dormehl  · 4 Nov 2014  · 268pp  · 75,850 words

her current best available option, who she tentatively agrees to marry, knowing that she can ditch him later on. (This is referred to as a “deferred acceptance.”) Come dawn of the second day and those men who remain single propose to their next best choice. That afternoon, the women who accepted marriage

…

, Alain 87 “De-Scription of Technical Objects, The” (Akrich) 136n DeadSocial 96 death, apps concerning 96–98 decimated-reality aggregators 45–47 Deep Blue 29 deferred acceptance 63 see also “Match” Deleuze, Gilles 54–55, 60 demassification 21 DeRose, Steven 194 Descartes, René 12 deviantART 37 Dialectic of Enlightenment (Adorno, Horkheimer) 179