deferred acceptance

Who Gets What — and Why: The New Economics of Matchmaking and Market Design
by Alvin E. Roth
Published 1 Jun 2015

Over the next year, working together, we figured 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 flexibility to shift positions between different residency programs.) We knew 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.

…

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 having employers offer jobs starting with offers to their most preferred candidates.

…

For example, Zach liked Cardozo, but not as much as Beacon, which accepted him—so he wouldn’t apply to Cardozo after being admitted to Beacon. Notice that we’ve just repeated the logic that we used in 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 simplifications, because details matter so much in market design. Just as the medical Match had some special features (including couples looking for two jobs), so, too, does New York school choice.

The Inner Lives of Markets: How People Shape Them—And They Shape Us
by Tim Sullivan
Published 6 Jun 2016

At a 2003 parents’ group meeting in Boston’s West Zone, the minutes included the following advice: “[F]ind a school you like that is undersubscribed and put it as a top choice, OR, find a school that you like that is popular and put it as a first choice and find a school that is less popular for a ‘safe’ second choice.”7 A mechanism that 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 a long story shorter (there is, after all, no such thing as a short story in the annals of school reform), after 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.)

…

And it was a simple enough approach that parents, and probably 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 of the options available to them. But he’s managed to insert it into a more transparent and effective mechanism. 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.

…

This goes on until all boys and girls find matches (or until boys have run 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 a boy-girl pair eying one another from across the room, wishing they could be together.

The Man From the Future: The Visionary Life of John Von Neumann
by Ananyo Bhattacharya
Published 6 Oct 2021

Perhaps in this spirit, Gale sent a few other mathematicians a note in 1960 asking, ‘For any pattern of preferences, is it possible to find a stable set of marriages?’ Shapley sent his answer by return of post. Let each boy propose to his best girl. Let each girl with several proposals reject all but her favorite, but defer acceptance until she is sure no one better will come her way. The rejected boys then propose to their next-best choices, and so on, until there are no girls with more than one suitor. Marry. The result is stable, since the extramarital liaisons that were previously rejected will be disliked by the girl partners, while all others will be disliked by the boy partners.31 Shapley’s solution applies to any market that requires two sets of people to be paired up so that no one can do better.

…

The result is stable, since the extramarital liaisons that were previously rejected will be disliked by the girl partners, while all others will be disliked by the boy partners.31 Shapley’s solution applies to any market that requires two sets of people to be paired up so that no one can do better. Gale and Shapley wrote up the findings in 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 garnering him a reputation in the press as a mathematical matchmaker extraordinaire. He would be one of two game theorists whose striking early contributions did much to make the field useful for economics and other disciplines.

…

Page numbers in bold refer to illustrations A Beautiful Mind (film) 198 ‘A Model of General Economic Equilibrium’ (von Neumann) 151, 312n21 A New Kind of Science (Wolfram) 251–3 Aberdeen Proving Ground, Maryland 72–3, 83, 105, 128, 135–8 additivity postulate 51–2, 297–8n59 Aiken, Howard 104 air power 83, 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 Analytical Engine 290n12 anti-Semitism 2, 5, 14–15, 62–64, 78, 118, 142, 152–3, 155, 198 Apollinaire, Guillaume 154–165 Apple 16, 173, 179 Applied Mathematics Panel 104, 187–8, 191 Archimedes x Aristotle 112 Arizona, University of 188, 258 Arnold, Henry ‘Hap’ 183–6, 209 ARPANET, the 103 Arrow, Kenneth 151 artificial intelligence 121, 122, 257, 264, 274, 275–276 Artificial Living Plants 263, 325n72 ASCC (Automatic Sequence Controlled Calculator) 104 Atanasoff, John Vincent 127 Atlas Missile Project 216–18 atom bomb ‘gun type’ 81–2, 86 implosion method 82, 84–9, feasibility of 80 origins of 77–8 petition against use 92–3 power 80, 91, 95 targets 94 see also Manhattan Project Atomic Energy Commission 14 Oppenheimer hearing 211–12 Atomic Energy Research Establishment, Harwell 52 Augenstein, Bruno 216–18, 217 Aumann, Robert 178 Austria, Nazi annexation of 1187, 154–5 automata cellular 234–7, 236, 243–53 Conway’s achievements 237–41, 238, 239, 240, 242, 243 evolution of 229, 236–7 most fecund 272–3 kinetic theory of 228–32, 269–70, 272, 273 see also self-reproducing automata Automatic Computing Engine (ACE) 121, 125 Axelrod, Robert 181, 272 Aydelotte, Frank 128–9, 130 Babbage, Charles 290n12 Bacharach, Michael 172 backward induction 164, 319n51 Bainbridge, Kenneth 90–2 Ballistics Research Laboratory 72–3, 77, 79, 105, 107–8, 110, 128, 135, 136 bargaining problem, the 199 Barricelli, Nils Aall 254–5, 256, 257 Bartik, Jean 1321, 135 Bath, Nautical Almanac Office 79 Belfast 52 Bell, John Stewart 52–7, 60 critique of VNs impossibility proof 52–4 and the EPR paradox 55–7 Bell, Mary 52 Bell’s inequality 56–7, 60 Berlin, Bebelplatz 64 Berlin, University of 12, 21, 25–6, 39–41, 40 Bernstein, Jeremy 274 Bertlmann, Reinhold 56 Bigelow, Julian 130, 138, 140 Bikini Atoll 98 Binmore, Ken 166, 168 Birkhoff, Garrett 69–70 Birkhoff, George 69 Blackett, Patrick 188 Blade Runner (film) 231 Blair, Clay 192–3 bluffing 166–8 Bockscar 95–6 Bohm, David 53–5, 56–7 Bohr, Niels 29–30, 31, 35, 43–9, 57, 76, 78, 156, 296n43, 301n23 Boltzmann, Ludwig 69 Bolyai, János 17–18, 19 bombs, maximising destructive power of 73, 83 Borel, Émile 146–7, 169 Born, Max 32–3, 34–5, 63–4, 293–4n10 Bowyer, Adrian 225 brain, the information processing (IP) metaphor 276 structure 227–8, 273 workings of 273–6 Brainerd, John 108 Braun, Wernher von 265 Brenner, Sydney 231 Brodie, Bernard 218, 222 Bronowski, Jacob 142, 164 Brouwer, L.

The Formula: How Algorithms Solve All Our Problems-And Create More
by Luke Dormehl
Published 4 Nov 2014

Certain women will be in the fortunate position of having received multiple proposals, while others will have received none. On the afternoon of the first day, each woman rejects all suitors except for 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 on day one have the chance to trade up, if the man who proposed to them on day two is, in their view, preferable to the person they are engaged to.

…

M. 203 cogito ergo sum (I think, therefore I am) 12 Colorado public-benefits system, errors in 153–54 Community 196 Comte, Auguste 114–16 Conboy, Kevin 13, 92–95 Conly, Sarah 138–39 cookies 17 Coughlan, Alexandra 201 Coupland, Douglas 16 CourseSmart 39–41 crime, see law and law enforcement Crohn’s disease 10 Crosby, Michelle 131 Crowded Room 89 Cruise, Tom 68–69, 118 Csikszentmihalyi, Mihaly 100 Cuckoo’s Calling, The (Galbraith) 187 Culture of Public Problems, The (Gusfield) 142–43 “cyberbole” 210 origin of 4 DARPA 213 Darwin, Charles 31, 118 data-mining 10, 41, 67–68, 106, 126, 134–35, 150, 156, 158–60, 183, 187, 223 dating sim 103–4 Dawkins, Richard 129 de Botton, 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 Dick, Philip K. 118, 226 Die Walküre 70 differential pricing 50–52 digital humanities 3 “Digital Panopticon, The” (Poole) 55–56 “Digitizing the Racialized Body” (Hansen) 53 Disney 181 “dividuals” 54 divorce: algorithm for 129 rate of 67, 71–72 “Do Artifacts Have Politics?”