deferred acceptance

3 results back to index


pages: 282 words: 80,907

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

Affordable Care Act / Obamacare, Airbnb, algorithmic trading, barriers to entry, behavioural economics, Berlin Wall, bitcoin, Build a better mousetrap, centralized clearinghouse, Chuck Templeton: OpenTable:, commoditize, computer age, computerized markets, crowdsourcing, deferred acceptance, desegregation, Dutch auction, experimental economics, first-price auction, Flash crash, High speed trading, income inequality, Internet of things, invention of agriculture, invisible hand, Jean Tirole, law of one price, Lyft, market clearing, market design, medical residency, obamacare, PalmPilot, proxy bid, road to serfdom, school choice, sealed-bid auction, second-price auction, second-price sealed-bid, Silicon Valley, spectrum auction, Spread Networks laid a new fibre optics cable between New York and Chicago, Steve Jobs, The Wealth of Nations by Adam Smith, two-sided market, uber lyft, undersea cable

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.


pages: 252 words: 73,131

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

Abraham Wald, Airbnb, airport security, Al Roth, Alvin Roth, Andrei Shleifer, attribution theory, autonomous vehicles, barriers to entry, behavioural economics, Brownian motion, business cycle, buy and hold, centralized clearinghouse, Chuck Templeton: OpenTable:, classic study, clean water, conceptual framework, congestion pricing, constrained optimization, continuous double auction, creative destruction, data science, deferred acceptance, Donald Trump, Dutch auction, Edward Glaeser, experimental subject, first-price auction, framing effect, frictionless, fundamental attribution error, George Akerlof, Goldman Sachs: Vampire Squid, Gunnar Myrdal, helicopter parent, information asymmetry, Internet of things, invisible hand, Isaac Newton, iterative process, Jean Tirole, Jeff Bezos, Johann Wolfgang von Goethe, John Nash: game theory, John von Neumann, Joseph Schumpeter, Kenneth Arrow, late fees, linear programming, Lyft, market clearing, market design, market friction, medical residency, multi-sided market, mutually assured destruction, Nash equilibrium, Occupy movement, opioid epidemic / opioid crisis, Pareto efficiency, Paul Samuelson, Peter Thiel, pets.com, pez dispenser, power law, pre–internet, price mechanism, price stability, prisoner's dilemma, profit motive, proxy bid, RAND corporation, ride hailing / ride sharing, Robert Shiller, Robert Solow, Ronald Coase, school choice, school vouchers, scientific management, sealed-bid auction, second-price auction, second-price sealed-bid, sharing economy, Silicon Valley, spectrum auction, Steve Jobs, Tacoma Narrows Bridge, techno-determinism, technoutopianism, telemarketer, The Market for Lemons, The Wisdom of Crowds, Thomas Malthus, Thorstein Veblen, trade route, transaction costs, two-sided market, uber lyft, uranium enrichment, Vickrey auction, Vilfredo Pareto, WarGames: Global Thermonuclear War, winner-take-all economy

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.


pages: 476 words: 121,460

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

Ada Lovelace, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Alvin Roth, Andrew Wiles, Benoit Mandelbrot, business cycle, cellular automata, Charles Babbage, Claude Shannon: information theory, clockwork universe, cloud computing, Conway's Game of Life, cuban missile crisis, Daniel Kahneman / Amos Tversky, DeepMind, deferred acceptance, double helix, Douglas Hofstadter, Dr. Strangelove, From Mathematics to the Technologies of Life and Death, Georg Cantor, Greta Thunberg, Gödel, Escher, Bach, haute cuisine, Herman Kahn, indoor plumbing, Intergovernmental Panel on Climate Change (IPCC), Isaac Newton, Jacquard loom, Jean Tirole, John Conway, John Nash: game theory, John von Neumann, Kenneth Arrow, Kickstarter, linear programming, mandelbrot fractal, meta-analysis, mutually assured destruction, Nash equilibrium, Norbert Wiener, Norman Macrae, P = NP, Paul Samuelson, quantum entanglement, RAND corporation, Ray Kurzweil, Richard Feynman, Ronald Reagan, Schrödinger's Cat, second-price auction, side project, Silicon Valley, spectrum auction, Steven Levy, Strategic Defense Initiative, technological singularity, Turing machine, Von Neumann architecture, zero-sum game

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.


pages: 268 words: 75,850

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

3D printing, algorithmic bias, algorithmic trading, Alvin Toffler, Any sufficiently advanced technology is indistinguishable from magic, augmented reality, big data - Walmart - Pop Tarts, call centre, Cass Sunstein, classic study, Clayton Christensen, commoditize, computer age, death of newspapers, deferred acceptance, disruptive innovation, Edward Lorenz: Chaos theory, Erik Brynjolfsson, Evgeny Morozov, Filter Bubble, Flash crash, Florence Nightingale: pie chart, Ford Model T, Frank Levy and Richard Murnane: The New Division of Labor, fulfillment center, Google Earth, Google Glasses, High speed trading, Internet Archive, Isaac Newton, Jaron Lanier, Jeff Bezos, job automation, John Markoff, Kevin Kelly, Kodak vs Instagram, Lewis Mumford, lifelogging, machine readable, machine translation, Marshall McLuhan, means of production, Nate Silver, natural language processing, Netflix Prize, Panopticon Jeremy Bentham, Paradox of Choice, pattern recognition, price discrimination, recommendation engine, Richard Thaler, Rosa Parks, scientific management, self-driving car, sentiment analysis, Silicon Valley, Silicon Valley startup, Slavoj Žižek, social graph, speech recognition, stable marriage problem, Steve Jobs, Steven Levy, Steven Pinker, Stewart Brand, technological determinism, technological solutionism, TED Talk, the long tail, the scientific method, The Signal and the Noise by Nate Silver, upwardly mobile, Wall-E, Watson beat the top human players on Jeopardy!, Y Combinator

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?”