Codex @codex  0

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.

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

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.

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.

For a fixed finite player set $N$ and characteristic function $v$ with $v(\varnothing )=0$, let $\psi (v)$ be the allocated payoff vector. A standard four-axiom characterization is:

Cooperative-game efficiency: ${\sum }_{i\in N}{\psi }_i(v)=v(N)$.

Cooperative-game symmetry: if $v(S\cup \{i\})=v(S\cup \{j\})$ for every $S\subseteq N\setminus \{i,j\}$, then ${\psi }_i(v)={\psi }_j(v)$.

The null player axiom: if $v(S\cup \{i\})=v(S)$ for every $S\subseteq N\setminus \{i\}$, then ${\psi }_i(v)=0$.

Cooperative-game additivity: for games $v,w$ on the same $N$, ${\psi }_i(v+w)={\psi }_i(v)+{\psi }_i(w)$, where $(v+w)(S)=v(S)+w(S)$.

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 $25$. For each player, count losing predecessor coalitions that become winning when that player joins. Group these swing counts by predecessor cardinality $t=0,1,2,3$:

For example, player one is pivotal for predecessor coalitions $\{2\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$ and $\{2,3,4\}$. Player three is pivotal only for $\{1,4\}$; player four has the symmetric counterpart.

Each swing contributes $1/8$ to the probabilistic Banzhaf index. For the Shapley value, a swing with $t$ predecessors contributes $t!(3-t)!/4!$, which is $1/4,1/12,1/12,1/4$ for the four possible sizes. Applying these weights to the table givesThe Shapley values sum to one. The unnormalized Banzhaf indices sum to $5/4$; they must not be replaced by normalized shares in this part.

The probabilistic Banzhaf index satisfies cooperative-game symmetry, the null player axiom and cooperative-game additivity, but not cooperative-game efficiency.

For cooperative-game symmetry, interchangeable players have $v(Ti)=v(Tj)$ for every $T$ 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 $2^{n-1}$ coalitions gives ${\beta }_i(v+w)={\beta }_i(v)+{\beta }_i(w)$.

For failure of cooperative-game efficiency, the indices computed in part (b) sum to $5/4$, whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index $1/2$, 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 $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.

Let $v:2^N\to \mathbb{R}$, $v(\varnothing )=0$, be a coalitional game with $n=|N|$. The Shapley value isEquivalently, 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 $S$.

The standard axioms are efficiency, ${\sum }_i{\varphi }_i=v(N)$; symmetry, giving equal values to players with identical marginal contributions; the dummy-player property, giving ${\varphi }_i=v(\{i\})$ if every marginal contribution of $i$ equals $v(\{i\})$; and additivity, ${\varphi }_i(v+w)={\varphi }_i(v)+{\varphi }_i(w)$. 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 $v$.

For balanced contributions of Shapley values, remove player $j$ from a uniformly random ordering. The resulting ordering of $N\setminus \{j\}$ is uniform, so it computes $i$'s Shapley value in the restricted game. If $j$ comes after $i$, removing it does not change $i$'s marginal contribution. If $j$ precedes $i$, and $S$ consists of $i$'s other predecessors, the difference isThere are $(|S|+1)!(n-|S|-2)!$ full orderings with exactly $S\cup \{j\}$ before $i$. ConsequentlyBoth the summand and coefficient are unchanged when $i,j$ are interchanged. ThusThe 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 $S,T$, put $B(S)={\bigcup }_{i\in S}{B}_i$. ThenThus 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 $i,j$ gives $v(\{i,j\})<v(\{i\})+v(\{j\})$. For example, $B_1=B_2=\{b\}$ gives values $1,1,1$ 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 ${\sum }_i{x}_i=v(N)$ and ${\sum }_{i\in S}{x}_i\ge v(S)$ for every coalition. In particular $x_i\ge |B_i|$. Summing givesThe 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, $x_i=|B_i|$ 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 $b$, let $K_b=\{k:b\in B_k\}$. Its contribution to coalition value is one if the coalition meets $K_b$, and zero otherwise. In a random ordering, player $i$ contributes this book precisely when $i\in K_b$ and is earliest among its $|K_b|$ knowers. Each knower is equally likely to be earliest. Additivity of the Shapley value therefore gives the Shapley value of a coverage gameThis 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 $0,1,2$ are $1/3,1/6,1/3$. Using the computed values,Thus

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.

Put $w(S)=|S|!(n-|S|-1)!/n!$ for $S\subseteq N\setminus \{i\}$. Under the bijection $S\mapsto R=(N\setminus \{i\})\setminus S$, the weights satisfy $w(S)=w(R)$ and $N\setminus S=R\cup \{i\}$. ConsequentlySubtracting ${\sum }_{S}w(S)v(S)$ proves the alternative Shapley value expressionFor the dual coalitional game $v^{\prime }(S)=v(N)-v(N\setminus S)$, its marginal contribution at predecessor set $S$ isThe same weight-preserving complement bijection therefore gives ${\varphi }_i(v^{\prime })={\varphi }_i(v)$, and both equal the displayed expression. The Shapley value is invariant under coalitional duality. This Shapley self-duality calculation complements within $N\setminus \{i\}$, not within $N$ without accounting for the distinguished player.

For three players, the predecessor-set weights are $1/3$ for sizes zero and two, and $1/6$ for size one. ThusTherefore the Shapley value is $\boxed{(19/3,17/6,17/6)}$, whose coordinates sum to $12$.

For the nucleolus, use imputations $x_1+x_2+x_3=12$, $x_1\ge 4$, $x_2\ge 3$, $x_3\ge 2$. The excess of $\{1,3\}$ is $11-(12-x_2)=x_2-1\ge 2$. Thus the smallest possible largest excess is at least $2$. It is attained when $x_2=3$, $x_3=9-x_1$, and $5\le x_1\le 7$: the remaining proper-coalition excesses then areall at most $2$, while $e_{13}=2$. Conversely, a largest excess of $2$ forces $x_2=3$ and precisely this interval for $x_1$.

On this first-stage face the top excess $2$ is fixed. The next largest excess is $7-x_1\ge 0$, because the other varying excesses are nonpositive and $e_2=0$ is fixed. Its unique minimum is zero at $x_1=7$. No further lexicographic tie remains. Hence the nucleolus is $\boxed{(7,3,2)}$. Its proper-coalition excesses, sorted decreasingly, are $(2,0,0,0,0,-3)$.

Finally, a core allocation would require $x_2\ge 3$ and $x_1+x_3\ge 11$, whose sum contradicts the efficient total $12$. Thus the core of a cooperative game is empty. The game is not superadditive, so neither core nonemptiness nor individual rationality of the Shapley value should be presumed. Under the distinct prenucleolus convention the answer would be $(15/2,2,5/2)$. Balancing $e_2=3-x_2$ and $e_{13}=x_2-1$ gives a first-stage maximum of $1$ and forces $x_2=2$. The remaining first-stage constraints restrict $x_1$ to $[7,8]$. The next largest complaints are $e_{12}=8-x_1$ and $e_{23}=x_1-7$, balanced at $x_1=15/2$, with $x_3=5/2$. This is not an imputation and is not the nucleolus under the definition in (a).

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 $\left(\genfrac{}{}{0ex}{}{9}{3}\right)$ such sets, each giving $8!6!$ orderings. Their Shapley value is thereforeEvery ordering has exactly one pivotal member, since the empty coalition loses and the full coalition wins. This proves efficiency directly: $5\alpha +10\beta =1$, where $\alpha$ is the value of each permanent member. HenceThe vector has five entries $421/2145$ and ten entries $4/2145$. 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 $\alpha$.

True, with the usual normalization $v(\varnothing )=0$. For a convex cooperative game, the supermodular inequality implies increasing marginal contributions: if $A\subseteq B$ and $i\notin B$, apply it to $A\cup \{i\}$ and $B$ to obtainFix an ordering $\pi$ and let $P_i$ be the set of players before $i$. Its marginal contribution vector is $m_i^{\pi }=v(P_i\cup \{i\})-v(P_i)$. Summing in order telescopes to ${\sum }_i{m}_i^{\pi }=v(N)$. For any coalition $S$, $S\cap P_i\subseteq P_i$, so increasing marginals giveThese are exactly the efficiency and coalition constraints of the core of a cooperative game. Thus every marginal contribution vector is in the core. The core is a convex set, being an intersection of linear half-spaces and an efficiency hyperplane. The Shapley value is the average of the marginal contribution vectors over all orderings, so it too lies in the core. This proves Shapley value belongs to the core of a convex game, without needing a separate existence theorem for the core.

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand coalition worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For $G_2$, the stated weighted graph triangle has grand coalition value $2+3+3=8$ and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability $1/2$, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:The values sum to $8=v_2(N)$, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.

Assume the standard empty-coalition normalization $v(\varnothing )=0$. A convex cooperative game has increasing marginal contributions: whenever $A\subseteq B$ and $i\notin B$,This follows from the supermodular inequality applied to $A\cup \{i\}$ and $B$. Fix a permutation $\pi$ of all players, let $P_i$ be the players preceding $i$, and form its marginal contribution vectorSumming along the full permutation is a telescoping sum, so ${\sum }_{i\in N}{m}_i^{\pi }=v(N)$. For an arbitrary coalition $S$, list its members in their induced order $i_1,\dots ,i_k$, and put $S_j=\{i_1,\dots ,i_j\}$. Since $S_{j-1}\subseteq P_{i_j}$, increasing marginal contributions giveThus every marginal contribution vector belongs to the core. The vector of Shapley values is exactly their uniform average over the $n!$ permutations, hence a convex combination. By the preceding part, that average is in the core. This proves that the Shapley value allocation belongs to the core of a convex cooperative game, including every coalition constraint. It is the result Shapley value belongs to the core of a convex game.