= Solution
Use the usual <empty-coalition normalization> $v(\varnothing)=0$ for a <transferable utility game>. Write $P_i=\{1,\ldots,i-1\}$, so the proposed <payoff> is the <marginal contribution>
$$
x_i=v(P_i\cup\{i\})-v(P_i).
$$
The 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$:
$$
v(A\cup\{i\})+v(B)
\le v(B\cup\{i\})+v(A).
$$
Rearranging gives
$$
v(A\cup\{i\})-v(A)
\le v(B\cup\{i\})-v(B).
$$
The vector is efficient by a <telescoping sum>:
$$
\sum_{i=1}^{n}x_i
=\sum_{i=1}^{n}
\bigl(v(\{1,\ldots,i\})-v(\{1,\ldots,i-1\})\bigr)
=v(N)-v(\varnothing)=v(N).
$$
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 give
$$
x_i\ge v((T\cap P_i)\cup\{i\})-v(T\cap P_i).
$$
Sum over the members of $T$ in increasing order. The right-hand side is another <telescoping sum>, now along the growing <coalition> $T$:
$$
\sum_{i\in T}x_i\ge v(T)-v(\varnothing)=v(T).
$$
Efficiency and these inequalities for every <coalition> are exactly the defining requirements of the <core of a cooperative game>. Thus \b[$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.
Back to article page
