Lloyd Shapley

The father of game theory is a puzzling man

The strategy games and brainteasers Shapley loved are still stacked neatly on a small side table. Tucson, Arizona is where Shapley lived his final years while being cared for by his son Peter and his wife. These 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, he would just stare at it for a long time and make a few moves, stare at it again and make a few more moves and then be done and say ‘I solved it in 20 moves,’” Peter remembers. “And I was thinking it takes me 200 moves but I can do it a lot faster. As a mathematician, he would look for the optimal solution, which isn’t always the fastest one. He was good at that.”

Shapley showed his mathematical skills, and his passion for puzzles, by inventing a strategy game himself alongside a few friends, including Nash, called So Long Sucker in 1950.

Can Game Theory help survive life in the army?

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

Can an algorithm help us find true love?

Peter tells us honestly that he has only a vague idea of his father’s contributions to game theory. Maybe this is because Shapley, as he himself knew, was not a very good teacher. “He spoke at a level beyond that of high school students or even most college undergraduates,” recalls Peter. What he does know about his father’s theories is that the stable marriage problem has nothing to do with marriage. It’s just a metaphor for paring up people or groups.

But if Shapley wasn’t able to explain his own theories to a non-economist, who can?

We meet Alvin Roth, Shapley’s co-laureate, in his office at 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 school children and schools and for doctors and residency programs. Roth says that men and women provide the simplest way to illustrate the way the algorithm works as he dives into an example.

How can we make a good match?

“Every man proposes to the woman who’s his first choice to marry,” he begins. “And every woman who receives multiple proposals rejects all but the one she likes best. When she doesn’t accept that one yet, this is called a deferred-acceptance algorithm. She defers a decision on that one, doesn’t reject him.”

According to the algorithm Shapley invented 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, along with the women who are also without a proposal. “What Gale and Shapley proved is regardless of what preferences you started with, the deferred-acceptance algorithm produces a stable matching,” says Roth.

Letter between Shapley and Gale that defined the algorithm

Is it possible to forecast the outcome of a game?

Shapley also collaborated closely with his friend mathematician and game theorist Robert Aumann. Peter still remembers all the times his father and Aumann fought “about one single comma for hours.”

Aumann says that Shapley should have received the Nobel Prize before all other game theorists because his work was the foundation upon which they all stand. Together, the two defined the Aumann-Shapley value. It built upon Shapley’s most famous work, the Shapley value, which is 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.

Shapley liked to solve problems on paper but often left implementing real world approaches to others. As Peter admits, he liked to solve a problem and walk away, searching for a new one.

What does Shapley’s work teach us about elections?

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. 

“We have five veto powers. The United States, the United Kingdom, Russia, China and France,” says Aumann, referring to the United Nations Security Council. “There are 10 others with no veto power. So you work out the power relationships. Ninety-eight percent of the Shapley value lies with the big five. One would say veto is not so important. Well, it’s very important.”

Photo of Lloyd Shapley, Peter Shapley and President Obama

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

Master of Games: Who was Lloyd Shapley?

Shapley grew up during the Great Depression and was a passionate democrat all his life. Peter proudly presents the photo of him, his father and former US president Barack Obama who Shapley loved. “I remember a few years ago, I was driving with him down the freeway and he saw a sign that said ‘This project was funded by the American Recovery Act’ and he said, ‘That’s good, that’s why I became a democrat, 'cause that’s what they were doing in 1932’.”

While walking through Sabino Canyon in Tucson, a place where both father and son often walked together, Peter reflects on his father’s last few days. Receiving the Nobel Prize was the defining event of his father’s life. “But I don’t think he ever wanted it to be the last thing,” says Peter.