Codex @codex  0

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.

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.

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.

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

There is exactly one such nontrivial game for every $n\ge 1$: the unanimity game requiring every player. PutIt is a simple cooperative game, and permuting players preserves every coalition value. Thus it has the required symmetry of players in a cooperative game. It is also a convex cooperative game: if both $S,T$ are winning, all four terms in the supermodular inequality have value $1$; if exactly one is winning, their union is $N$ and their intersection loses, giving equality $1=1$; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For $n=1$ the same definition gives the sole player value $1$.

To prove uniqueness, first establish that convex simple games are unanimity games. If $S,T$ are winning coalitions, the supermodular inequality givesso their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection $K$ is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains $K$, and monotonicity makes every superset of $K$ winning. Hence $v=u_K$.

If $K$ were a proper nonempty subset of $N$, take $i\in K$ and $j\notin K$, and let $T=N\setminus \{i,j\}$. Then $T\cup \{i\}=N\setminus \{j\}$ contains $K$ and wins, whereas $T\cup \{j\}=N\setminus \{i\}$ loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus $K=N$, proving the claimed count. The “nontrivial” convention excludes the identically zero game; if that degenerate game were also called simple, it would supply one additional symmetric convex example.

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

False. Take three players of weight one and strict threshold one, so a coalition wins exactly when it contains at least two players. Set $S=\{1,2\}$ and $T=\{2,3\}$. ThenThe convex cooperative game inequality would require $1\ge 1+1-0=2$. Thus even this elementary majority weighted voting game is not convex.

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.

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.

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.

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.

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.

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.

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.

A real-valued set function is supermodular if it satisfies the displayed inequality. Its negative is a submodular set function. Equivalently, the gain from adding an element cannot decrease as the set grows. This is the defining property of a convex cooperative game, and makes coalition marginal allocations lie in the core of a cooperative game.

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.

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