Shapley, Roth, Matching and Markets
Today, the Nobel Prize in Economics went to Shapley and Roth for their work in matching methods.
Shapley's original theoretical work was solving the "Stable Marriage Problem". The idea's pretty simple. Suppose we have 3 men and 3 women, and we want there to be 3 marriages such that there is no mutually beneficial match that's better than the matches that actually occur. Shapley's work was developing an algorithm for solving that problem.
Here's how it works:
Each round, any man who isn't currently "engaged" proposes to their most preferred woman that they've not yet been rejected by.
Then, each woman says "maybe" to their most preferred suitor, and "no" to other suitors. If they say "maybe", the two are engaged.
If any men are not engaged at the end of that round, then we do another one.
An example:
Three men: Alan, Bill, and Carson. Three women: Xena, Yolanda, and Zelda. Each of them have preferences like this:
Alan: Yolanda > Zelda > Xena
Bill: Yolanda > Xena > Zelda
Carson: Xena > Zelda > Yolanda
Xena: Alan > Bill > Carson
Yolanda: Bill > Carson > Alan
Zelda: Carson > Alan > Bill
Round 1:
Alan - proposes to Yolanda
Bill - proposes to Yolanda
Carson - proposes to Xena
Yolanda - "maybe" to Bill, "no" to Alan.
Xena - "maybe" to Carson
Provisional matches:
Xena & Carson
Yolanda & Bill
Alan - not engaged.
Round 2:
Alan - proposes to Zelda
Zelda - "maybe" to Alan.
Ending matches:
Xena & Carson
Yolanda & Bill
Zelda & Alan
Each of these marriages is "stable". Xena would prefer either of the men to Carson - but neither of them would jilt their current wives for her. Carson got his first choice. Yolanda got her first choice. Bill got his first choice. Zelda would jilt Alan for Carson - but he's not interested. Alan would jilt Zelda for Yolanda - but she's not interested.
So, the matches are all "stable". There is no pairing where BOTH members of the pair are willing to jilt their current spouses to be together. In economic terms, we'd say that the matching is "Pareto optimal" - the only way to make one of these people better off is to make another worse off - so no one will willingly change anything.
Now, we know that this isn't really how marriage works - though it is weirdly close... But, it is an important matching algorithm nonetheless, as it is pretty simple to implement and results in matches that are pretty good, on the whole.
Roth's contribution, then, was taking the algorithm designed by Shapley and apply it to a number of cases. For example, he applies it to a school system with multiple schools. Students could express preferences for schools, and schools had preferences for students. Using a slight modification of Shapley's algorithm to allow for multiple "maybes" makes the problem relatively easy to solve, and allows for much better matching than a totally random assignment process. Medical students applying for residency go through a matching system that is centered on a Shapley-style algorithm. This type of algorithm is also being considered for organ donor matches.
To me, though, the most amazing thing is that the work of Shapley and Roth is so limited in its application. I'm not saying it's unimportant - their work solves a very specific problem in a way that's pretty good. The amazing thing, though, is that it's so rarely the way that we have to solve these kinds of problems. Why?
Because their work only applies where there isn't a market that includes money. Once you throw monetary exchange into the mix, the Shapley algorithm isn't required. Prices solve the problem.
Why? Because prices allow people to "make change" between options. For example, when looking for a job, I had a sense of which jobs I'd really like to have and which I'd less enjoy. Also, the various schools figured out who they wanted to hire. So, if I got two offers, I'd say "This is at a less desirable school, but pays enough more to be worth it." or maybe they didn't pay me enough more to be worth it. Through the pricing process, I'm willing to accept options below my first choice if there's a sufficient salary difference. Similarly for the schools and the offers they make - they're willing to hire a less desirable candidate, if they will accept a low enough salary. This ends up striking a balance between worker and employer preferences - not unlike how the Shapley algorithm balances men's and women's preferences.
Another interesting thing: the price system ensures a greater chance of a match the better the match is. Think of it this way: for any job, there's a minimum salary that will make me willing to do the job. For any worker, there's a maximum the employer is willing to pay to hire them. If I love the job, my minimum acceptable salary will be very low. If the employer really loves the worker, the maximum willingness to pay is very high. Result: if it's a great match, there's a wide range of salaries that both employer and employee find acceptable. On the other hand, if it's a lousy match, there may be no range of salaries that both find acceptable. (If it's high enough to satisfy the employee, it's too high for the employer. If it's low enough to satisfy the employer, it's too low for the employee.) But, that only happens if the employer and/or employee require a very high premium to hire the worker or accept the job.
People who aren't amazed by the wonderful coordinating function of prices and negotiation have clearly not thought enough about it. For thousands of years, they've been doing something that we only explicitly designed about 50 years ago - and on a much broader scale.
Shapley's original theoretical work was solving the "Stable Marriage Problem". The idea's pretty simple. Suppose we have 3 men and 3 women, and we want there to be 3 marriages such that there is no mutually beneficial match that's better than the matches that actually occur. Shapley's work was developing an algorithm for solving that problem.
Here's how it works:
Each round, any man who isn't currently "engaged" proposes to their most preferred woman that they've not yet been rejected by.
Then, each woman says "maybe" to their most preferred suitor, and "no" to other suitors. If they say "maybe", the two are engaged.
If any men are not engaged at the end of that round, then we do another one.
An example:
Three men: Alan, Bill, and Carson. Three women: Xena, Yolanda, and Zelda. Each of them have preferences like this:
Alan: Yolanda > Zelda > Xena
Bill: Yolanda > Xena > Zelda
Carson: Xena > Zelda > Yolanda
Xena: Alan > Bill > Carson
Yolanda: Bill > Carson > Alan
Zelda: Carson > Alan > Bill
Round 1:
Alan - proposes to Yolanda
Bill - proposes to Yolanda
Carson - proposes to Xena
Yolanda - "maybe" to Bill, "no" to Alan.
Xena - "maybe" to Carson
Provisional matches:
Xena & Carson
Yolanda & Bill
Alan - not engaged.
Round 2:
Alan - proposes to Zelda
Zelda - "maybe" to Alan.
Ending matches:
Xena & Carson
Yolanda & Bill
Zelda & Alan
Each of these marriages is "stable". Xena would prefer either of the men to Carson - but neither of them would jilt their current wives for her. Carson got his first choice. Yolanda got her first choice. Bill got his first choice. Zelda would jilt Alan for Carson - but he's not interested. Alan would jilt Zelda for Yolanda - but she's not interested.
So, the matches are all "stable". There is no pairing where BOTH members of the pair are willing to jilt their current spouses to be together. In economic terms, we'd say that the matching is "Pareto optimal" - the only way to make one of these people better off is to make another worse off - so no one will willingly change anything.
Now, we know that this isn't really how marriage works - though it is weirdly close... But, it is an important matching algorithm nonetheless, as it is pretty simple to implement and results in matches that are pretty good, on the whole.
Roth's contribution, then, was taking the algorithm designed by Shapley and apply it to a number of cases. For example, he applies it to a school system with multiple schools. Students could express preferences for schools, and schools had preferences for students. Using a slight modification of Shapley's algorithm to allow for multiple "maybes" makes the problem relatively easy to solve, and allows for much better matching than a totally random assignment process. Medical students applying for residency go through a matching system that is centered on a Shapley-style algorithm. This type of algorithm is also being considered for organ donor matches.
To me, though, the most amazing thing is that the work of Shapley and Roth is so limited in its application. I'm not saying it's unimportant - their work solves a very specific problem in a way that's pretty good. The amazing thing, though, is that it's so rarely the way that we have to solve these kinds of problems. Why?
Because their work only applies where there isn't a market that includes money. Once you throw monetary exchange into the mix, the Shapley algorithm isn't required. Prices solve the problem.
Why? Because prices allow people to "make change" between options. For example, when looking for a job, I had a sense of which jobs I'd really like to have and which I'd less enjoy. Also, the various schools figured out who they wanted to hire. So, if I got two offers, I'd say "This is at a less desirable school, but pays enough more to be worth it." or maybe they didn't pay me enough more to be worth it. Through the pricing process, I'm willing to accept options below my first choice if there's a sufficient salary difference. Similarly for the schools and the offers they make - they're willing to hire a less desirable candidate, if they will accept a low enough salary. This ends up striking a balance between worker and employer preferences - not unlike how the Shapley algorithm balances men's and women's preferences.
Another interesting thing: the price system ensures a greater chance of a match the better the match is. Think of it this way: for any job, there's a minimum salary that will make me willing to do the job. For any worker, there's a maximum the employer is willing to pay to hire them. If I love the job, my minimum acceptable salary will be very low. If the employer really loves the worker, the maximum willingness to pay is very high. Result: if it's a great match, there's a wide range of salaries that both employer and employee find acceptable. On the other hand, if it's a lousy match, there may be no range of salaries that both find acceptable. (If it's high enough to satisfy the employee, it's too high for the employer. If it's low enough to satisfy the employer, it's too low for the employee.) But, that only happens if the employer and/or employee require a very high premium to hire the worker or accept the job.
People who aren't amazed by the wonderful coordinating function of prices and negotiation have clearly not thought enough about it. For thousands of years, they've been doing something that we only explicitly designed about 50 years ago - and on a much broader scale.