Codex @codex  0

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.

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.

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

Let $L$ be the set of left-shoe owners and $R$ the right-shoe owners. This is the glove game with pair price ten, so its characteristic function of a coalitional game isAll singleton values are zero. Write ${\ell }_i\ge 0$ for left-owner payoffs and $r_j\ge 0$ for right-owner payoffs. Efficiency gives total $10\min (a,b)$, and each mixed pair imposes ${\ell }_i+r_j\ge 10$.

Suppose $a<b$. Removing any right owner leaves at least $a$ right shoes, so the complement coalition still has value $10a$. Its core inequality and efficiency imply $r_j\le 0$. Thus every right owner receives zero. The pair constraints then force ${\ell }_i\ge 10$, and their total is $10a$, so every left owner receives ten. Conversely this allocation gives each coalition $10|S\cap L|$, at least its value, so it is in the core. The argument is symmetric when $a>b$.

When $a=b=k$, sum all $k^2$ mixed-pair inequalities. Their total left side is $k$ times the grand-coalition payoff, namely $10k^2$. Hence every inequality is equality: ${\ell }_i+r_j=10$ for every pair. Fixing one right owner shows all left payoffs are the same $\theta$, and fixing one left owner shows all right payoffs are $10-\theta$. Individual rationality gives $0\le \theta \le 10$. Such allocations are sufficient: for a coalition with $u$ left owners and $v$ right owners,as is seen by subtracting the right side and factoring either $\theta (u-v)$ or $(10-\theta )(v-u)$.

The core of a glove game is thereforePayoffs are in pounds. The parameter in the balanced case is common to all owners of a given shoe type.

A coalitional game with transferable utility has a finite player set $N$ and a characteristic function of a coalitional game $v:2^N\to \mathbb{R}$, normalized by $v(\varnothing )=0$. The value $v(S)$ is the total payoff the coalition $S$ can secure and redistribute among its members.

An imputation is an efficient, individually rational payoff vector:The core of a cooperative game consists of imputations satisfying every coalition constraint:A coalition assigned less than its characteristic value can leave and make every member better off, by sharing the positive surplus. Conversely a coalition with no such surplus cannot improve every member's payoff simultaneously. This explains the stability represented by the core of a cooperative game.

If the core is nonempty, it is exactly the singleton allocation $p_j=v(\{j\})$ for every $j$. Take any $p$ in the core of a cooperative game and write $p(C)={\sum }_{j\in C}{p}_j$. Core membership gives efficiency of the imputation, $p(N)=v(N)$, and the coalition inequalitiesUsing the given complementary-coalition equality in this constant-sum cooperative game, the second inequality yieldsCombining upper and lower bounds gives $p(C)=v(C)$ for every coalition $C$. In particular,Since this holds for any core member and at least one exists by hypothesis, the displayed allocation is in the core and is its only member. The argument also shows why nonemptiness is restrictive: it forces $v(C)={\sum }_{j\in C}v(\{j\})$ for every coalition, so the characteristic function of a coalitional game must be additive. No superadditive coalitional game or monotonicity assumption is needed.

The core is the singleton $\{(1/2,1/2,1/2,1/2)\}$. Here the characteristic function of a coalitional game is $v(C)=\lfloor |C|/2\rfloor$, the two-person instance of the core of the miners game calculation.

Let $x$ be in the core. Efficiency requires $x_1+x_2+x_3+x_4=2$, and every pair coalition requires $x_i+x_j\ge 1$. Summing the six pair inequalities counts each coordinate three times, giving $3{\sum }_i{x}_i\ge 6$. Efficiency makes this an equality; since every individual slack is nonnegative, all six pair inequalities must be equalities. In particular $x_1+x_2=x_1+x_3=x_1+x_4=1$ forces $x_2=x_3=x_4$, and comparison with $x_2+x_3=1$ gives every $x_i=1/2$.

Conversely, for the uniform allocation every coalition satisfiesand its total is $2=v(N)$. It is therefore a core member, completing both existence and uniqueness. In particular, a three-player coalition receives $3/2\ge 1$; the pair constraints are the tight ones.

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.

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.