= Solution
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)\geq 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$.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2004/iii/paper-33-owned-network.png]
{title=Company ownership and capacities in the two-demand communication network}
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 are
$$
u+w\leq3,\quad u\leq1,\quad v\leq1,\quad
v+w\leq2,\quad w+z\leq2,\quad u,v,w,z\geq0,
\qquad R=6(u+v+w)+4z.
$$
Every feasible traffic pattern decomposes into these <graph paths>, so these inequalities are exact. The first is redundant, since $u\leq1$ and $w\leq2$ 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):
$$
\begin{array}{c|c}
s\to t&(1,-6)\\
s\to L&(2,0)\\
L\to t&(1,-6)\\
L\to R&(\infty,-6)\\
s\to R&(\infty,-4)\\
R\to t&(2,0)\\
t\to s&(\infty,0)
\end{array}
$$
The first forward <graph path> carries $u$, $sLt$ carries $v$, $sLRt$ carries $w$, and $sRt$ carries $z$. Conservation at $L$ imposes $v+w\leq2$, and at $R$ imposes $w+z\leq2$; 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:
$$
R=6u+4v+2(v+w)+4(w+z)
\leq6+4+4+8=22.
$$
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$, and
$$
\boxed{R_{\max}=\text{£}22000.}
$$
All 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. Therefore
$$
\begin{array}{c|rrrrrrr}
S&\{i\}&\{j\}&\{k\}&\{i,j\}&\{i,k\}&\{j,k\}&N\\ \hline
v(S)&0&0&8&12&12&8&22.
\end{array}
$$
Writing payments in thousands, all stable divisions of the revenue are exactly
$$
\boxed{\begin{gathered}
x_i+x_j+x_k=22,\qquad x_i,x_j\geq0,\quad x_k\geq8,\\
x_i+x_j\geq12,\quad x_i+x_k\geq12,\quad x_j+x_k\geq8.
\end{gathered}}
$$
Equivalently, $8\leq x_k\leq10$, $0\leq x_j\leq10$ 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 gives
$$
-x_i,\quad -x_j,\quad 8-x_k,\quad x_k-10,\quad x_j-10,\quad x_i-14.
$$
The 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\leq x_j\leq9$ 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
$$
\boxed{\text{the nucleolus pays }(\text{£}8000,\text{£}5000,\text{£}9000)
\text{ to }(i,j,k).}
$$
Back to article page
