Shapley value

Last updated

The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Prize in Economics for it in 2012. [1] [2] To each cooperative game 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. [3] [4]

Contents

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, followed by the price of stability, is precisely the Shapley value cost-sharing rule. [5]

Formal definition

Formally, a coalitional game is defined as: There is a set N (of n players) and a function 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, [6] the amount that player i gets 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. The formula can be interpreted as follows: imagine the coalition being formed one actor at a time, with each actor demanding their contribution (S∪{i}) − (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:

where the sum ranges over all orders of the players and is the set of players in which precede in the order . Finally, it can also be expressed as

which can be interpreted as

Examples

Business example

Consider a simplified description of a business. An owner, o, provides crucial capital in the sense that without him no gains can be obtained. There are k workers w1,...,wk, each of whom contributes an amount p to the total profit. Let

The value function for this coalitional game is

where m is the cardinality of . Computing the Shapley value for this coalition game leads to a value of kp/2 for the owner and p/2 for each worker.

Glove game

The glove game is a coalitional game where the players have left- and right-hand gloves and the goal is to form pairs. Let

where players 1 and 2 have right-hand gloves and player 3 has a left-hand glove.

The value function for this coalitional game is

The formula for calculating the Shapley value is

where R is an ordering of the players and is the set of players in N which precede i in the order R.

The following table displays the marginal contributions of Player 1.

Observe

By a symmetry argument it can be shown that

Due to the efficiency axiom, the sum of all the Shapley values is equal to 1, which means that

Properties

The Shapley value has many desirable properties.

Efficiency

The sum of the Shapley values of all agents equals the value of the grand coalition, so that all the gain is distributed among the agents:

Proof:

since is a telescoping sum and there are |N|! different orderings R.

Symmetry

If and are two actors who are equivalent in the sense that

for every subset of which contains neither nor , then .

This property is also called equal treatment of equals.

Linearity

If two coalition games described by gain functions and are combined, then the distributed gains should correspond to the gains derived from and the gains derived from :

for every in . Also, for any real number ,

for every in .

Null player

The Shapley value of a null player in a game is zero. A player is null in if for all coalitions that do not contain .

Given a player set , the Shapley value is the only map from the set of all games to payoff vectors that satisfies all four properties: Efficiency, Symmetry, Linearity, Null player.

Stand-alone test

If v is a subadditive set function, i.e., , then for each agent i: .

Similarly, if v is a superadditive set function, i.e., , then for each agent i: .

So, if the cooperation has positive externalities, all agents (weakly) gain, and if it has negative externalities, all agents (weakly) lose. [7] :147-156

Anonymity

If i and j are two agents, and w is a gain function that is identical to v except that the roles of i and j have been exchanged, then . This means that the labeling of the agents doesn't play a role in the assignment of their gains.

Marginalism

The Shapley value can be defined as a function which uses only the marginal contributions of player i as the arguments.

Characterization

The Shapley value not only has desirable properties, it is also the only payment rule satisfying some subset of these properties. For example, it is the only payment rule satisfying the four properties of Efficiency, Symmetry, Linearity and Null player. [8] See [7] :147-156 for more characterizations.

Aumann–Shapley value

In their 1974 book, Lloyd Shapley and Robert Aumann extended the concept of the Shapley value to infinite games (defined with respect to a non-atomic measure), creating the diagonal formula. [9] This was later extended by Jean-François Mertens and Abraham Neyman.

As seen above, the value of an n-person game associates to each player the expectation of his contribution to the worth or the coalition or players before him in a random ordering of all the players. When there are many players and each individual plays only a minor role, the set of all players preceding a given one is heuristically thought as a good sample of the players so that the value of a given infinitesimal player ds around as "his" contribution to the worth of a "perfect" sample of the population of all players.

Symbolically, if v is the coalitional worth function associating to each coalition c measured subset of a measurable set I that can be thought as without loss of generality.

where denotes the Shapley value of the infinitesimal player ds in the game, tI is a perfect sample of the all-player set I containing a proportion t of all the players, and is the coalition obtained after ds joins tI. This is the heuristic form of the diagonal formula.

Assuming some regularity of the worth function, for example assuming v can be represented as differentiable function of a non-atomic measure on I, μ, with density function , with ( the characteristic function of c). Under such conditions

,

as can be shown by approximating the density by a step function and keeping the proportion t for each level of the density function, and

The diagonal formula has then the form developed by Aumann and Shapley (1974)

Above μ can be vector valued (as long as the function is defined and differentiable on the range of μ, the above formula makes sense).

In the argument above if the measure contains atoms is no longer true—this is why the diagonal formula mostly applies to non-atomic games.

Two approaches were deployed to extend this diagonal formula when the function f is no longer differentiable. Mertens goes back to the original formula and takes the derivative after the integral thereby benefiting from the smoothing effect. Neyman took a different approach. Going back to an elementary application of Mertens's approach from Mertens (1980): [10]

This works for example for majority games—while the original diagonal formula cannot be used directly. How Mertens further extends this by identifying symmetries that the Shapley value should be invariant upon, and averaging over such symmetries to create further smoothing effect commuting averages with the derivative operation as above. [11] A survey for non atomic value is found in Neyman (2002) [12]

Generalization to coalitions

The Shapley value only assigns values to the individual agents. It has been generalized [13] [ irrelevant citation ] to apply to a group of agents C as,

See also

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".

Normal distribution Probability distribution

In probability theory, a normaldistribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

In probability theory, the central limit theorem (CLT) establishes that, in some situations, when independent random variables are added, their properly normalized sum tends toward a normal distribution even if the original variables themselves are not normally distributed. The theorem is a key concept in probability theory because it implies that probabilistic and statistical methods that work for normal distributions can be applicable to many problems involving other types of distributions.

Navier–Stokes equations Equations describing the motion of viscous fluid substances

In physics, the Navier–Stokes equations, named after French engineer and physicist Claude-Louis Navier and British physicist and mathematician George Gabriel Stokes, describe the motion of viscous fluid substances.

Eulers totient function function which gives the number of integers relatively prime to its input

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ kn for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.

Noethers theorem Statement relating differentiable symmetries to conserved quantities

Noether's theorem or Noether's first theorem states that every differentiable symmetry of the action of a physical system has a corresponding conservation law. The theorem was proven by mathematician Emmy Noether in 1915 and published in 1918, after a special case was proven by E. Cosserat and F. Cosserat in 1909. The action of a physical system is the integral over time of a Lagrangian function, from which the system's behavior can be determined by the principle of least action. This theorem only applies to continuous and smooth symmetries over physical space.

In the mathematical field of differential geometry, a metric tensor is a type of function which takes as input a pair of tangent vectors v and w at a point of a surface and produces a real number scalar g(v, w) in a way that generalizes many of the familiar properties of the dot product of vectors in Euclidean space. In the same way as a dot product, metric tensors are used to define the length of and angle between tangent vectors. Through integration, the metric tensor allows one to define and compute the length of curves on the manifold.

The Klein–Gordon equation is a relativistic wave equation, related to the Schrödinger equation. It is second-order in space and time and manifestly Lorentz-covariant. It is a quantized version of the relativistic energy–momentum relation. Its solutions include a quantum scalar or pseudoscalar field, a field whose quanta are spinless particles. Its theoretical relevance is similar to that of the Dirac equation. Electromagnetic interactions can be incorporated, forming the topic of scalar electrodynamics, but because common spinless particles like the pions are unstable and also experience the strong interaction the practical utility is limited.

Jensens inequality Theorem of convex functions

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context, some of which are presented below. In its simplest form the inequality states that the convex transformation of a mean is less than or equal to the mean applied after convex transformation; it is a simple corollary that the opposite is true of concave transformations.

In mathematics, the Jacobi elliptic functions are a set of basic elliptic functions, and auxiliary theta functions, that are of historical importance. They are found in the description of the motion of a pendulum, as well as in the design of the electronic elliptic filters. While trigonometric functions are defined with reference to a circle, the Jacobi elliptic functions are a generalization which refer to other conic sections, the ellipse in particular. The relation to trigonometric functions is contained in the notation, for example, by the matching notation sn for sin. The Jacobi elliptic functions are used more often in practical problems than the Weierstrass elliptic functions as they do not require notions of complex analysis to be defined and/or understood. They were introduced by Carl Gustav Jakob Jacobi (1829).

Total variation Measure of the local oscillation behavior of a function

In mathematics, the total variation identifies several slightly different concepts, related to the structure of the codomain of a function or a measure. For a real-valued continuous function f, defined on an interval [a, b] ⊂ ℝ, its total variation on the interval of definition is a measure of the one-dimensional arclength of the curve with parametric equation xf(x), for x ∈ [a, b].

In quantum field theory, a quartic interaction is a type of self-interaction in a scalar field. Other types of quartic interactions may be found under the topic of four-fermion interactions. A classical free scalar field satisfies the Klein–Gordon equation. If a scalar field is denoted , a quartic interaction is represented by adding a potential term to the Lagrangian density. The coupling constant is dimensionless in 4-dimensional spacetime.

In statistics, econometrics and signal processing, an autoregressive (AR) model is a representation of a type of random process; as such, it is used to describe certain time-varying processes in nature, economics, etc. The autoregressive model specifies that the output variable depends linearly on its own previous values and on a stochastic term ; thus the model is in the form of a stochastic difference equation. Together with the moving-average (MA) model, it is a special case and key component of the more general autoregressive–moving-average (ARMA) and autoregressive integrated moving average (ARIMA) models of time series, which have a more complicated stochastic structure; it is also a special case of the vector autoregressive model (VAR), which consists of a system of more than one interlocking stochastic difference equation in more than one evolving random variable.

Folded normal distribution probability distribution

The folded normal distribution is a probability distribution related to the normal distribution. Given a normally distributed random variable X with mean μ and variance σ2, the random variable Y = |X| has a folded normal distribution. Such a case may be encountered if only the magnitude of some variable is recorded, but not its sign. The distribution is called "folded" because probability mass to the left of the x = 0 is folded over by taking the absolute value. In the physics of heat conduction, the folded normal distribution is a fundamental solution of the heat equation on the upper plane.

Alternatives to general relativity are physical theories that attempt to describe the phenomenon of gravitation in competition to Einstein's theory of general relativity. There have been many different attempts at constructing an ideal theory of gravity.

In mathematics, the Fortuin–Kasteleyn–Ginibre (FKG) inequality is a correlation inequality, a fundamental tool in statistical mechanics and probabilistic combinatorics, due to Cees M. Fortuin, Pieter W. Kasteleyn, and Jean Ginibre (1971). Informally, it says that in many random systems, increasing events are positively correlated, while an increasing and a decreasing event are negatively correlated. It was obtained by studying the random cluster model.

In mathematics, the ATS theorem is the theorem on the approximation of a trigonometric sum by a shorter one. The application of the ATS theorem in certain problems of mathematical and theoretical physics can be very helpful.

In mathematics, the Pettis integral or Gelfand–Pettis integral, named after Israel M. Gelfand and Billy James Pettis, extends the definition of the Lebesgue integral to vector-valued functions on a measure space, by exploiting duality. The integral was introduced by Gelfand for the case when the measure space is an interval with Lebesgue measure. The integral is also called the weak integral in contrast to the Bochner integral, which is the strong integral.

In mathematics, the method of steepest descent or stationary-phase method or saddle-point method is an extension of Laplace's method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point, in roughly the direction of steepest descent or stationary phase. The saddle-point approximation is used with integrals in the complex plane, whereas Laplace’s method is used with real integrals.

Lagrangian field theory is a formalism in classical field theory. It is the field-theoretic analogue of Lagrangian mechanics. Lagrangian mechanics is used to analyze the motion of a system of discrete particles each with a finite number of degrees of freedom. Lagrangian field theory applies to continua and fields, which have an infinite number of degrees of freedom.

References

  1. Shapley, Lloyd S. (August 21, 1951). "Notes on the n-Person Game -- II: The Value of an n-Person Game" (PDF). Santa Monica, Calif.: RAND Corporation.
  2. Roth, Alvin E., ed. (1988). The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511528446. ISBN   0-521-36177-X.
  3. Hart, Sergiu (1989). "Shapley Value". In Eatwell, J.; Milgate, M.; Newman, P. (eds.). The New Palgrave: Game Theory. Norton. pp. 210–216. doi:10.1007/978-1-349-20181-5_25. ISBN   978-0-333-49537-7.
  4. Hart, Sergiu (May 12, 2016). "A Bibliography of Cooperative Games: Value Theory".
  5. Phillips, Matthew; Marden, Jason R. (July 2018). "Design Tradeoffs in Concave Cost-Sharing Games". IEEE Transactions on Automatic Control. 63 (7): 2242–2247. doi:10.1109/tac.2017.2765299. ISSN   0018-9286.
  6. For a proof of unique existence, see Ichiishi, Tatsuro (1983). Game Theory for Economic Analysis. New York: Academic Press. pp. 118–120. ISBN   0-12-370180-5.
  7. 1 2 Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN   9780262134231.
  8. Shapley, Lloyd S. (1953). "A Value for n-person Games". In Kuhn, H. W.; Tucker, A. W. (eds.). Contributions to the Theory of Games. Annals of Mathematical Studies. 28. Princeton University Press. pp. 307–317. doi:10.1515/9781400881970-018. ISBN   9781400881970.
  9. Aumann, Robert J.; Shapley, Lloyd S. (1974). Values of Non-Atomic Games. Princeton: Princeton Univ. Press. ISBN   0-691-08103-4.
  10. Mertens, Jean-François (1980). "Values and Derivatives". Mathematics of Operations Research. 5 (4): 523–552. doi:10.1287/moor.5.4.523. JSTOR   3689325.
  11. Mertens, Jean-François (1988). "The Shapley Value in the Non Differentiable Case". International Journal of Game Theory. 17 (1): 1–65. doi:10.1007/BF01240834.
  12. Neyman, A., 2002. Value of Games with infinitely many Players, "Handbook of Game Theory with Economic Applications," Handbook of Game Theory with Economic Applications, Elsevier, edition 1, volume 3, number 3, 00. R.J. Aumann & S. Hart (ed.).
  13. Owen, Guillermo (1972). "Multilinear Extensions of Games". Management Science. 18 (5): 64–79. doi:10.1287/mnsc.18.5.64. hdl: 10338.dmlcz/135728 .

Further reading