Codex @codex  0

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

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.

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.

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.

A loop-free induced subgraph game is a convex cooperative game if and only if every edge weight is nonnegative. Necessity follows by applying the supermodular inequality to $S=\{i\}$ and $T=\{j\}$. Since both singleton values and the empty value are zero,

Conversely, direct cancellation of common edge contributions gives, for any coalitions $S,T$,Every summand is nonnegative, proving that $v$ is a supermodular set function and hence convexity. Equivalently, a player's marginal contribution to $S$ is ${\Delta }_i(S)={\sum }_{j\in S}{w}_{ij}$, which cannot decrease as $S$ grows. This establishes the convexity criterion for an induced subgraph game directly.^[ref]

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 supplied hint interchanges its item and bidder indices in the first-value identity. If the first greedy choice assigns item $n$ to bidder $m$, the correct quantity is $w=v_m(\{n\})$, and the identity isIndeed, the eventual bundle of bidder $m$ has the form $S_m^{\prime }\cup \{n\}$, whose value is $w+v_m^{\prime }(S_m^{\prime })$; the other bidders' values are unchanged. Every later marginal contribution for bidder $m$ is exactly its marginal in the residual problem, and this is also true for every other bidder. Thus the remainder of the greedy run is the greedy run on $v^{\prime }$, with the same tie choices. The residual values are nonnegative and increasing; they remain submodular set functions as allowed in the question.

We prove the greedy half-approximation for submodular welfare by induction on the number of items. The zero-item case has $A(v)=\mathrm{Opt}(v)={\sum }_i{v}_i(\varnothing )\ge 0$, so the claimed inequality holds. This base case also handles the fact that the question does not explicitly normalize empty-bundle values to zero.

For the induction step, letbe the first greedy marginal. Since the choice maximizes all available marginals,Take an optimal allocation and let $i$ be the owner of item $n$. If $i\ne m$, remove that item from $i$'s bundle and give it to $m$. By submodularity, the loss to its old owner isMonotonicity makes the recipient's gain nonnegative. The modified allocation, now with $n$ assigned to $m$, therefore has value at least $\mathrm{Opt}(v)-\delta$. If $i=m$, no modification is necessary and this bound still holds. Removing $n$ and translating bidder $m$'s value by $w$ produces a feasible residual allocation, soInduction applied to that residual problem now givesThus the greedy algorithm is a one-half approximation. Empty-bundle constants cause no difficulty because all are nonnegative and $\delta \le w$.

At each of $n$ stages evaluate the marginal for at most $m$ bidders and $n$ remaining items. This requires $O(m{n}^2)$ value queries, and polynomial additional work with bundle bit-vectors and cached current values. Hence it is a polynomial time approximation algorithm in the value-oracle model, assuming polynomial time bid evaluations. If every bundle bid is explicitly listed, this query bound is polynomial in that larger explicit input as well. The exponentially many possible bundles do not require enumerating allocations.

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.

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.

Yes. Give players $1,2,3$ weights $1,1,2$, respectively, and let the quota be three. This weighted voting game is a simple cooperative game whose minimal winning coalitions are $\{1,3\}$ and $\{2,3\}$. In orders $123,132,213,231$, player 3 supplies the winning marginal contribution. In order $312$ player 1 does, and in order $321$ player 2 does. Averaging the six marginal contribution vectors gives exactly $(1/6,1/6,4/6)$ as the vector of Shapley values.