Additivity of a cooperative-game value Created 2026-10-25 Updated 2026-10-31
A value has cooperative-game additivity when adding two characteristic functions on the same player set adds their allocation vectors. Here for every coalition. The sum of two simple cooperative games need not be simple; the axiom is naturally stated on transferable utility games.
Every nontrivial simple cooperative game that is a convex cooperative game is a unanimity game. If two coalitions win, the supermodular inequality forces their intersection to win as well. Intersecting the finite nonempty family of winning coalitions gives a winning set . Every winning coalition contains ; conversely monotonicity makes every superset of win. Thus the game is . Conversely, every unanimity game is a supermodular set function, as a direct check of the winning and losing cases shows.
For a monotone simple cooperative game with empty value and grand-coalition value , the core of a cooperative game consists exactly of the nonnegative unit-total payoff vectors supported on veto players.
For the proof, singleton core conditions give . Every winning coalition must receive at least , the full available total, so all players outside it receive zero. A positively paid player therefore belongs to every winning coalition and is a veto player. Conversely, a unit-total nonnegative allocation supported on veto players gives every winning coalition exactly and every losing coalition at least . These are precisely the core inequalities. The core is thus nonempty if and only if a veto player exists.
An induced subgraph game extended by one self-loop weight per player. Each loop is counted once, so and
Singleton and pair coalition values determine all weights; larger coalition values must then agree with their sums. Signed weights are allowed. For example, two loops of weight joined by an edge of weight represent the simple cooperative game in which any coalition meeting those two players wins.
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.
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.
A simple cooperative game is a transferable utility game with
A coalition of value is a winning coalition; a value- coalition loses. The displayed definition uses the usual monotone, nontrivial convention: the empty coalition loses and the grand coalition wins.
Yes; without self-loops, such a nontrivial simple cooperative game has exactly one positive edge, of weight . For each pair,
because singleton and loop contributions are zero. Summing all edge weights gives , so precisely one unordered pair has weight , and all other pairs have weight zero.
Thus the winning coalitions are exactly those containing both and . For any , set
This payoff vector is efficient, since . Every winning coalition receives and every losing coalition receives a nonnegative total, so all inequalities hold. Hence it belongs to the core of a cooperative game.
In fact these are all core allocations. Singleton conditions require , and the winning pair requires ; efficiency then forces equality and zero payoffs outside the pair. The endpoints are both veto players, consistent with the general characterization of the core of a simple cooperative game.
No. Two positive self-loops and one negative edge give a simple cooperative game with an empty core of a cooperative game. Give players loop weights , put , and give every other loop and edge weight zero. For a coalition ,
Thus a coalition wins exactly when it contains player or player . This is monotone, has values in , and satisfies . Extra players for any do not alter any coalition value.
The core singleton inequalities would require , and for every other player, while efficiency requires . These requirements are inconsistent. Equivalently, the two disjoint winning singleton coalitions leave no veto player. Signed weights are essential to this particular representation and are permitted in the induced subgraph game model.
There is exactly one such nontrivial game for every : the unanimity game requiring every player. Put
It is a simple cooperative game, and permuting players preserves every coalition value. Thus it has the required symmetry of players in a cooperative game. It is also a convex cooperative game: if both are winning, all four terms in the supermodular inequality have value ; if exactly one is winning, their union is and their intersection loses, giving equality ; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For the same definition gives the sole player value .
To prove uniqueness, first establish that convex simple games are unanimity games. If are winning coalitions, the supermodular inequality gives
so their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains , and monotonicity makes every superset of winning. Hence .
If were a proper nonempty subset of , take and , and let . Then contains and wins, whereas loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus , proving the claimed count. The “nontrivial” convention excludes the identically zero game; if that degenerate game were also called simple, it would supply one additional symmetric convex example.
For a simple cooperative game, the Shapley value is the probability that a player is pivotal in a uniformly random ordering. Symmetry gives one value for permanent members and another for nonpermanent members.
A particular nonpermanent member is pivotal exactly when all five permanent members and exactly three of the other nine nonpermanent members precede them. The predecessor set then has size eight. There are such sets, each giving orderings. Their Shapley value is therefore
Every ordering has exactly one pivotal member, since the empty coalition loses and the full coalition wins. This proves efficiency directly: , where is the value of each permanent member. Hence
The vector has five entries and ten entries . As a check, a permanent member is pivotal when they are last among the permanent members and occupy a position from nine to fifteen; counting those orderings gives the same .
Yes. Give players weights , respectively, and let the quota be three. This weighted voting game is a simple cooperative game whose minimal winning coalitions are and . In orders , player 3 supplies the winning marginal contribution. In order player 1 does, and in order player 2 does. Averaging the six marginal contribution vectors gives exactly as the vector of Shapley values.
No. In a simple cooperative game, a player's marginal contribution along any permutation is zero or one. With three players there are six equally likely permutations, so every Shapley value is an integer multiple of , by the Shapley value denominator in a simple game. But and are not integers. The vector sums to one, but fails this necessary denominator condition.
Yes. Use the simple cooperative game in which a coalition wins exactly when it contains at least two players. In every permutation, precisely the second arrival changes a losing coalition into a winning one. Each player is second in two of the six permutations, so each Shapley value is . This constructs the required vector while verifying that singleton coalitions lose and the grand coalition wins.
No. The denominator test from part ii is satisfied here, so a stronger obstruction is needed. Put and . In a three-player simple cooperative game, the Shapley value formula gives, for distinct ,
Subtract the corresponding expression for :
Each coalition value is zero or one, so this difference must be an integer multiple of . This is the obstruction from pairwise Shapley differences in a three-player simple game. The proposed first two coordinates differ by , which is not an integer multiple of . Therefore the vector cannot occur, even though each coordinate separately passes the denominator test.
Let . If the two disjoint winning coalitions exchange players, the aggregate weight is conserved:
If both resulting coalitions lost, each weight would be strictly below , making their sum strictly below . This is impossible. Thus every weighted voting game has swap robustness for disjoint winning coalitions, even when the weights or quota are negative.
The converse is false. The four-player prime-cardinality game from part (a) has swap robustness for disjoint winning coalitions: swapping one player each way preserves each coalition's cardinality, so in fact both winning coalitions remain winning. Part (a) proves it is not a weighted voting game.
Even imposing monotonicity would not repair the converse under the printed disjointness restriction. As a stronger counterexample, use five players and declare a coalition winning exactly when it contains player and contains either both or both . This is a simple cooperative game, and all its winning coalitions contain player , so no two are disjoint; the stated swap condition holds vacuously.
Nevertheless and win, while and lose. Both pairs contain every player the same total number of times. A weighted representation would therefore give
a contradiction. This is a trade obstruction to weighted voting and pinpoints how weak the disjoint-only swap requirement is.
The probabilistic Banzhaf index averages a player's marginal contribution over all coalitions not containing that player, each given equal weight. In a simple cooperative game, it is the probability of changing a losing coalition into a winning one when every other player joins independently with probability . Its sum over players need not equal the grand-coalition value: in a three-player majority game each player has index , giving total despite . This convention differs from both the raw count of pivotal coalitions and the normalized Banzhaf index.
The name refers to John Banzhaf, whose 1965 paper addresses the mathematical analysis of weighted voting.[ref]
Shapley value 2026-10-06
The Shapley value averages each player's marginal contribution over uniformly random player orderings. Exactly orderings have immediately before player , giving the formula. The values sum to by telescoping each ordering. In a simple cooperative game this is the probability of being pivotal. For a convex cooperative game, Shapley value belongs to the core of a convex game guarantees a stable allocation as well.
In an -player simple cooperative game, every marginal contribution along a player permutation is zero or one. The Shapley value is its average over the equally likely permutations. Thus counts the orders in which player changes a losing coalition into a winning one and is an integer. In lowest terms, the coordinate's denominator divides . This is a necessary constraint on a proposed Shapley value vector, not a sufficient one.
On three players, let exactly when contains player 1 and at least one of players 2 and 3, and zero otherwise. This simple cooperative game is superadditive: disjoint coalitions cannot both contain player 1, so at most one can have value one. Its core of a cooperative game is exactly , since singleton nonnegativity and the two winning-pair constraints force the other two coordinates to zero. In a random player ordering, player 1 is pivotal unless it comes first, whereas each other player is pivotal in just one of the six orders. Thus its Shapley value is , outside the core: coalition receives only . Convex cooperative games have the stronger property that their Shapley value belongs to the core of a convex game.