The Shapley value is a
solution concept
In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most comm ...
in cooperative
game theory. It was named in honor of
Lloyd Shapley
Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
, who introduced it in 1951 and won the
Nobel Memorial Prize in Economic Sciences
The Nobel Memorial Prize in Economic Sciences, officially the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel ( sv, Sveriges riksbanks pris i ekonomisk vetenskap till Alfred Nobels minne), is an economics award administered ...
for it in 2012. To each
cooperative game Cooperative game may refer to:
* Cooperative board game, board games in which players work together to achieve a common goal
* Cooperative game theory, in game theory, a game with competition between groups of players and the possibility of cooperat ...
it assigns a unique distribution (among the players) of a total surplus generated by the coalition of all players. The Shapley value is characterized by a collection of desirable properties. Hart (1989) provides a survey of the subject.
The setup is as follows: a coalition of players cooperates, and obtains a certain overall gain from that cooperation. Since some players may contribute more to the coalition than others or may possess different bargaining power (for example threatening to destroy the whole surplus), what final distribution of generated surplus among the players should arise in any particular game? Or phrased differently: how important is each player to the overall cooperation, and what payoff can he or she reasonably expect? The Shapley value provides one possible answer to this question.
For cost-sharing games with concave cost functions, the optimal cost-sharing rule that optimizes the
price of anarchy The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of effici ...
, followed by the
price of stability
In game theory, the price of stability (PoS) of a game is the ratio between the best objective function value of one of its equilibria and that of an optimal outcome. The PoS is relevant for games in which there is some objective authority that ...
, is precisely the Shapley value cost-sharing rule. (A symmetrical statement is similarly valid for utility-sharing games with convex utility functions.) In
mechanism design
Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts a ...
, this means that the Shapley value solution concept is optimal for these sets of games.
Formal definition
Formally, a coalitional game is defined as:
There is a set ''N'' (of ''n'' players) and a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
that maps subsets of players to the real numbers:
, with
, where
denotes the empty set. The function
is called a characteristic function.
The function
has the following meaning: if ''S'' is a coalition of players, then
(''S''), called the worth of coalition ''S'', describes the total expected sum of payoffs the members of
can obtain by cooperation.
The Shapley value is one way to distribute the total gains to the players, assuming that they all collaborate. It is a "fair" distribution in the sense that it is the only distribution with certain desirable properties listed below. According to the Shapley value, the amount that player ''i'' is given in a coalitional game
is
:
:
where ''n'' is the total number of players and the sum extends over all subsets ''S'' of ''N'' not containing player ''i''. Also note that
is the
multinomial coefficient
In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.
Theorem
For any positive integer ...
. The formula can be interpreted as follows: imagine the coalition being formed one actor at a time, with each actor demanding their contribution
(''S''∪) −
(''S'') as a fair compensation, and then for each actor take the average of this contribution over the possible different
permutations in which the coalition can be formed.
An alternative equivalent formula for the Shapley value is:
: