Transferable utility game ($v:2^N\to \mathbb{R},v(\varnothing )=0$)

A finite transferable utility game gives each coalition $S\subseteq N$ a real value $v(S)$ that its members can distribute among themselves. The usual normalization is $v(\varnothing )=0$. An efficient payoff vector $x$ satisfies ${\sum }_{i\in N}{x}_i=v(N)$. Simple cooperative games model winning coalitions with values zero and one; convex cooperative games model increasing marginal contributions.

A value has cooperative-game additivity when adding two characteristic functions on the same player set adds their allocation vectors. Here $(v+w)(S)=v(S)+w(S)$ for every coalition. The sum of two simple cooperative games need not be simple; the axiom is naturally stated on transferable utility games.

A null player has zero marginal contribution to every coalition. The axiom for a null player requires allocating that player zero. This is the zero-marginal convention used here.

A value assigning a vector of payoffs $\psi (v)$ to a transferable utility game has cooperative-game efficiency when it distributes exactly the grand-coalition value. This is a budget-total condition; it does not assert membership in the core of a cooperative game.

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 $1/2$. Its sum over players need not equal the grand-coalition value: in a three-player majority game each player has index $1/2$, giving total $3/2$ despite $v(N)=1$. 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]

For distinct players $i,j$, expand each probabilistic Banzhaf index by whether the sampled coalition contains the other player. The terms $v(T)$ and $v(T\cup \{i,j\})$ cancel on subtraction, leaving the displayed identity. In a weighted voting game with $w_i\le w_j$, every summand is nonnegative, proving that the index is monotone in the player's weight. Equal weights give equal indices, although different weights can also have equal indices.

The normalized Banzhaf index rescales the probabilistic Banzhaf indices to sum to the grand-coalition value, whenever the denominator is nonzero. It preserves cooperative-game symmetry and assigns zero to a null player, but generally fails cooperative-game additivity. For example, add the three-player majority game to a dictatorship of player one. Their normalized indices are $(1/3,1/3,1/3)$ and $(1,0,0)$, whereas the sum game has normalized index $(6/5,2/5,2/5)$, not their vector sum. The sum game has grand-coalition value two, which must be retained in the normalization.

Players $i,j$ are symmetric when interchanging them does not affect any coalition value. The displayed condition is equivalent to invariance under their transposition. If every pair is symmetric, arbitrary permutations preserve the game, and coalitions of equal cardinality have equal values. This is a property of the transferable utility game, rather than a requirement that a chosen payoff allocation treat players equally.

A value has cooperative-game symmetry when it assigns equal payoffs to players satisfying symmetry of players in a cooperative game. Thus equality of their marginal contributions is reflected in the allocation, rather than merely being a property of the underlying game.

A transferable utility game represented by a weighted undirected graph, with one player per graph vertex. A coalition receives the sum of weights of the graph edges in its induced subgraph; absent edges have weight zero. Singleton and empty coalitions have value zero. This is a representation of a transferable utility game, distinct from a graphical description of local payoffs in a normal-form game.

A loop-free induced subgraph game is a convex cooperative game exactly when all edge weights are nonnegative. Necessity follows by testing the supermodular inequality on two distinct singleton coalitions. For sufficiency,Only edges connecting the two set differences survive cancellation. Loop contributions cancel as well, so the same off-diagonal condition remains sufficient and necessary when self-loops are added.

An induced subgraph game extended by one self-loop weight ${\ell }_i$ per player. Each loop is counted once, so $v(\{i\})={\ell }_i$ andSingleton 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 $1$ joined by an edge of weight $-1$ represent the simple cooperative game in which any coalition meeting those two players wins.

In a uniformly random player permutation, edge $\{i,j\}$ contributes $w_{ij}$ to $i$'s marginal contribution exactly when $j$ precedes $i$, which occurs with probability $1/2$. Sum these expected contributions over incident graph edges to obtain the displayed Shapley value. This proof works for arbitrary real edge weights; nonnegativity is not required.

A transferable utility game satisfying the displayed equality for every coalition. This forces $v(\varnothing )=0$. It does not by itself guarantee a nonempty core: core rigidity in a constant-sum cooperative game shows that nonemptiness requires the characteristic function of a coalitional game to be additive.

For a core allocation $x$, the inequalities for $S$ and its complement, together with efficiency, give $x(S)\ge v(S)$ and $x(S)=v(N)-x(N\setminus S)\le v(N)-v(N\setminus S)=v(S)$. Thus equality holds for every coalition; singletons force $x_i=v(\{i\})$ and all other values must be their sums. Conversely, if the characteristic function of a coalitional game is additive, that unique allocation satisfies every core inequality with equality. Hence a constant-sum cooperative game has either an empty core or this one-point core.

The usual convention that the empty coalition creates no value. It makes the sum of a marginal contribution vector equal $v(N)$ by a telescoping sum. Without it, that sum is $v(N)-v(\varnothing )$, so the vector need not satisfy efficiency in the core of a cooperative game. The constant function $v(T)=1$ is supermodular but gives a zero marginal vector and fails efficiency for a nonempty player set.

Players hold finite sets of resources, and their coalition value is the number of distinct resources they collectively cover. The value is generally subadditive rather than superadditive: overlapping resources are counted only once. It is a superadditive coalitional game exactly when the players' resource sets are pairwise disjoint.

Decompose a coverage coalitional game into one-resource games and use additivity of the Shapley value. A player contributes a resource precisely when it is the earliest player in a random ordering among those holding that resource. Each holder has probability the reciprocal of the number of holders of being earliest. Summing these contributions proves the formula, regardless of overlaps or emptiness of the core.

A coverage coalitional game has a nonempty core of a cooperative game exactly when all resource sets are pairwise disjoint. Singleton coalition constraints require $x_i\ge |B_i|$, while efficiency requires ${\sum }_i{x}_i=|{\bigcup }_i{B}_i|$. Any overlap makes these inequalities inconsistent. When there is no overlap, the allocation $x_i=|B_i|$ is the unique core allocation and gives every coalition its value exactly.

With nonnegative claims $c_i$ and an estate $0\le a\le {\sum }_i{c}_i$, a coalition's guaranteed worth is the estate left after all outside claims are met, or zero if those claims exhaust it. Writing the total deficit $d={\sum }_i{c}_i-a$ gives $v(S)=({\sum }_{i\in S}{c}_i-d{)}_{+}$. For disjoint coalitions, $(p+q-d{)}_{+}\ge (p-d{)}_{+}+(q-d{)}_{+}$, so this is a superadditive coalitional game. Its core of a cooperative game consists exactly of efficient allocations with $0\le x_i\le c_i$: the upper bounds are equivalent to the complementary-coalition constraints, and the lower bounds together with efficiency imply every other coalition constraint.

The characteristic function of a coalitional game is superadditive when disjoint coalitions can attain at least the sum of their separate values by joining. This follows when their separate strategies can be played together without interference. Superadditivity is an additional property of an abstract transferable utility game, not a consequence of merely assigning values to subsets: $v(\{1\})=v(\{2\})=v(\{1,2\})=1$ is a normalized counterexample.

Players each own one object of one of two complementary types. A matched pair sells for $\omega >0$, and objects of one type alone have no value. The characteristic function of a coalitional game is therefore the displayed matching count times pair price. The core of a glove game pays the scarce type the entire pair value and the abundant type zero; if type counts are equal, a common split between the two types can vary continuously.

If there are fewer left owners than right owners, deleting any right owner leaves the grand-coalition value unchanged. The complement's core constraint and efficiency force that owner's payoff to be zero. Mixed-pair inequalities then require every left owner to receive at least $\omega$, and efficiency makes all these payoffs exactly $\omega$. Reverse the types when right owners are scarce. If both counts equal $k$, sum all $k^2$ mixed-pair inequalities. Their total is exactly $k$ times the grand-coalition payoff, so each pair sum is $\omega$. Hence all left owners receive a common $\theta \in [0,\omega ]$ and all right owners $\omega -\theta$. Such allocations meet every coalition constraint because $\theta u+(\omega -\theta )v\ge \omega \min (u,v)$. This proves the complete core description.

The characteristic function assigns every coalition its total attainable transferable payoff, with $v(\varnothing )=0$. It determines the efficiency condition of an imputation and all constraints of the core of a cooperative game. For the glove game, $v(S)=\omega \min (|S\cap L|,|S\cap R|)$; for miners requiring $r$ people to carry one lump, $v(S)=\lfloor |S|/r\rfloor$. This game-theoretic function is distinct from the characteristic function of a probability distribution.

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 $S$ equals its original contribution at the complementary predecessor set in $N\setminus \{i\}$. This preserves the Shapley value.

When the imputation set is nonempty, the nucleolus is the unique imputation lexicographically minimizing the vector of excesses of a coalition sorted decreasingly. It minimizes the largest complaint first, then subsequent complaints among ties. It can be computed through successive linear programs that minimize the current maximum excess and retain constraints fixed by prior stages. Its uniqueness is the standard nucleolus theorem. If the core of a cooperative game is nonempty, the nucleolus belongs to it; an empty core does not preclude a nucleolus.

The prenucleolus uses the same sorted excesses of a coalition but minimizes over all efficient payoff vectors, without imposing individual rationality. It can differ from the nucleolus when coalition values are not superadditive. Any computation must state which domain is used rather than silently relaxing imputation inequalities.

An imputation is an efficient, individually rational allocation in a transferable utility game. Its total is the grand-coalition value and each player receives at least its singleton value. The set is nonempty exactly when $v(N)\ge {\sum }_{i}v(\{i\})$, and is then compact. This individual-rationality condition distinguishes the nucleolus from the prenucleolus.

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.

A coalition is a subset of the players in a transferable utility game, considered as a group that can act together. The game assigns it value $v(S)$. The core of a cooperative game constrains the total payoff assigned to every coalition, while a marginal contribution measures the value gained by adding one player.

The excess measures a coalition's complaint against an allocation: a positive excess means its own attainable value exceeds its assigned total. The core of a cooperative game requires every excess to be nonpositive at an efficient allocation. The nucleolus lexicographically minimizes the decreasingly sorted excess vector over imputations.

A transferable utility game is convex when its coalition-value function is supermodular. Equivalently a player's marginal contribution cannot decrease when the preceding coalition grows. The implication follows by applying the displayed inequality to $A\cup \{i\}$ and $B$ with $A\subseteq B$, $i\notin B$; the reverse implication follows by adding successive marginal inequalities. This property concerns coalition values, not geometrical convexity of a strategy space.

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 $K\ne \varnothing$. Every winning coalition contains $K$; conversely monotonicity makes every superset of $K$ win. Thus the game is $u_K$. Conversely, every unanimity game is a supermodular set function, as a direct check of the winning and losing cases shows.

Choose a uniform random ordering of $N$ and restrict it to $T$. The restriction is uniform, and each player's predecessor set in $T$ is contained in their predecessor set in $N$. Increasing marginal contributions in a convex cooperative game make the full-population contribution at least the restricted contribution. Averaging proves the displayed Shapley value inequality. Summing over $i\in T$ and using efficiency in the restricted game proves every core inequality.

Increasing marginal contributions imply $m_i^{\pi }\ge v((S\cap P_i)\cup \{i\})-v(S\cap P_i)$ for $i\in S$. Summing telescopes to ${\sum }_{i\in S}{m}_i^{\pi }\ge v(S)$, while efficiency follows by telescoping over the full ordering. Hence every marginal contribution vector is in the core of a cooperative game. The core is a convex set, so their average, the Shapley value, is in it too. This gives an elementary proof of nonemptiness and stability for a convex cooperative game.

The core consists of efficient payoff vectors for which each coalition receives at least its own attainable value. Thus no coalition can improve every member's payoff by leaving. It is a convex set defined by linear constraints, but can be empty. Every convex cooperative game has a nonempty core because each marginal contribution vector belongs to it.

For a monotone simple cooperative game with empty value $0$ and grand-coalition value $1$, 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 $x_i\ge 0$. Every winning coalition must receive at least $1$, 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 $1$ and every losing coalition at least $0$. These are precisely the core inequalities. The core is thus nonempty if and only if a veto player exists.

For $r\ge 2$, the core is zero when $n<r$, the nonnegative unit simplex when $n=r$, the single allocation $x_i=1/r$ when $n\ge 2r$ is divisible by $r$, and empty for all other $n\ge r$. To prove the obstruction, every $r$-person coalition requires payoff at least one. Summing these constraints counts each player $\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ times and gives $r\lfloor n/r\rfloor /n\ge 1$, impossible when $r\nmid n$. For a divisible $n$, all such coalition sums must equal one. Comparing coalitions with the same $r-1$ members makes all individual payoffs equal when $n>r$. The uniform allocation satisfies every coalition constraint because $|S|/r\ge \lfloor |S|/r\rfloor$. At $n=r$ all proper coalition values are zero, giving the whole simplex instead.

The Shapley value averages each player's marginal contribution over uniformly random player orderings. Exactly $|S|!(n-|S|-1)!$ orderings have $S$ immediately before player $i$, giving the formula. The values sum to $v(N)$ 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.

Cooperative-game efficiency, cooperative-game symmetry, the null player axiom and cooperative-game additivity characterize the Shapley value. The ordering-average definition satisfies all four: marginal totals telescope, relabelling players preserves the ordering average, zero marginals average to zero and marginal contributions add pointwise. The original work gives an equivalent axiomatization combining some of these requirements.^[ref]

For uniqueness, write $u_T$ for the unanimity game of a nonempty coalition $T$. Recursively define $a_T=v(T)-{\sum }_{\varnothing \ne R⊊T}{a}_R$ in increasing order of $|T|$. Then $v(S)={\sum }_{\varnothing \ne T\subseteq S}{a}_T$, so $v={\sum }_{\varnothing \ne T\subseteq N}{a}_T{u}_T$. Apply the axioms to every scaled unanimity game $a_T{u}_T$. Players outside $T$ receive zero; cooperative-game symmetry and cooperative-game efficiency give each player inside $T$ the amount $a_T/|T|$. Every game is a finite sum of such scaled unanimity games, and cooperative-game additivity therefore determines every allocation uniquely. Applying the axioms directly to the scaled games avoids assuming real homogeneity from additivity alone.

For three distinct players $i,j,k$ in a normalized simple cooperative game, enumerate the predecessor coalitions in the Shapley value formula:Subtracting the formula with $i$ and $j$ exchanged proves the displayed identity. Every coalition value is zero or one, so $2({\varphi }_i-{\varphi }_j)$ is an integer. This rules out, for example, coordinates differing by $1/6$, 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.

In an $n$-player simple cooperative game, every marginal contribution along a player permutation is zero or one. The Shapley value is its average over the $n!$ equally likely permutations. Thus $n!{\varphi }_i(v)$ counts the orders in which player $i$ changes a losing coalition into a winning one and is an integer. In lowest terms, the coordinate's denominator divides $n!$. This is a necessary constraint on a proposed Shapley value vector, not a sufficient one.

For $k$ unit sellers and $3k$ unit buyers with unit surplus per trade, a coalition's value is the smaller of its seller and buyer counts. Give each player an independent uniform arrival time. Conditional on a specified seller arriving at time $t$, the previous buyers and other sellers have independent binomial counts $B\sim \mathrm{Bin}(3k,t)$ and $S\sim \mathrm{Bin}(k-1,t)$. The seller contributes one exactly when $B>S$. For fixed positive $t$ this probability tends to one; a Chebyshev bound and a split near $t=0$ also give an explicit uniform integral estimate. Averaging gives seller Shapley value tending to one. Efficiency and role symmetry give $s_k+3b_k=1$, hence the buyer value tends to zero.

For a coalitional game, restriction to the remaining players preserves coalition values. Remove player $j$ from a uniformly random ordering when comparing player $i$'s Shapley value. The marginal contribution changes only when $j$ precedes $i$. If $S$ is the set of other predecessors, the change is $v(S\cup \{i,j\})-v(S\cup \{i\})-v(S\cup \{j\})+v(S)$, with coefficient $(|S|+1)!(n-|S|-2)!/n!$. The same expression and coefficient arise after interchanging $i,j$, proving balanced contributions.

An entrepreneur is indispensable and a coalition containing the entrepreneur and $k$ of $n$ workers earns $p(k)$; a coalition without the entrepreneur earns zero. A worker's marginal contribution is nonzero only when the entrepreneur precedes them. The probability that the entrepreneur and exactly $k$ other workers precede that worker is $(k+1)/(n(n+1))$, giving the displayed common Shapley value wage. The entrepreneur receives $p(n)-nw$. Convex nondecreasing $p$ makes all marginal contributions increase with predecessor sets, so the whole Shapley value allocation belongs to the core.

Complementing predecessor sets within $N\setminus \{i\}$ preserves their Shapley value weights, since the factorials $|S|!$ and $(n-|S|-1)!$ interchange. For the dual coalitional game, the corresponding marginal contribution equals the original contribution at that complementary set. Hence the values coincide. The same bijection gives ${\varphi }_i(v)={\sum }_{S}w(S)(v(N\setminus S)-v(S))$.

For a player ordering $\pi$, $P_i$ is the set before player $i$, and the displayed entries form its marginal contribution vector. Their sum is $v(N)-v(\varnothing )$. 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.

A weighted voting game assigns player weights and a threshold, and declares coalitions winning when their total weight passes that threshold. The strict $>t$ convention is equivalent to quota $t+1$ for integer weights; another common convention writes a weak inequality directly. Nontrivial examples are simple cooperative games. Having nonnegative weights does not guarantee a convex cooperative game: two-of-three majority supplies a counterexample.

Suppose winning coalitions $W_1,\dots ,W_k$ and losing coalitions $L_1,\dots ,L_k$ contain each player the same total number of times:No real-weight, weak-quota weighted voting game represents those outcomes. Summing weights over the winning family gives at least $kq$, while summing over the losing family gives strictly less than $kq$. Equal player multiplicities make the two sums identical, a contradiction. This certificate works without assuming nonnegative weights.

For example, the winners $\{1,2,3\},\{1,4,5\}$ and losers $\{1,2,4\},\{1,3,5\}$ form a two-against-two obstruction. A monotone game whose minimal winning coalitions are the first two sets realizes this certificate, even though every winner contains player $1$.

A zero-one coalitional game has this property if exchanging one player each way between two disjoint winning coalitions leaves at least one winning. Any weighted voting game satisfies it: the exchange preserves their aggregate weight, which is at least twice the quota, whereas two losing coalitions would have aggregate weight strictly below twice the quota.

The disjointness restriction is substantive. If every winning coalition contains a common player, the condition is vacuous. It is consequently weaker than restrictions allowing exchanges between overlapping winning coalitions, and does not characterize weighted voting games.

A simple cooperative game is a monotone transferable utility game in which each coalition either loses, with value zero, or wins, with value one. In the usual nontrivial convention the empty coalition loses and the grand coalition wins. The Shapley value is then the probability that a player changes a losing coalition into a winning one when players enter in uniformly random order.

For a fixed nonempty coalition $K$, the simple cooperative game in which a coalition wins exactly when it contains $K$. Members of $K$ are exactly the veto players. It is a convex cooperative game: intersections of winning coalitions still contain $K$, and checking the remaining zero-one cases establishes the supermodular inequality. Full symmetry of players in a cooperative game forces $K=N$.

A player belonging to every winning coalition. Giving all of the grand-coalition value to a veto player satisfies every core constraint in a nontrivial simple cooperative game. If there are no veto players, its core of a simple cooperative game is empty.

A coalition of value $1$ in a simple cooperative game. Monotonicity makes every superset of a winning coalition winning. An inclusion-minimal winning coalition has no winning proper subset.