For a coalitional game, restriction to the remaining players preserves coalition values. Remove player from a uniformly random ordering when comparing player 's Shapley value. The marginal contribution changes only when precedes . If is the set of other predecessors, the change is , with coefficient . The same expression and coefficient arise after interchanging , proving balanced contributions.
Cooperative cost game 2026-10-31
A transferable utility game formulated as costs to be shared among members of each coalition , with . Its cost core consists of payment vectors satisfying the displayed efficiency and coalition inequalities, where . A coalition should not be charged more than its standalone cost. Changing signs to and converts these conditions to the usual benefit-game core of a cooperative game. The Shapley value can be applied directly to costs, giving payments whose sum is .
Cooperative game theory Created 2026-10-06 Updated 2026-10-07
Cooperative game theory studies what groups of players can achieve together and how their joint value can be allocated. A transferable utility game assigns a real value to each coalition. The core of a cooperative game asks which allocations no coalition can improve upon; the Shapley value averages marginal contributions across player orderings.
Dual coalitional game Created 2026-10-07 Updated 2026-10-14
Duality assigns a coalition the grand-coalition value less the value of its complement. For a normalized transferable utility game, the dual is normalized and taking the dual twice recovers the original game. A player's dual marginal contribution at predecessor set equals its original contribution at the complementary predecessor set in . This preserves the Shapley value.
The Shapley value is a linear map on real characteristic functions with zero value at the empty coalition. In each player permutation, the marginal contribution to is times the marginal to plus times the marginal to . Taking their expectations proves the formula for arbitrary real . This directly proves real homogeneity as well as cooperative-game additivity.
Lloyd Shapley Created 2026-10-18 Updated 2026-11-05
Lloyd Shapley was a mathematician whose work helped shape game theory and the mathematical study of matching markets. His research on stable matching with David Gale supplied an existence theorem and a constructive procedure, while the Shapley value gives a systematic way to allocate the value created by cooperation.[ref] The Shapley value averages each participant's marginal contribution over all orders in which a group might form. This makes a fairness rule precise through combinatorics, rather than selecting a division solely by bargaining strength or an arbitrary order of arrival.
Marginal contribution Created 2026-10-06 Updated 2026-10-07
A player's marginal contribution to a coalition is the increase in its value when that player joins. In a convex cooperative game, marginal contributions increase with the preceding coalition. Averaging contributions across player orderings gives the Shapley value.
Marginal contribution vector Created 2026-10-06 Updated 2026-10-07
For a player ordering , is the set before player , and the displayed entries form its marginal contribution vector. Their sum is . The Shapley value is the average of these vectors. In a convex cooperative game, increasing marginal contributions make each such vector satisfy every coalition constraint of the core of a cooperative game.
For three distinct players in a normalized simple cooperative game, enumerate the predecessor coalitions in the Shapley value formula:
Subtracting the formula with and exchanged proves the displayed identity. Every coalition value is zero or one, so is an integer. This rules out, for example, coordinates differing by , although each may separately satisfy the Shapley value denominator in a simple game. The difference identity itself holds for arbitrary three-player transferable utility games; the integer restriction uses the zero-one values.
For an -player transferable utility game with , the Shapley value is
It averages player 's marginal contribution over uniformly random orders of all players. Exactly of the permutations put precisely before . For a cooperative cost game, apply the same linear formula to the cost function; the result represents payments instead of distributed benefits.
Take three players and define the simple cooperative game
It is a superadditive coalitional game: two disjoint coalitions cannot both have value one because each would need player 1. If one has value one, their union does too; if neither does, the desired inequality is immediate.
The vector belongs to the core of a cooperative game. More strongly, it is the unique core vector: singleton constraints give nonnegative coordinates, efficiency gives sum one, and the value-one coalitions and force .
In a random player ordering, player 1 is pivotal unless it comes first, giving Shapley value . Player 2 is pivotal only in order , and player 3 only in order . Thus
The coalition receives only , so the Shapley value is outside the core. This proves that superadditivity and nonempty core do not imply Shapley stability.
Remove any plane types with zero count, retaining the increasing order of the remaining lengths; if none remain, return the empty allocation. For the retained types put and . Then every plane of type has Shapley value
Compute suffix counts in a backward pass. In a forward pass, accumulate and output as the common payment for type .
For correctness, layer costs and is required by exactly planes. A particular requiring plane is earliest among these in a random ordering with probability . Its expected marginal contribution to the layer is therefore that layer's cost divided by . Summing the layers it requires proves the formula. This is the Shapley value of an airport game.
The two passes use arithmetic operations. If every individual payment must be explicitly listed, add the unavoidable output work. For counts given in binary, the compact per-type output is polynomial in the input size; expanding an exponentially large number of identical entries need not be. With integer lengths and rational , all fractions can be computed exactly with polynomial bit complexity: a common denominator divides a product of at most suffix counts, whose bit length is , in addition to the input denominator of . For arbitrary real , the same rational factors give symbolic multiples of it.
For a fixed finite player set and characteristic function with , let be the allocated payoff vector. A standard four-axiom characterization is:
Cooperative-game efficiency: .
Cooperative-game symmetry: if for every , then .
The null player axiom: if for every , then .
Cooperative-game additivity: for games on the same , , where .
These axioms uniquely specify the Shapley value. This is the zero-marginal null-player convention. The original work combines some requirements into an equivalent formulation.[ref]
Use the inclusive quota: a coalition wins at weight at least . For each player, count losing predecessor coalitions that become winning when that player joins. Group these swing counts by predecessor cardinality :
Player and weightSwing counts Shapley valueBanzhaf index
For example, player one is pivotal for predecessor coalitions , , , and . Player three is pivotal only for ; player four has the symmetric counterpart.
Each swing contributes to the probabilistic Banzhaf index. For the Shapley value, a swing with predecessors contributes , which is for the four possible sizes. Applying these weights to the table gives
The Shapley values sum to one. The unnormalized Banzhaf indices sum to ; they must not be replaced by normalized shares in this part.
For cooperative-game symmetry, interchangeable players have for every omitting them. The Banzhaf difference identity therefore gives equal indices. For a null player, every marginal contribution in the defining average is zero, so its index is zero.
For cooperative-game additivity, each marginal contribution is additive:
Averaging both sides over the same coalitions gives .
For failure of cooperative-game efficiency, the indices computed in part (b) sum to , whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index , also exceeding the total value when summed. Pivotality averaged over independently chosen coalitions does not telescope in the way the ordering-average Shapley value does.
For a transferable utility game on player set , its characteristic function of a coalitional game is , where is the maximum transferable surplus attainable by coalition and . An imputation is a payoff vector satisfying efficiency and individual rationality . The core of a cooperative game consists of the efficient payoff vectors satisfying
These conditions prevent any coalition from blocking the allocation; singleton constraints include individual rationality.
The Shapley value payoff is
Equivalently, it is the expected marginal contribution of player when the players arrive in uniformly random order. The factorial weight counts the orders with exactly preceding . Summing marginal contributions telescopes along each order, proving Shapley efficiency.
In the four-player market a coalition creates one unit of surplus exactly when it contains the seller and at least one buyer. Thus
All singleton values are zero and . Core constraints for the pairs require for every buyer . Since all payoffs are nonnegative and sum to one, the other two buyers' payoffs must be zero for each such pair. Therefore every buyer receives zero and the seller receives one. This vector satisfies all coalition inequalities, so
The seller's marginal contribution is one unless he arrives before all three buyers, which happens with probability . A given buyer contributes one exactly when the seller is first and that buyer is second, with probability . Hence
In particular the Shapley allocation need not lie in this market's core.
For the market with sellers and buyers, a coalition containing sellers and buyers can make precisely trades, each producing unit surplus. Thus and . Let and denote the common Shapley payoffs within the two roles. Role symmetry and the telescoping efficiency identity give
It remains to prove , rather than infer it only from competitive intuition.
Generate a uniformly random arrival order by giving every player an independent uniform time in . Conditional on a specified seller's arrival time , the number of preceding buyers and number of preceding other sellers are independent, with
The seller adds a trade precisely when . Consequently
For , the difference has mean and variance . By Chebyshev's inequality,
Split the integral at . Using the trivial bound one on the first piece gives
This proves the Shapley limit in a buyer-heavy exchange market. Since , we conclude
The proof accounts for sellers arriving very early, where a fixed-time concentration argument alone would not be uniform.
Let , , be a coalitional game with . The Shapley value is
Equivalently, choose a uniformly random player ordering and average each player's marginal contribution when that player joins its predecessors. The coefficient counts precisely the orderings with predecessor set .
The standard axioms are efficiency, ; symmetry, giving equal values to players with identical marginal contributions; the dummy-player property, giving if every marginal contribution of equals ; and additivity, . The null-player form of the dummy axiom gives zero to a player contributing nothing. These properties characterize the Shapley value. They also follow directly from its formula: efficiency telescopes along each ordering, symmetry relabels orderings, constant dummy contributions average to themselves, and the sum is linear in .
For balanced contributions of Shapley values, remove player from a uniformly random ordering. The resulting ordering of is uniform, so it computes 's Shapley value in the restricted game. If comes after , removing it does not change 's marginal contribution. If precedes , and consists of 's other predecessors, the difference is
There are full orderings with exactly before . Consequently
Both the summand and coefficient are unchanged when are interchanged. Thus
The restriction keeps all coalition values for the remaining players, exactly matching the payoff comparison after a departure. The identity does not require the differences to be positive.
Now consider the coverage coalitional game formed by the finite book sets. For disjoint coalitions , put . Then
Thus coverage is generally subadditive. It is a superadditive coalitional game precisely when the book sets are pairwise disjoint: disjointness makes the displayed formula additive, while a common book of players gives . For example, gives values and disproves unconditional superadditivity. The printed clause must therefore have its disjointness condition apply to superadditivity as well as to core nonemptiness.
For the core of a coverage game, an allocation must satisfy efficiency and for every coalition. In particular . Summing gives
The reverse inequality always holds, with equality exactly when no book appears in two sets. Therefore overlap makes the core empty. If the sets are disjoint, gives every coalition exactly its value and is a core allocation; the singleton lower bounds and efficiency make it the only one. Hence superadditivity and a nonempty core each occur exactly in the pairwise-disjoint case.
Finally write the game as a sum over individual books. For a book , let . Its contribution to coalition value is one if the coalition meets , and zero otherwise. In a random ordering, player contributes this book precisely when and is earliest among its knowers. Each knower is equally likely to be earliest. Additivity of the Shapley value therefore gives the Shapley value of a coverage game
This formula remains valid when books overlap and the core is empty.
The Shapley value is the expected marginal contribution of a player when the players join in uniformly random order. Equivalently,
For three players, the weights for predecessor sets of sizes are . Using the computed values,
Thus
The characteristic function of a coalitional game assigns each coalition its total attainable transferable payoff , with . In a transferable utility game the members may divide that total among themselves. This game-theoretic characteristic function is not the characteristic function of a probability distribution.
The Shapley value assigns to player the average marginal contribution that player makes over all uniformly random orderings of the players. If is the predecessor set in ordering , then
For any ordering, summing all contributions telescopes to , so the Shapley value is efficient. It treats interchangeable players equally, pays a null player zero, and is additive in the characteristic function. These properties give its standard fairness axioms and uniquely characterize the Shapley value. The random-order interpretation explains why every position and predecessor coalition receives a principled weight rather than privileging a particular bargaining order.
For a convex cooperative game, couple a uniform ordering of with its restriction to . The restricted ordering is uniform on . For , the restricted predecessor set is , so increasing marginal contributions give
Averaging proves Shapley population monotonicity in a convex game:
The comparison is meaningful for players who participate in the restricted game; no restricted value is defined for a player outside . Summing over and applying efficiency in that restricted game gives
Together with efficiency for , these are exactly the core of a cooperative game inequalities. Hence the Shapley value belongs to the core of a convex game. This proves the requested stability, not just individual rationality.
Now label the entrepreneur by and the workers by . A coalition without the entrepreneur has value zero; one containing the entrepreneur and workers has value . Workers are interchangeable, so their Shapley values agree. Fix one worker. Their contribution is zero if the entrepreneur appears after them. If the entrepreneur and exactly of the other workers appear before them, it is . For a fixed choice of those workers, the predecessors can be ordered in ways and the remaining successors in ways. Therefore the probability of this event, summing over the predecessor choices, is
The fair wage is thus
This is Shapley wages in an entrepreneur-worker game. The entrepreneur's payoff, by efficiency, is
It also follows directly because the entrepreneur has each possible number of predecessors with probability , and their contribution is then . When , the differences are all and , so
Finally suppose is convex and nondecreasing on nonnegative integers, so is nonnegative and nondecreasing. We verify that the entire coalitional game is convex. The entrepreneur's contribution to a set of workers is , which increases with that set. A worker's contribution is zero when the entrepreneur is absent and is when the entrepreneur and other workers are present. Enlarging a predecessor set either leaves both contributions zero, introduces the entrepreneur and a nonnegative contribution, or increases and hence . Every player's marginal contributions therefore increase, giving a convex cooperative game. The result already proved yields the complete Shapley allocation lies in the core, including the entrepreneur's payoff.
One can also verify the core inequalities directly. Nonentrepreneur coalitions receive , their value. For a coalition containing the entrepreneur and workers, it suffices that
Since in the wage sum, . Nondecreasing makes this full average no greater than the average of the final differences, which is the displayed right side. Thus ; the grand coalition has equality by efficiency. This confirms the core conclusion without assuming .
For a transferable utility game with , an efficient allocation satisfies . An imputation is efficient and individually rational, . Write and define the excess of a coalition as .
The core of a cooperative game is
It consists of allocations immune to a coalition's blocking: no coalition can obtain more for its members by leaving. The singleton inequalities imply individual rationality. The core may be empty.
The nucleolus, when the imputation set is nonempty, is the unique imputation that lexicographically minimizes the list of coalition excesses arranged from largest to smallest. It first minimizes the largest complaint, then the second largest among ties, and so on. Including the empty and grand coalitions adds constant zeros and does not change the solution. Minimization on efficient allocations without individual rationality instead defines the prenucleolus, a different convention that matters for this paper's game.
The Shapley value is the average marginal contribution of each player over all uniformly ordered player arrivals:
Exactly orderings have as the predecessor set of . This is an average-contribution fairness rule, rather than a blocking-stability condition; it need not be individually rational for an arbitrary game.