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, Berlin Wall, bitcoin, Build a better mousetrap, centralized clearinghouse, computer age, crowdsourcing, deferred acceptance, desegregation, 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, 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

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. 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.

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 always produces a stable matching, at least for markets without too many complications, such as couples who need two jobs in the same city. (But I’m getting ahead of myself.) Lloyd Shapley was one of the founding giants of game theory. He wrote many papers that initiated whole areas of study, but this was the paper for which he was recognized with the Nobel Prize in Economics in 2012. David Gale 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.

Beacon was also a very 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 step 1. When Zach applied, it compared him with the 150 who hadn’t been rejected in step 1 and anyone else who applied in step 2, ranked them all, and rejected all but the top 150 of this new group. Zach wasn’t rejected in the second step nor in any subsequent step. And when the algorithm ended, he was accepted by Beacon. Unlike his brother, he could safely list his true preferences, putting Beacon second. That didn’t interfere at 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 the algorithm.


pages: 252 words: 73,131

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


Airbnb, airport security, Al Roth, Andrei Shleifer, attribution theory, autonomous vehicles, barriers to entry, Brownian motion, centralized clearinghouse, clean water, conceptual framework, constrained optimization, continuous double auction, deferred acceptance, Donald Trump, Edward Glaeser, experimental subject, first-price auction, framing effect, frictionless, fundamental attribution error, George Akerlof, Goldman Sachs: Vampire Squid, helicopter parent, 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, late fees, linear programming, Lyft, market clearing, market design, market friction, medical residency, multi-sided market, mutually assured destruction, Nash equilibrium, Occupy movement, Peter Thiel,, pez dispenser, pre–internet, price mechanism, price stability, prisoner's dilemma, profit motive, proxy bid, RAND corporation, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Ronald Coase, school choice, school vouchers, sealed-bid auction, second-price auction, second-price sealed-bid, sharing economy, Silicon Valley, spectrum auction, Steve Jobs, Tacoma Narrows Bridge, technoutopianism, telemarketer, The Market for Lemons, The Wisdom of Crowds, Thomas Malthus, Thorstein Veblen, trade route, transaction costs, two-sided market, uranium enrichment, Vickrey auction, winner-take-all economy

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. How did Shapley know 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?

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.) Students listed up to six schools, in order of preference. The rankings that each school assigned to students were dictated by school board priorities: preference was given to applicants with siblings, and half of all seats were reserved for walk zone students who lived within a mile of the school.

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. More often there are tweaks and adjustments along the way, or as was the case in Boston, we’re blindsided by something serious enough that we need to return to the drawing board.


pages: 268 words: 75,850

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


3D printing, algorithmic trading, Any sufficiently advanced technology is indistinguishable from magic, augmented reality, big data - Walmart - Pop Tarts, call centre, Cass Sunstein, Clayton Christensen, computer age, death of newspapers, deferred acceptance, Edward Lorenz: Chaos theory, Erik Brynjolfsson, Filter Bubble, Flash crash, Florence Nightingale: pie chart, Frank Levy and Richard Murnane: The New Division of Labor, Google Earth, Google Glasses, High speed trading, Internet Archive, Isaac Newton, Jaron Lanier, Jeff Bezos, job automation, Kevin Kelly, Kodak vs Instagram, Marshall McLuhan, means of production, Nate Silver, natural language processing, Netflix Prize, pattern recognition, price discrimination, recommendation engine, Richard Thaler, Rosa Parks, self-driving car, sentiment analysis, Silicon Valley, Silicon Valley startup, Slavoj Žižek, social graph, speech recognition, Steve Jobs, Steven Levy, Steven Pinker, Stewart Brand, 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

On the morning of the first day, every man proposes to his first choice of wife. 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. This process continues for days three, four, five, et cetera, until all couples are matched in stable relationships.

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