A puzzling man
The strategy games and mental puzzles Lloyd Shapley always loved are still stacked neatly on a small side table. Here in Tucson, Arizona, Shapley lived his last years being cared for by his son, Peter, and his wife. These mental puzzles are an important memory, Peter tells us. Not only of Shapley himself, but also of Peter’s childhood with his father. “When the Rubik’s cube came out,” Peter remembers, “he would just stare at it for a long time and make a few moves, stare at it again for a long time and make a few more moves, and then make a few more and be done and say ‘I solved it in 20 moves’.” He smiles. “And I was thinking: It takes me 200 moves, but I can do it a lot faster. But, as a mathematician, he would look for the optimal solution, which isn’t always the fastest one. He was good at that.”
Can Game Theory help survive life in the army?
Shapley showed his mathematical skills, and his passion for mind puzzles, by inventing a strategy game himself; ‘So Long Sucker’ was published in 1950. During his time in the army, he was able to establish his location and sent coded messages to his family. Since he was drafted into the army out of Harvard, his superiors were smart enough to use his know-how in support roles instead of on the battlefield. Peter tells us that his father used to: “Break codes and figure out things like that. They were trying to consolidate weather reports from everywhere to figure out what the weather would be like over Japan in a few days.”
Finding your big love using an algorithm
Peter tells us honestly that he has only a vague idea of Shapley’s contributions to Game Theory. Maybe this is because Shapley, as he himself knew, was not a very good teacher, of undergraduates at least. Peter recalls that: “He spoke at a level beyond that of high school students or even most college undergraduates.” What he does know about his father’s theories is that the so-called ‘marriage problem’ has nothing to do with marriage. It’s just a metaphor for paring up people or groups.
But if Lloyd Shapley wasn’t able to explain his own theories to a non-economist, who can?
Get new questions as they launch
We meet Alvin Roth, Shapley’s co-Laureate, in his office in Stanford. He pays tribute to the marriage problem, since it was the basis for his own work which was honored with the Nobel Prize. Shapley’s algorithm, Roth explains, allowed him to find stable matchings, not for men and women but, for example, for school children and schools, or doctors and residency programs. Roth explains that men and women provide the simplest way to illustrate the way the algorithm works, and he dives into the case in which partners start to rank each other.
How can we make a good match?
“Every man proposes to the woman who’s his first choice to marry. And every woman who receives multiple proposals rejects all but the one she likes best. And she doesn’t accept that one yet, that’s why this is called a deferred-acceptance algorithm. She defers a decision on that one, doesn’t reject him.” Every man who’s been rejected at the previous step will propose to their next choice of woman. “And every woman looks at every proposal she has gotten so far without regard to when it came in,” Roth says. “She orders the people who have proposed to her according to preferences. She keeps the one she prefers and rejects the rest. And defers a decision on the one she likes the most.”
According to the algorithm Shapley formulated with fellow economist David Gale, when no more proposals are made, every man will be married to the woman who is holding his proposal, if there is one. And men whose proposals are not being held are single, as well as the women who are also without a proposal. “What Gale and Shapley proved is regardless of what preferences you started with,” Roth explains, “the deferred-acceptance algorithm produces a stable matching.”
Is it possible to forecast the outcome of a game?
Lloyd Shapley had an intense friendship, and collaborated intensely with mathematician and game theorist Robert Aumann. His son, Peter, still remembers all the times his father and Aumann fought “about one single comma for hours”.
As we meet Aumann in Zurich, he mentions that his friend should have received the Nobel Prize before all other game theorists, because his work was the foundation upon which they all stand. Together, they defined the Aumann-Shapley Value, which builds upon Shapley’s most famous work: the Shapley Value, a way of evaluating a game situation before the game gets played. It can help decide, for example, if you would rather play the game, or go and have lunch.
Aumann demonstrates how the value works using a modern device, his cellphone. “If you look at this device and look at the weather, on Wednesday it says thunderstorms. It will tell you there’s a 60 percent chance of a thunderstorm at 4 o’clock. So what can I expect at 4 o’clock?” Aumann asks. “So, it’s 60 percent thunderstorm, 40 percent sunny weather. It’s an estimate, an expectation.” Applied to a game, Aumann adds, the Shapley Value looks at power relationships and analyzes them.
What does Shapley’s work teach us about elections?
Shapley liked to solve problems on paper, then he left others to apply his work to real-life approaches. As Peter admits, he liked to solve a problem and walk away, to look for a new one.
In what became known as the Shapley-Shubik index, the Shapley value became the default guide to analyzing all kinds of electoral situations. “He came up with a concept and proved mathematically that the voters in the medium-sized states have more power in the election of a president,” Peter explains.
Aumann cites the United Nations Security Council as an example. “We have five veto powers: the United States, the United Kingdom, Russia, China and France,” he says. “There are ten others with no veto power. So you work out the power relationships: 98 percent of the Shapley Value lies with the big five. One would say, veto, it’s not so important. Well, it’s very important!“
A parliamentary democracy that consists of one large and many small parties can also be used to see how power is distributed according to the Shapley-Shubik index. “A large party has maybe one third of the votes, and the small parties split the other two thirds,” explains Aumann. “Now the large party has one third of the votes but half the power. In unity there is power.” Then he reverses it, where two large parties each have one third of the votes and the many small parties share the remaining one third. “In that case, in unity there is a lack of power. Because in that case the power of the small parties is bigger. The big parties, who each have one third only, have a quarter of the power, while half of the power is spread among the small parties.”