Abstract Generated abstract
This paper studies cooperative games in reduced 0-1 form and the relation between the core and stable solutions under continuous changes of the characteristic function. It considers a family of games in which coalition values are nondecreasing continuous functions of a parameter, defines a set formed from the current core together with traces of earlier intersections of core boundary hyperplanes, and proves that this set is externally stable whenever the initial core is a solution and the final core is nonempty. The argument analyzes imputations outside the constructed set and shows that each is dominated by an imputation within it. An example concerning a market with one seller and several buyers illustrates conditions under which the constructed externally stable set is also internally stable, thereby yielding a solution.
Full Text
UDC 519
MATHEMATICS
O. BONDAREVA
A THEOREM ON EXTERNALLY STABLE SETS
(Presented by Academician Yu. V. Linnik on 23 X 1969)
Consider a cooperative game \(\Gamma\) with the set of players \(I=\{1,2,\ldots,n\}\) and characteristic function \(v(S)\), given in 0–1-reduced form, i.e.
\[ v(i)=0,\quad i=1,2,\ldots,n;\qquad v(I)=1. \]
Then the set of imputations is
\[ A=\left\{x=(x_1,\ldots,x_n): x_i\geq 0,\ \sum_{i=1}^{n}x_i=1\right\}. \]
As is known, a solution is a set of imputations \(V\subset A\) possessing internal and external stability.
The core is a considerably simpler object than a solution; it has the form
\[ U=\left\{x\in A:\ \sum_{i\in S}x_i\geq v(S),\ \forall S\subset I\right\}. \]
If all \(v(S)=0,\ S\subset I,\ S\ne I\), then \(A=U\) and \(U\) is a solution; known are also nontrivial sufficient conditions which \(v(S)\) must satisfy for the core to be a solution (see \((^{1,2})\)).
The question arose whether it is possible to construct some transition from the core to a solution. It turns out that if, in a three-person game, one continuously increases \(v(S)\), \(|S|=2\), up to some \(v'(S)\) at which the core is still nonempty, then the latter, together with the traces of the intersections of its boundaries during this process (see the precise definitions below), gives a solution of the game. In the general case one can prove only the external stability of such a set.
We now formulate the problem mathematically. Consider a family of games \(\Gamma_t,\ 0\leq t\leq 1\), with the set of players \(I=\{1,2,\ldots,n\}\), the same for all games, and let
\[ v_t(i)\equiv 0,\qquad 0\leq t\leq 1, \]
\[ v_t(I)\equiv 1,\qquad 0\leq t\leq 1, \]
and let \(v_t(S)=f_S(t),\ 2\leq |S|\leq n-1\), be nondecreasing continuous functions on \(0\leq t\leq 1\).
Denote by \(U(t)\) the core of the game \(\Gamma_t\), by \(V(t)\) the solution, and by \(F(t)\) the following set:
\[ F(t)= \bigcup_{0\leq \tau<t}\ \bigcup_{S\ne T} \left\{ \begin{array}{l} x\in U(\tau),\\[3pt] \displaystyle \sum_{i\in S}x_i=f_S(\tau),\quad 2\leq |S|\leq n-1,\\[8pt] \displaystyle \sum_{i\in T}x_i=f_T(\tau),\quad 2\leq |T|\leq n-1. \end{array} \right. \]
Put \(W(t)=F(t)\cup U(t)\). Note that the set of imputations \(A\) is the same for all games \(\Gamma_t\).
Theorem. If the family of games \(\Gamma_t,\ 0\leq t\leq 1\), is such that: 1) \(U(0)=V(0)\); 2) \(U(1)\ne \Lambda\), then the set \(W(t)\) is externally stable in the game \(\Gamma_t\) for every \(0\leq t\leq 1\).
Proof. Fix some \(t: 0<t\leq 1\) (for \(t=0\) the theorem is true by condition 1)). The external stability of \(W(t)\) means that, whatever \(z\in A-W(t)\) may be, there exists an \(x\in W(t)\) such that \(x>z\).
Consider two possibilities.
I. \(z\notin U(\tau)\), \(0\leq \tau\leq t\). Since \(U(0)=V(0)\) and \(z\notin U(0)\), there exist \(y\in U(0)\) and an essential \(S_0\) such that
\[ y \underset{S_0}{>} z. \tag{1} \]
Consider the sets
\[ h_{S_0}(\tau)=U(\tau)\cap \left\{x:\sum_{i\in S_0}x_i=f_{S_0}(\tau)\right\}, \]
\[ H_{S_0}(t)=\bigcup_{0\leq \tau\leq t} h_{S_0}(\tau) \]
and the convex open cone
\[ K_{S_0}(z)=\{x\in A: x_i>z_i,\ \forall i\in S_0\}. \]
In view of condition (1), \(K_{S_0}(z)\cap h_{S_0}(0)\neq \Lambda\).
1) If \(H_{S_0}(t)\in F(t)\), then \(y\in W(t)\), and \(y>z\); there remains the case:
2) \(H_{S_0}(t)\notin F(t)\), i.e., there exists an \(x\in H_{S_0}(t)\) such that
\[ \sum_{i\in S} x_i>v(S), \]
\(S\subset I,\ S\neq S_0\); this means that \(H_{S_0}(t)\) is a closed domain of dimension \((n-1)\) in Euclidean space \(E_{n-1}\). Since \(K_{S_0}(z)\cap h_{S_0}(0)\neq \Lambda\), the open cone \(K_{S_0}(z)\) intersects the set \(H_{S_0}(t)\) at some point \(\omega\) lying on the boundary of \(H_{S_0}(t)\), but not belonging to \(h_{S_0}(0)\). If, in addition:
a) \(\omega_i>0,\ i=1,2,\ldots,n\), then \(\omega\in F(t)\), hence \(\omega\in W(t)\), and \(\omega>z\); there remains the case b) \(\omega_{i_0}=0\) and \(\omega\notin F(t)\); necessarily then \(i_0\notin S_0\); let
\[ \tau_0:\quad \sum_{i\in S_0}\omega_i=f_{S_0}(\tau_0)>f_{S_0}(0), \]
then
\[ \sum_{i\in T}\omega_i>f_T(\tau_0),\quad T\neq S_0. \tag{2} \]
Consider the allocation \(a(\mathscr{E})=(a_1(\mathscr{E}),\ldots,a_n(\mathscr{E}))\):
\[ a_i(\mathscr{E})=\omega_i+\frac{\mathscr{E}}{|S_0|},\quad i\in S_0, \]
\[ a_j(\mathscr{E})=\omega_j-\mathscr{E}_j,\quad j\notin S_0, \]
\[ \mathscr{E}\geq 0,\quad \mathscr{E}_j\leq \omega_j,\quad \sum_{j\notin S_0}\mathscr{E}_j=\mathscr{E}. \]
It is easy to show that, by continuously increasing \(\mathscr{E}\), we finally obtain such an \(\overline{\mathscr{E}}\) that either \(a(\overline{\mathscr{E}})\in U(t)\), or at least two conditions from (2) are violated, i.e. \(a(\overline{\mathscr{E}})\in F(t)\). Hence, also in case b), there exists \(a(\overline{\mathscr{E}})>z\), \(a(\overline{\mathscr{E}})\in W(t)\).
II. \(z\in U(\tau_0)\), \(0\leq \tau_0<t\), i.e. \(z\in U(0)\). Consider the sets \(H_S(t)\) for all \(S: 1<|S|<n\) (they may be both empty and repeating). It is clear that
\[ \bigcup_S H_S(t)\cup U(t)=U(0); \]
since \(z\notin U(t)\), there exists a nonempty \(H_{S_0}(t): z\in H_{S_0}(t)\). Consider the cone \(K_{S_0}(z)\); since
\[ \sum_{i\in S_0} z_i\geq v(S_0) \]
and \(K_{S_0}(z)\) is open, \(K_{S_0}(z)\cap h_{S_0}(0)=\Lambda\). Since \(z\notin F(t)\), \(H_{S_0}(t)\) in the space \(E_{n-1}\) is a closed set of the same dimension, the point \(z\) is an interior point of \(H_{S_0}(t)\); hence the cone \(K_{S_0}(z)\) intersects \(H_{S_0}(t)\) at a point \(y\notin h_{S_0}(0)\). Further, as in case I, 2), considering two possibilities, we complete the proof.
Example. Consider a market with one seller, player 1, and buyers, players \(2,3,\ldots,n\). Then \(v(S)=0,\ 1\notin S\), and let \(v(1,2,\ldots\)
\[ \ldots,n)=1. \]
If \(v(S) \leq 1/(n-|S|+1)\), \(1 \in S\), then, by the theorem of T. E. Kulakovskaya, the game has a solution coinciding with the core.
Consider the transformation
\[ f_{S_0}(t)=t,\quad S_0=(2,3,\ldots,n);\qquad f_S(t)\equiv v(S),\quad S\ne S_0; \]
it is obvious that \(\Gamma_t\), for any \(0\leq t\leq 1\), has a nonempty core.
Consider the set \(W(t)\), \(0\leq t\leq 1\); it is externally stable in \(\Gamma_t\) by the theorem. Its internal stability can be violated because of domination by the coalition \(S_0\). But for any \(x=(x_1,\ldots,x_n)\):
\[ \sum_{i=2}^{n} x_i=t, \]
\[ \sum_{i\in S} x_i \geq v(S), \]
if \(y=(y_1,\ldots,y_n)\) is such that \(y_i<x_i,\ i=2,\ldots,n\), then
\[ \sum_{i\in S} y_i>v(S),\quad 1\in S, \]
i.e. \(\operatorname{dom} h_{S_0}(t)\) lies inside the core \(U(0)\), that is, \(W(t)\) is internally stable.
Thus, a solution has been described for any game:
\[ v(S)\leq 1/(n-|S|+1),\quad 1\in S;\qquad v(S)=0,\quad S\subset \{2,\ldots,n\}; \]
\[ v(2,3,\ldots,n)\leq 1. \]
Leningrad State University
named after A. A. Zhdanov
Received
7 X 1969
CITED LITERATURE
- O. N. Bondareva, Problems of Cybernetics, no. 10, 1963.