stable marriage problem

3 results back to index

The Mathematics of Love: Patterns, Proofs, and the Search for the Ultimate Equation by Hannah Fry

Brownian motion, John Nash: game theory, linear programming, Nash equilibrium, Pareto efficiency, power law, recommendation engine, Skype, stable marriage problem, statistical model, TED Talk

The situation is less appealing for the girls. Rachel, Phoebe and Monica end up with their second, third and second choices respectively. Not great in a list of three, and especially when compared to the boys, who ended up with their first, second, and first choices respectively. This setup is known as the ‘stable marriage problem’, and the process through which the friends picked their partners is called the Gale-Shapley algorithm. If we look into the mathematics behind these couplings, some extraordinary results appear. Regardless of how many boys and girls there are, it turns out that whenever the boys do the approaching, there are four outcomes which will always be true: 1.

…

If you sit around and wait for people to talk to you, you’ll end up with the least bad person who approaches you. Regardless of the type of relationship you’re after, it pays to take the initiative. The difference in outcomes between those who do the asking and those who wait to be asked is particularly important when the stable marriage problem is applied beyond imaginary couples at a party: something the US government found out the hard way. Through the National Resident Matching Program, the US government has been using the Gale-Shapley algorithm to match doctors to hospitals since the 1950s. Initially, the hospitals did the ‘proposing’.

…

But for all the extensions and examples, the message remains the same: if you can handle the occasional cringe-inducing rejection, ultimately, taking the initiative will see you rewarded. It is always better to do the approaching than to sit back and wait for people to come to you. So aim high, and aim frequently: the maths says so. 4 Online Dating So hopefully you’re now bold enough to approach the hotties at a party, armed only with your knowledge of the stable marriage problem. But too many parties in a row can be a bit exhausting, and not many of them will have a Joey or a Rachel to keep things interesting. So why not turn to an approach that can bring you success from the comfort of your living room? It’s time for online dating. At this point, almost everyone knows a couple who met on an internet dating site.

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

Now imagine that each location around the world can only be visited by one family at a time, but that all families have to still go on holiday during the same week. Now imagine that those holiday destinations also have their own list about which family they want to welcome. In 1962, two American economists named David Gale and Lloyd Shapley set out to devise an algorithmic solution to just this conundrum. What they came up with was called The Stable Marriage Problem—also known as “The Match.”1 To explain The Match, picture a remote island, cut off from the rest of civilization. On this island, there live an even number of men and women of marriageable age. The problem asks that all of these people are paired up in what we might consider a stable relationship.

…

This statistically unlikely event is done only for the sake of mathematical simplicity. A scenario where men want to marry men, women want to marry women, or everyone wants to marry everyone, does not necessarily yield the same stable outcome as the relatively straightforward matching I described. Another issue is that the Stable Marriage Problem presumes that all people of marriageable age do, in fact, wish to get married, and that the location in which they live is so remote that there is no chance whatsoever that any residents could marry someone from outside its boundaries. Yet another problem is that the algorithm assumes marriages only fail in the event of a disruptive third party, who is a better match for one part of a particular couple.

…

The part of The Match that causes me the most problems, however, is the piece of information we are asked to take as writ before the algorithm even gets going: namely the idea that each of the men and women addressed by the puzzle is able to compile a list in which they rank, without error, everyone of the opposite gender in the order that they would most happily be married to them. Of all the assumptions made by David Gale and Lloyd Shapley, this seems the most grievous. I do, of course, write these words with tongue firmly planted in cheek. As noted, the Stable Marriage Problem invokes romantic marriage as metaphor only, being designed for the purpose of matching medical students with hospitals. For this task it is largely suitable—since issues of one party chewing with their mouth open, or ogling a third party, are unlikely to result in separation. But by pointing out these conceptual difficulties, I do make a serious point: that outside of mathematical puzzles human beings have a nasty habit of behaving unpredictably.

The Creativity Code: How AI Is Learning to Write, Paint and Think by Marcus Du Sautoy

3D printing, Ada Lovelace, Albert Einstein, algorithmic bias, AlphaGo, Alvin Roth, Andrew Wiles, Automated Insights, Benoit Mandelbrot, Bletchley Park, Cambridge Analytica, Charles Babbage, Claude Shannon: information theory, computer vision, Computing Machinery and Intelligence, correlation does not imply causation, crowdsourcing, data is the new oil, data science, deep learning, DeepMind, Demis Hassabis, Donald Trump, double helix, Douglas Hofstadter, driverless car, Elon Musk, Erik Brynjolfsson, Fellow of the Royal Society, Flash crash, Gödel, Escher, Bach, Henri Poincaré, Jacquard loom, John Conway, Kickstarter, Loebner Prize, machine translation, mandelbrot fractal, Minecraft, move 37, music of the spheres, Mustafa Suleyman, Narrative Science, natural language processing, Netflix Prize, PageRank, pattern recognition, Paul Erdős, Peter Thiel, random walk, Ray Kurzweil, recommendation engine, Rubik’s Cube, Second Machine Age, Silicon Valley, speech recognition, stable marriage problem, Turing test, Watson beat the top human players on Jeopardy!, wikimedia commons

In fact, the algorithms seem to be better than we are on our own: recent research published in the Proceedings of the National Academy of Sciences looked at 19,000 people who married between 2005 and 2012 and found that those who met online were happier and had more stable marriages. The first algorithm to win its creators a Nobel Prize, originally formulated by two mathematicians, David Gale and Lloyd Shapley, in 1962, used a matching algorithm to solve something called ‘the Stable Marriage Problem’. Gale, who died in 2008, missed out on the award, but Shapley shared the prize in 2012 with the economist Alvin Roth, who saw the importance of the algorithm not just to the question of relationships but also to social problems including assigning health care and student places fairly. Shapley was amused by the award: ‘I consider myself a mathematician and the award is for economics,’ he said at the time, clearly surprised by the committee’s decision.

…

Shapley was amused by the award: ‘I consider myself a mathematician and the award is for economics,’ he said at the time, clearly surprised by the committee’s decision. ‘I never, never in my life took a course in economics.’ But the mathematics he cooked up has had profound economic and social implications. The Stable Marriage Problem that Shapley solved with Gale sounds more like a parlour game than a piece of cutting-edge economic theory. To illustrate the precise nature of the problem, imagine you’ve got four heterosexual men and four heterosexual women. They’ve been asked to list the four members of the opposite sex in order of preference.

…

Ekhad 179 Shankar, Ravi 11 Shannon, Claude 19, 203 Shapley, Lloyd 57, 58, 61 Shelley, Percy Bysshe 281 Shinshu University 236 shogi 97 Siemens 110, 111 SIGGRAPH conference (1980) 115 Sigur Rós: ‘Óveður 228–9 Silver, David 33, 38, 39, 98 Simrock, Nikolaus 194 Sky Arts 290 Slater, David 108–9 Sloane, Neil 291–2 Smith, Alvy Ray 115 Smith, Zadie 303 Société des auteurs, compositeurs et éditeurs de musique (SACEM) 229–30 Socrates 165 songwriting 213–32; AIVA and 229–30; The Continuator and 218–21; ‘Daddy’s Car’ (first pop song written by AI) 223–4; emotion and 204–6; Eno and 229; Fantom app and 226–8; Flow Machine and 221–4, 222; Hello World (AI album) 224; jazz/improvisation and 213–14, 218–24, 298, 299; Jukedeck and 225–6; Markov chain and 214–18, 216, 217; Sigur Rós: ‘Óveður and 228–9; Spotify and fake artists 224–5; why we make music 230–1 Sony 116, 124; Computer Science Laboratory, Paris 214, 224, 271 Sophocles 165 Spain football team 55 spam filters 90–1 SPEAC 198–200, 198 Spielberg, Steven 115 Spotify 135, 224–5 square root 1; of minus one 12; of 2 163, 244 Stable Marriage Problem, The 57–61, 58, 59, 60 Stanford University 48, 196, 259; Law School 109 Star Trek: The Next Generation (Cause and Effect episode) 251 Steels, Luc 271–2 Stokes, Mark 77 Stoppard, Tom 99 storytelling 275–97, 305; Android Lloyd Webber and 290; Beyond the Fence (musical) and 290–1; Botnik and 284–6; Cambridge Analytica and 296; Cybernetic Poet and 280–2; Ferranti Mark 1 and 277–8; future of AI and 305–6; mathematical tales, generating new 291–3; MduS uses AI to compose section of this book 297; NaNoGenMo (National Novel Generation Month)/AI novels 282–3; news stories, AI generated 293–6; Oulipo (Ouvroir de littérature potentielle) 278–80; plagiarism and 297; PropperWryter and 290; Scheherazade-IF and 286–8, 306; ‘The Great Automatic Grammatizator’ (Dahl) and 276–7, 297; What If Machine (Whim) and 288–91 Strachey, Christopher 278 Stravinsky, Igor 204–6 string theory 171 Stuttgart Academy of Fine Art 126 Suleyman, Mustafa 25 supervised learning 95–6, 97, 137 surprise, creativity and 4, 8, 40, 65, 66, 102–3, 148, 168, 202, 241, 248–9 symmetries 3, 4, 10, 11, 18, 100, 102, 172, 175, 177, 187, 191–2, 208, 235, 250, 292 tabula rasa learning 73, 97, 98 Taylor, Richard 123, 124, 172 Theme Park 23 Thiel, Peter 25 Thomas, Rob 227–8 Tinguely, Jean 119 Tolstoy, Leo 105, 242, 243 Touchette, Hugo 55 Trebek, Alex 262 Trinity College, Cambridge 240 Trump, Donald 54, 258 Trybulec, Andrzej 236 Turing, Alan 2, 7, 8, 24, 66, 277, 278; ‘Computing Machinery and Intelligence’ 254 Turing Test 7, 38, 71, 200–2, 220–1, 239–41, 254–7, 258, 260, 273, 281, 282, 297 University College London 25 University of Alberta 236 University of California, San Diego 117 University of Manchester 277–8 University of Oregon 123, 201 University of Texas 88 Up (film) 115 Valéry, Paul 233 value, creativity and 4, 8, 12, 16, 17, 40–1, 102–3, 167–8, 238–9, 301, 304 Van Gogh, Vincent 16, 41, 126, 128, 131, 135, 136, 137, 138 Veenendaal, Albert van 220–1 Venice Biennale (1966) 117 Vinyals, Oriol 235, 236, 238 vision, computer 43, 70–80, 75, 93–4, 137–8, 143, 145, 212 visuals, code made 110–13 Voevodsky, Vladimir 181–5 Vogelkop gardener bowerbird 108 Vol Libre (‘Free Flight’) animation 114 Walsh, Toby 292 Warhol, Andy 107 Watson 261–8 Watson, Thomas J. 262 Weierstrass, Karl 7 Weizenbaum, Joseph 255, 256 Wells, H.