The Value of Shapley

Nobel laureate Lloyd Shapley passed away Saturday. We best know Shapley for his stable matching algorithm with David Gale. Nicole Immorlica guest posted on stable matching shortly after Gale's passing in 2008.

I'd like to talk about another great innovation, the Shapley Value, a solution concept for cooperative games. For example, suppose no candidate has a majority of candidates heading into the Republican convention and there is no winner on the first ballot. Now we have many delegates that might group themselves into coalitions, and a union of coalitions that have enough delegates can determine the nominee. Larger coalitions have more power than smaller ones but even a single delegate coalition could tip the election. The Shapley value gives weights to the coalitions that measures their relative power with some nice linear and symmetric properties. In this scenario, the Shapley value of a coalition is the probability that adding that coalition will tip the election when coalitions are added in a random order.

Game Theorist Robert Aumann, another Nobel laureate, used the Shapley value to predict winning coalitions in Israeli elections.

The main challenge of the Shapley value is computational, in general it is #P-complete to compute but it can be approximated efficiently.