There’s an apocryphal story about how Richard Nixon’s speechwriter quit. Back in the days before the autocue became portable and discreet, speechwriters would create enormous flashcards through which the politician would flip during his speech. The famous last speech allegedly climaxed as follows:
FLASHCARD: We can whip inflation, and I’m going to tell you how
FLASHCARD: We can find every American man and woman a job and I’m going to tell you how
FLASHCARD: We can win in Vietnam and I’m going to tell you how
FLASHCARD: You’re on your own, bud
Halfway through “Who Gets What” it starts to feel a lot like Alvin Roth is about to pull that type of stunt on his reader. He keeps talking about how he has an algorithm that will decide on fair kidney exchanges; an algorithm to place doctors with residency programs; an algorithm to place law students with the right clerkship; an algorithm to place kids at the right nursery in New York and the right public school in Boston. An algorithm that can’t be gamed. An algorithm that makes the market “thick.” An algorithm that prevents the market from going “early” or running into “congestion” but helps it stay “fast” and “safe”
On page 131 out of 230, while I’m despairing there’s ever going to be an algorithm in the book, but also secretly hoping it might bring about world peace or help me grow more hair on my scalp (to say nothing of knowing more about kidneys and kidney exchanges than I ever thought I would), comes some early relief in the form of the words “PART III: Design Inventions to Make Markets Smarter, Thicker and Faster.” Lo and behold, on page 141 the algorithm appears, as it’s meant to be applied to employers and applicants for jobs:
Step 0. Applicants and employers privately submit preferences to a clearinghouse in the form of rank order lists
Step 1. Each employer offers jobs to its top-choice candidates up to the number of its available positions. Each applicant looks at all the offers he or she has received, tentatively accepts the best one (the one highest on her preference list) and rejects any other
…
Step n. Each employer that had a job offer rejected in the previous step, offers that job to its next choice, if one remains. Each applicant considers the offer he or she has been holding together with his or her new offer(s) and tentatively accepts the most preferred of these. The applicant rejects any remaining offers –including possibly the one that had been tentatively accepted earlier but is no longer the best offer received.
The algorithm ends when no offer is rejected, so that no firm wants to make any additional offers. At that point, each applicant and employer is matched by having each applicant accept whatever offer he or she had most recently tentatively accepted. That is, all acceptances are deferred until the end, when no more offers are forthcoming
So there you have it. That’s the magic algorithm that won Alvin Roth the Nobel Prize. Yeah, I was underwhelmed too. But it’s apparently very clever.
The best thing about it is that after you go through these steps there aren’t any applicants and employers that aren’t matched to each other but wish they were. These guys, whenever they exist (after an inferior algorithm is used that allows them to occur) are very destabilizing, because they could potentially get on the phone to each other and bring the whole edifice down, so they have a special name, they are called “blocking pairs.”
The proof is as follows: suppose Athan got matched with Merrill but had ranked JP Morgan above Merrill. Well, that’s some tough dudu, because the way the algorithm works it’s clear JP Morgan filled up its analyst class before it got down to Athan, or else Athan would have switched from having tentatively accepted Merrill to accepting JP Morgan during the algorithm. So Athan never got shown JP Morgan, basically.
So the JP Morgan / Athan “blocking pair” does not exist and by similar logic neither does any other blocking pair.
Sadly, the author does not explain adequately why all’s good if there are no blocking pairs.
In particular, the author fails to demonstrate why there’s no point in strategically putting your second choice first if you are not a very strong candidate. He claims this is a nice feature of the algorithm, but if I was applying for a school spot for my kid and I knew this algorithm was being used, I’d still go conservative and put down my second choice first if it was good enough, to make sure I don’t get my third choice. In particular, I suspect the algorithm is not entirely bulletproof and requires a lot of agents on both sides to rank each other honestly. Perhaps I’m wrong but I’d like to see a proof. If you have one, PLEASE PLEASE PLEASE list it below.
Three fantastic chapters follow. One on signaling (example: the peacock’s tail, a long line outside a good restaurant), one on “repugnant” markets in goods or services that we think should not be traded (or, alternatively, not traded for money) and finally a truly exquisite final chapter on what a free market is and what it isn’t. I loved that chapter. It was worth the price of the book, and the pain I endured before I got to it.
And then the penny dropped. The guy wrote a meandering 167-page book about the algorithm and the publisher said “can we pad this out, perhaps” and the author added three more chapters he was saving for somewhere else.
How do I know? Page 105 the author states that “No companies have yet made a large-scale market for restaurant reservations as I write this in mid-2014,” yet on page 218 of the killer last chapter he discusses booking a restaurant on OpenTable, which was recently sold to Priceline for 2.7 billion dollars and (ask around) has already totally transformed the restaurant business in places like San Francisco, New York and London. Interesting, eh?
With all that said, this was a book well worth reading. For the humor, for the large number of awesome quotes (example, page 10 “Decisions that depend on what others are doing are called strategic decisions”) and for forcing me to think.
But it would have benefited from another round of editing. Still, this was a good book, if not a great book.