Game Theory, Cooperation and Shapley Value

The only thing that will redeem mankind is cooperation.”

– Bertrand Russell

Lloyd Shapley is an American economist. He has made significant contribution to fields of mathematical economics, especially game theory. In 2012 he won Nobel Prize in Economics (which he shared with Alvin Roth.)

In game theory, a cooperative game is a game where groups of players or coalitions behave in cooperative manner while choosing strategy ex. they may work on project which is mutually beneficial to them and workout strategy to fairly distribute both gains and cost among themselves.

coalition%20cartoon%20thumbnail%20crop

Distribution of gains or cost is easy if contribution of all players is equal. But if it is unequal then some other method is required. Shapley has made significant contribution in this area of game theory. The Shapley value applies primarily in situations when the contributions of each actor are unequal. The Shapley value ensures each actor ends up spending less, than they would have if they had acted independently. This is important, because otherwise there is no incentive for actors to collaborate.

“Competition has been shown to be useful up to a certain point and no further, but cooperation, which is the thing we must strive for today, begins where competition leaves off.”

– Franklin D. Roosevelt

A famous example of the Shapley value in practice is the airport runway problem.

In the problem, an airport needs to be built airstrip to accommodate a range of aircraft which require different lengths of runway. Cost of building each runway is different. The question is how to distribute the costs of the airport among all actors in an fair manner.

The solution is given below, which calculates the Shapley value.

shapley value

If players do not cooperate then they will have to build runway on their own ( cost will vary from 4 units to 16 units), but if they cooperate then they have to build only one strip that will cost them 16 units, now question is how do they share the cost among themselves.

article-2151985-0250E20D00000578-217_468x325

First player A’s (4 units, also least cost) cost is equally shared among all players. Next marginal cost of player B is equally shared among 3 players, then marginal cost of player C is shared among 2 players and finally player D bears the remaining marginal cost. Adding marginal costs (row wise) will tell how much each player will have to pay (which is the Shapley value).

In the end, actors requiring a shorter runway pay less, and those needing a longer runway pay more.

We find that Shapley value for each player is not only fair, but also less than what they would have spent individually if they had not cooperated.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s