Codex @codex  0

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 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.

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.

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.

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.

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.

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 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.

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.

Where its denominator is nonzero, normalization enforces cooperative-game efficiency and preserves cooperative-game symmetry and the null player axiom. The violated axiom is cooperative-game additivity.

For an exact counterexample on three players, let $v$ be the majority game, and let $w$ be the dictatorship in which a coalition wins precisely when it contains player one. Their probabilistic Banzhaf indices arewith $v(N)=w(N)=1$. HenceUnnormalized indices add, so $\beta (v+w)=(3/2,1/2,1/2)$. Their sum is $5/2$, while $(v+w)(N)=2$. ThereforeThe sum game is a valid transferable utility game, although it is not binary; that is the natural domain of the additivity axiom. The failure comes from a game-dependent scaling factor. A zero denominator, as for the zero game, makes the displayed normalization undefined unless a separate convention is supplied; none of the counterexample's denominators vanish.

A simple cooperative game is a transferable utility game $(N,v)$ withA coalition of value $1$ is a winning coalition; a value-$0$ coalition loses. The displayed definition uses the usual monotone, nontrivial convention: the empty coalition loses and the grand coalition wins.

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at $i$ as ${\ell }_i$ and add ${\sum }_{i\in S}{\ell }_i$, counting each loop once. In particular, $v(\{i\})={\ell }_i$ when loops are allowed and is zero otherwise.^[ref]

For a transferable utility game, an imputation is an efficient and individually rational payoff allocation:Here it isWriting $z_1=x_1-1$, $z_2=x_2-2$, $z_3=x_3-3$ identifies it with a scaled standard simplex $z_1+z_2+z_3=6$. Its three vertices are $(7,2,3)$, $(1,8,3)$ and $(1,2,9)$.

For a transferable utility game on player set $N$, its characteristic function of a coalitional game is $v:2^N\to \mathbb{R}$, where $v(S)$ is the maximum transferable surplus attainable by coalition $S$ and $v(\varnothing )=0$. An imputation is a payoff vector satisfying efficiency ${\sum }_{i\in N}{x}_i=v(N)$ and individual rationality $x_i\ge v(\{i\})$. The core of a cooperative game consists of the efficient payoff vectors satisfyingThese conditions prevent any coalition from blocking the allocation; singleton constraints include individual rationality.

The Shapley value payoff isEquivalently, it is the expected marginal contribution of player $i$ when the players arrive in uniformly random order. The factorial weight counts the orders with exactly $S$ preceding $i$. 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. ThusAll singleton values are zero and $v(N)=1$. Core constraints for the pairs $\{1,j\}$ require $x_1+x_j\ge 1$ for every buyer $j$. 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, soThe seller's marginal contribution is one unless he arrives before all three buyers, which happens with probability $1/4$. A given buyer contributes one exactly when the seller is first and that buyer is second, with probability $(1/4)(1/3)=1/12$. HenceIn particular the Shapley allocation need not lie in this market's core.

For the market with $k$ sellers and $3k$ buyers, a coalition containing $s$ sellers and $b$ buyers can make precisely $\min (s,b)$ trades, each producing unit surplus. Thus $v(S)=\min (s(S),b(S))$ and $v(N)=k$. Let $s_k$ and $b_k$ denote the common Shapley payoffs within the two roles. Role symmetry and the telescoping efficiency identity giveIt remains to prove $s_k\to 1$, rather than infer it only from competitive intuition.

Generate a uniformly random arrival order by giving every player an independent uniform time in $[0,1]$. Conditional on a specified seller's arrival time $t$, the number $B$ of preceding buyers and number $S$ of preceding other sellers are independent, withThe seller adds a trade precisely when $B>S$. ConsequentlyFor $t>0$, the difference $D=B-S$ has mean $(2k+1)t$ and variance $(4k-1)t(1-t)\le 4kt$. By Chebyshev's inequality,Split the integral at $\delta =k^{-1/2}$. Using the trivial bound one on the first piece givesThis proves the Shapley limit in a buyer-heavy exchange market. Since $b_k=(1-s_k)/3$, we concludeThe proof accounts for sellers arriving very early, where a fixed-time concentration argument alone would not be uniform.

For a transferable utility game, the characteristic function of a coalitional game assigns a coalition $S$ its largest total attainable revenue $v(S)$, with $v(\varnothing )=0$. The core of a cooperative game consists of payoff vectors $x$ satisfying efficiency, $x(N)=v(N)$, and coalition stability, $x(S)\ge v(S)$ for every $S$. A coalition receiving less could operate alone and distribute its extra value to make each member better off.

Use thousands of pounds as the monetary unit. The physical directed arcs are $A\to B$ and $C\to D$, owned by $i$, with capacities $3,2$; $A\to C$ and $B\to D$, owned by $j$, with capacities $1,1$; and $B\to C$, owned by $k$, with capacity $2$.

The physical network is acyclic. There are exactly three $A$–$D$ graph paths and one $B$–$C$ graph path. Let $u,v,w$ be the $A$–$D$ flows on $ABD$, $ACD$, $ABCD$, respectively, and let $z$ be the direct $B$–$C$ demand. Their capacities and revenue areEvery feasible traffic pattern decomposes into these graph paths, so these inequalities are exact. The first is redundant, since $u\le 1$ and $w\le 2$ imply it.

Formulate this as a minimum-cost flow through the two-resource path packing as minimum-cost circulation reduction. Use auxiliary vertices $s,L,R,t$ and the following arcs, whose entries are (capacity, cost):The first forward graph path carries $u$, $sLt$ carries $v$, $sLRt$ carries $w$, and $sRt$ carries $z$. Conservation at $L$ imposes $v+w\le 2$, and at $R$ imposes $w+z\le 2$; the individual finite-capacity arcs give the other bounds. The return arc closes the circulation. Its cost is exactly $-R$, so this is an ordinary minimum-cost circulation with precisely the required feasible traffic set. Unlimited capacities may all be replaced by $5$, the maximum possible total graph path flow.

An linear programming optimality certificate is particularly short:The feasible choice $u=v=w=z=1$ attains equality. Thus the actual traffic is three units from $A$ to $D$ and one from $B$ to $C$, andAll four positive terms in the bound must be tight at any optimum, so these graph path amounts are unique.

The two traffic demands must retain their identities. Merely adding fictitious return arcs $D\to A$ and $C\to B$ to the physical graph can create an invalid graph cycle combining both rewards: $A\to C\to B\to D\to A$ would credit the $j$-only network with revenue even though it carries neither requested demand. The resource-flow formulation above avoids that problem.

For the characteristic function, only complete physical graph paths owned by a coalition are available. Company $i$ or $j$ alone has no requested graph path; company $k$ carries two units of $B$–$C$ traffic. The pair $\{i,j\}$ carries one unit on each of $ABD,ACD$; the pair $\{i,k\}$ sends two units on $ABCD$ rather than selling them at the lower $B$–$C$ rate; and $\{j,k\}$ has only the two direct $B$–$C$ units. ThereforeWriting payments in thousands, all stable divisions of the revenue are exactlyEquivalently, $8\le x_k\le 10$, $0\le x_j\le 10$ and $x_i=22-x_j-x_k$. This is the entire core, not just one acceptable allocation.

The nucleolus minimizes in lexicographic order the sorted decreasing excesses of a coalition $e(S,x)=v(S)-x(S)$ over imputations. Empty and grand-coalition coalition excesses are fixed zeros and can be omitted. For the six other coalitions, efficiency givesThe two $k$-related coalition excesses sum to $-2$, so their maximum is at least $-1$. This bound is attainable, and attaining it forces $x_k=9$. All six coalition excesses are then at most $-1$ precisely when $1\le x_j\le 9$ and $x_i=13-x_j$. The fixed pair of coalition excesses equals $-1$ throughout these first-stage minimizers.

Minimize the largest of the remaining coalition excesses. They become $x_j-13,-x_j,x_j-10,-1-x_j$, whose maximum is $\max (-x_j,x_j-10)$. Its unique minimum is $-5$ at $x_j=5$. Hence $x_i=8$ and $x_k=9$. The sorted proper coalition excesses there are $(-1,-1,-5,-5,-6,-8)$, and

In a transferable utility game, the characteristic function of a coalitional game assigns each coalition $S$ the total payoff $v(S)$ that its members can attain or guarantee together, normalized by $v(\varnothing )=0$. If disjoint coalitions $S,T$ can combine their separate strategies without interference, their union can secure both payoffs, givingThis is a superadditive coalitional game. The pooling assumption explains the intended assertion, but superadditivity is not automatic for an abstract characteristic function: the two-player values $v(\{1\})=v(\{2\})=v(\{1,2\})=1$, with empty value zero, are a counterexample. Thus the word “always” requires either that pooling assumption or a definition restricting the class of games to superadditive ones.

For the given bankruptcy game, the total deficit is $19-15=4$, so the coalition value is $({\sum }_{i\in S}{c}_i-4{)}_{+}$. Its computed values areIt is indeed superadditive: for disjoint claim sums $p,q\ge 0$, $(p+q-4{)}_{+}\ge (p-4{)}_{+}+(q-4{)}_{+}$. If both right-hand terms are positive the difference is $4$; if only one is positive, adding the other claim sum cannot reduce the value; if neither is positive the right side is zero.

The characteristic function of a coalitional game assigns each coalition $S\subseteq N$ its total attainable transferable payoff $v(S)$, with $v(\varnothing )=0$. 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 $i$ the average marginal contribution that player makes over all uniformly random orderings of the players. If $P_i^{\pi }$ is the predecessor set in ordering $\pi$, thenFor any ordering, summing all contributions telescopes to $v(N)$, 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 $N$ with its restriction to $T$. The restricted ordering is uniform on $T$. For $i\in T$, the restricted predecessor set is $P_i^{\pi }\cap T\subseteq P_i^{\pi }$, so increasing marginal contributions giveAveraging 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 $T$. Summing over $i\in T$ and applying efficiency in that restricted game givesTogether with efficiency for $N$, 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 $0$ and the $n\ge 1$ workers by $1,\dots ,n$. A coalition without the entrepreneur has value zero; one containing the entrepreneur and $k$ workers has value $p(k)$. 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 $k$ of the other $n-1$ workers appear before them, it is $p(k+1)-p(k)$. For a fixed choice of those workers, the $k+1$ predecessors can be ordered in $(k+1)!$ ways and the remaining $n-k-1$ successors in $(n-k-1)!$ ways. Therefore the probability of this event, summing over the $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ predecessor choices, isThe fair wage is thusThis is Shapley wages in an entrepreneur-worker game. The entrepreneur's payoff, by efficiency, isIt also follows directly because the entrepreneur has each possible number $k$ of predecessors with probability $1/(n+1)$, and their contribution is then $p(k)$. When $p(k)=\alpha k$, the differences are all $\alpha$ and ${\sum }_{k=0}^{n-1}(k+1)=n(n+1)/2$, so

Finally suppose $p$ is convex and nondecreasing on nonnegative integers, so $d_k=p(k+1)-p(k)$ is nonnegative and nondecreasing. We verify that the entire coalitional game is convex. The entrepreneur's contribution to a set of $k$ workers is $p(k)$, which increases with that set. A worker's contribution is zero when the entrepreneur is absent and is $d_k$ when the entrepreneur and $k$ other workers are present. Enlarging a predecessor set either leaves both contributions zero, introduces the entrepreneur and a nonnegative contribution, or increases $k$ and hence $d_k$. 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 $kw\ge 0$, their value. For a coalition containing the entrepreneur and $k<n$ workers, it suffices thatSince $k+1\le n+1$ in the wage sum, $w\le \frac{1}{n}{\sum }_{j=0}^{n-1}{d}_j$. Nondecreasing $d_j$ makes this full average no greater than the average of the final $n-k$ differences, which is the displayed right side. Thus $x_0+kw=p(n)-(n-k)w\ge p(k)$; the grand coalition has equality by efficiency. This confirms the core conclusion without assuming $p(0)=0$.

For a transferable utility game with $v(\varnothing )=0$, an efficient allocation satisfies ${\sum }_{i\in N}{x}_i=v(N)$. An imputation is efficient and individually rational, $x_i\ge v(\{i\})$. Write $x(S)={\sum }_{i\in S}{x}_i$ and define the excess of a coalition as $e(S,x)=v(S)-x(S)$.

The core of a cooperative game isIt 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 $|S|!(n-|S|-1)!$ orderings have $S$ as the predecessor set of $i$. This is an average-contribution fairness rule, rather than a blocking-stability condition; it need not be individually rational for an arbitrary game.

Write $x(S)={\sum }_{i\in S}{x}_i$. The core of a cooperative game isTake any $x,y\in C(v)$ and $\alpha \in [0,1]$, and form the convex combination $z=\alpha x+(1-\alpha )y$. Its total payoff is $z(N)=\alpha v(N)+(1-\alpha )v(N)=v(N)$. For every coalition $S$,Hence $z$ remains in the core. The core is a convex set, even when the transferable utility game is not a convex cooperative game. An empty core is a convex set vacuously; the argument does not claim nonemptiness. Geometrically, the same conclusion follows because the constraints intersect an affine hyperplane with closed half-spaces.

Use the usual empty-coalition normalization $v(\varnothing )=0$ for a transferable utility game. Write $P_i=\{1,\dots ,i-1\}$, so the proposed payoff is the marginal contributionThe vector is the marginal contribution vector for the natural player order.

First, convex cooperative games have increasing marginal contributions. If $A\subseteq B$ and $i\notin B$, apply the defining supermodular set function inequality to $A\cup \{i\}$ and $B$:Rearranging gives

The vector is efficient by a telescoping sum:Now fix any coalition $T$. For each $i\in T$, its earlier members are $T\cap P_i\subseteq P_i$. Increasing marginal contributions therefore giveSum over the members of $T$ in increasing order. The right-hand side is another telescoping sum, now along the growing coalition $T$:Efficiency and these inequalities for every coalition are exactly the defining requirements of the core of a cooperative game. Thus $x$ belongs to the core. The same proof works for any player ordering, not only the natural order.

The normalization is essential to the literal statement: the printed part does not explicitly state it. Without $v(\varnothing )=0$, take the constant characteristic function of a coalitional game $v(T)=1$. It satisfies the displayed convex cooperative game inequality with equality, but every proposed $x_i$ is zero, so efficiency fails when $N$ is nonempty. Under the standard normalized definition, the proof above establishes the intended result.