=Paper=
{{Paper
|id=Vol-1623/paperme12
|storemode=property
|title=On Strong Accessibility of the Core of TU Cooperative Game
|pdfUrl=https://ceur-ws.org/Vol-1623/paperme12.pdf
|volume=Vol-1623
|authors=Valery Vasilev
|dblpUrl=https://dblp.org/rec/conf/door/Vasilev16
}}
==On Strong Accessibility of the Core of TU Cooperative Game==
https://ceur-ws.org/Vol-1623/paperme12.pdf
On Strong Accessibility of the Core
of TU Cooperative Game
Valery Vasil’ev
Sobolev Institute of Mathematics, Russian Academy of Sciences,
Prosp. Acad. Koptyuga 4, 630090 Novosibirsk, Russia
vasilev@math.nsc.ru
Abstract. In the paper, a strengthening of the core-accessibility theorem by
the author is proposed. It is shown that for any imputation outside of the
nonempty core of TU cooperative game a strongly monotonic trajectory orig-
inating from this imputation exists, which converges to some element of the
core. Here, strong monotonicity means that each imputation from the trajec-
tory dominates several preceding elements and, besides, the number of these
dominated imputations tends to infinity. To show that transferable utility as-
sumption is relevant for strong accessibility of the core, we give an example of
NTU cooperative game with a “black hole” being a nonempty closed subset of
dominated imputations that contains all the sequential improvement trajecto-
ries originating from its points.
Keywords: Domination, core, strong monotonicity, strong accessibility, dy-
namic system, endpoint, generalized Lyapunov function
1 Introduction
Let N = {1, . . . , n} be a set of players. Recall (see, e.g., [2], [4]), that an n-person
cooperative game with transferable utility (TU cooperative game, for short) on N is
a function v : 2N → R that associates with each subset S ⊆ N (called a coalition, if
nonempty), a real number v(S), the worth of S (it is required that v(∅) = 0). If “big
coalition” N forms, then it can divide its worth, v(N ), in any possible way among the
players i ∈ N. In case each player i is endowed with amount not less than her worth,
v({i}), we get so-called imputation (individually-rational and efficient payoff) of the
game v. Collection of imputations of the game v is denoted by I(v) (below, we use a
standard shortening v(i) = v({i})):
∑
I(v) = {x ∈ RN | xi = v(N ), xi ≥ v(i), i ∈ N } .
i∈N
Further, we apply one more shortening: for any x = (x1 , . . . , xn ) ∈ RN and S ∈ 2N we
put
∑
x(S) = xi .
i∈S
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
644 Valery Vasil’ev
In order to introduce classic domination relation αv on I(v), some additional terms are
required. First, recall that imputation x is said to be dominated by imputation y via a
coalition S, if xi < yi , i ∈ S, and y(S) ≤ v(S). Further, we say, for short, that x ∈ I(v)
is dominated by y ∈ I(v), if there exists a coalition S such that x is dominated by y
via S. Finally, we say that x ∈ I(v) is dominated, if there exists an imputation y that
dominates x. Respectively, an imputation x is said to be un-dominated, if there is no
imputation that dominates it.
To summarize, we get formal descriptions of the classic domination relation αv on
I(v), given by the formula
x αv y ⇔ ∃S ∈ 2N \ {∅} [(xi < yi , i ∈ S) & (y(S) ≤ v(S))] ,
and the core C(αv ) of v being the set of un-dominated imputations of v :
C(αv ) = {x ∈ I(v) @y ∈ I(v)[ x αv y ]} .
Recall (see, e.g., [3], [4]), that the core C(αv ) is one of the main solutions of cooperative
game theory with numerous applications to social, economic, and political problems.
One of the most interesting problems relating to the core C(αv ) seems to be an asymp-
totic behavior of the processes of sequential improvement of dominated alternatives
(does there exist a non-dominated limit, or we deal with chaotic movement, etc. ).
Speaking formally, we have to study so-called αv -monotonic trajectories {xr }∞ r=0 with
xr ∈ I(v), r ≥ 0, originated from imputations outside the core C(αv ).
Definition 1. A sequence {xr }∞ r=0 with xr ∈ I(v), r ≥ 0, is said to be αv -monotonic
(monotonic, for short), if for each natural number r ≥ 1 it holds xr−1 αv xr .
Speaking differently, a sequence {xr }∞r=0 of imputations is called αv -monotonic, if any
element xr+1 dominates preceding element xr .
In the paper, we consider one of the problem relating to the asymptotic behavior of
monotonic sequences, so-called core-accessibility problem. Namely, we are interesting
if there exists, for any imputation outside the core, at least one monotonic sequence
starting at that imputation and converging to some un-dominated imputation. And if
so, what additional improvements of this sequence can be made. To isolate the cores
satisfying accessibility property mentioned, we present one of the key definitions of the
paper.
Definition 2 (Vasil’ev, 1987). The core C(αv ) of TU cooperative game v is called
accessible, if C(αv ) ̸= ∅, and for any imputation x ∈/ C(αv ) there exists a convergent
αv -monotonic sequence {xr }∞ r=0 of imputations such that x0 = x and limr→∞ xr belongs
to the core C(αv ) of the game v.
It turned out that the core-accessibility takes place for any TU cooperative game with
non-empty core.
Theorem 1 (Accessibility Theorem). The core C(αv ) of any TU cooperative game
v is accessible whenever it is nonempty.
On Strong Accessibility of the Core of TU Cooperative Game 645
This theorem was established in [5] (for more details, see [6]). It is worth to stress,
that both articles mentioned exploit only classic settings, including classic definitions
of imputation and domination (not like in [8], for instance, where the author, instead
of I(v), deals with a greater set of payoffs, thus essentially enlarging possibilities of
reconstruction for the elements outside the core).
A strengthening of Accessibility Theorem, proposed in the paper, is motivated by
the lack of transitivity of domination αv . Sequential improvement process {xr }∞ r=0 ,
based on non-complete and non-transitive binary relation αv , may contain several frag-
ments of type xr−1 αv xr αv xr+1 with xr+1 that doesn’t dominate xr−1 . Even more,
we may get a cycle xr−1 αv xr αv xr+1 αv xr−1 or more lengthy cycle
xr−1 αv xr αv . . . αv xm αv xr−1
with m > r + 1. Unfortunately, we have no idea relating to the exclusion of this
type of cycling in sequential improvement process. What can we do is just providing
each imputation xr+1 in the process {xr }∞ r=0 to be able dominate a wider collection of
previous imputations than a singleton {xr }. Certainly, it would be very nice to organize
an improvement process in such a way that any imputation xr+1 dominates all the
previous xm , m = 0, 1, . . . , r. But already very simple 3-person games demonstrate
impossibility of such a total domination phenomenon. Nevertheless, it turned out that
we can essentially refine improvement process provided that instead of αv -monotonicity
we apply its strengthening, given in the following definition.
Definition 3. A sequence {xr }∞ r=0 of imputations of TU cooperative game v is said to
be strongly αv -monotonic (strongly monotonic, for short), if there exists a sequence of
natural numbers kr → ∞ such that kr ≤ r, r ≥ 1, and xr−m αv xr for any r ≥ 1 and
m ∈ [1, kr ].
Now, we are in position to present main definition of the paper.
Definition 4. Let the core C(αv ) be non-empty. Then C(αv ) is said to be strongly ac-
cessible, if for any x ∈ I(v)\C(αv ) there exists a convergent and strongly αv -monotonic
sequence of imputations {xr }∞r=0 such that x0 = x and lim xr belongs to the core C(αv ).
In the paper, we propose a strengthening of above mentioned Accessibility Theorem:
for any TU cooperative game v the core C(αv ) is strongly accessible whenever it is
nonempty. Thus, in case of TU cooperative games we can raise the quality of a mono-
tonic improvement process to a rather high level. Note that another variant of raising
quality of improvement process is given in [7]: the case of constant kr (kr = k, r ≥ k)
is considered instead of the case kr → ∞.
The paper is organized as follows. Besides Introduction, it contains two parts and
appendix. First part is devoted to the proof of the strong accessibility theorem, second
part contains an example of NTU cooperative game that has nonempty core, which is
not accessible. Appendix, for the sake of completeness, is devoted to brief outline of
the proof of Accessibility Theorem. In contrast to [6], this proof is a straightforward
one. Moreover, it is not “immersed” into a more general setting, like in [5], [6].
646 Valery Vasil’ev
2 Proof of the Strong Accessibility Result
In this section we give a proof of strong accessibility of the core of TU cooperative game.
We show that any sequential improvement process that exists according to Theorem 1
admits a considerable improvement of its quality, suffering due to the non-transitivity
of classic domination relation. This lack of transitivity in the process of sequential
improvement of dominated alternatives may be inadmissible in many applications of
game theory to economical, sociological and political problems. By reconstructing a
monotonic process in appropriate way, we can get a strongly monotonic improvement
process with each imputation (except the first and second ones) dominating several
preceding alternatives. Even more, the number of this dominated alternatives tends
to infinity. Passing on to the formal presentation of the strong accessibility result, we
stress once more that its proof heavily relies upon Accessibility Theorem and some
elementary topological properties of the domination relation αv .
Theorem 2. Let v be an n-person TU cooperative game with nonempty core C(αv ).
Then for any imputation x ∈ I(v) \ C(αv ) there exist a sequence of natural numbers
kr → ∞ with kr ≤ r, r ≥ 1, and convergent sequence of imputations {xr }∞ 0 such that
x0 = x, limr→∞ xr belongs to the core C(αv ), and, besides, xr−m αv xr for all natural
numbers r ≥ 1 and m ∈ [1, kr ].
Proof. Let v be an n-person TU cooperative game with nonempty core C(αv ), and x be
some dominated imputation. Without loss of generality we may assume that v satisfies
requirement: v({i}) = 0 for each i ∈ N. Due to Accessibility Theorem there exists
an αv -monotonic convergent sequence of imputations {xr }∞ r=0 such that x0 = x and
x∗ = limr→∞ xr ∈ C(αv ). By Definition 1, for any r ≥ 1 there exists a coalition Sr such
that imputation xr = (xr,1 , . . . , xr,n ) dominates imputation xr−1 = (xr−1,1 , . . . , xr−1,n )
via Sr :
xr−1,i < xr,i , i ∈ Sr ; xr (Sr ) ≤ v(Sr ), r = 1, 2, . . . . (1)
Below, we exploit max-metric ρ∞ (x, y) = ∥x − y∥∞ = max {|xi − yi | i ∈ N } (re-
spectively, all the distances and neighborhoods we use in this section are given in this
metric). By applying max-metric we define vicinities Ur of imputations xr in order to
modify the sequence {xr }∞ r=0 in a way required by the definition of strong accessibility.
Namely, for any r > 1 we put
εr = min {xr,i − xr−1,i i ∈ Sr }/2
and define δr = min {εr , εr+1 }, r > 1. Further, for any r > 1 denote by Ur the
δr -neighborhood of the imputation xr :
Ur = {y ∈ I(v) ρ∞ (xr , y) < δr }, r = 2, 3, . . . . (2)
Fix some r ≥ 1. Since xr−1 is dominated by xr via the coalition Sr , directly from (1)
and 0-normalization condition v({i}) = 0, i ∈ N, it follows that
xr (Sr ) ≤ v(Sr ) and xr,i > 0, i ∈ Sr .
On Strong Accessibility of the Core of TU Cooperative Game 647
Hence, we may construct a “bundle” {xm r }m=1 ⊆ Ur satisfying αv -monotonicity con-
r−1
dition with respect to the coalition Sr :
x1r,i < x2r,i < . . . < xr−1
r,i < x r,i , i ∈ Sr , (3)
where xm m m m
r,i is an i-th component of the imputation xr = (xr,1 , . . . , xr,n ) of the game
1 r−1
under consideration. One can rather easily check that xr , . . . , xr may be given by
the formulae: xm r = xr + (m − r)c with
{
δr (n − sr )/nr , i ∈ Sr ,
ci =
−δr sr /nr , i ∈ N \ Sr ,
where sr = |Sr |, r ≥ 1. In particular, inclusions xr +(m−r)c ∈ Ur , m ∈ [1, r−1], r ≥ 1,
follow directly from the elementary relations1
∑ sr (n − sr ) ∑
ci = δr =− ci , r≥1,
nr
i∈Sr i∈N \Sr
r − m n − sr
(r − m)ci = δr < δr , i ∈ Sr , m ∈ [1, r − 1], r ≥ 1 ,
r n
r − m sr
(r − m)ci = δr < δr , i ∈ N \ Sr , m ∈ [1, r − 1], r ≥ 1 .
r n
Let us mention also, that monotonicity condition means (due to the inequality x(Sr ) ≤
v(Sr ) following from the assumption that xr dominates xr−1 via the coalition Sr ), that
in (general) collection {xm r }m=1 each imputation xr dominates preceding xr
r−1 m m−1
via
coalition Sr . Besides, the last element in the collection is dominated by xr : xr−1
r αv xr .
Note, that relations mentioned
x1r αv x2r αv . . . αv xr−1
r αv xr
possess some “transitivity features”: each element of the collection under consideration
dominates all the preceding elements. As to xr , it dominates (together with xr−1 ) each
imputation xmr , m = 1, . . . , r−1. Note also, that according to the choice of the vicinities
Ur we get: the first imputation x1r (together with the others xm r , m ≤ r − 1) dominates
xr−1 and xmr−1 , m = 1, . . . , r − 2, via the coalition S r .
Passing on to the formation of a sequence {ys }∞ s=0 , originating from the above men-
tioned imputation x ∈ / C(αv ) and satisfying all the requirements of strong accessibility,
we introduce first the numbers er = r(r + 1)/2, r = 1, . . . . Further, by exploiting
∞
above mentioned elements xr and xm r we define the sought for sequence {ys }s=0 by the
formula
x0 = x , if s = 0;
ys = xr , if s = er ; (4)
m
xr+1 , if s = er + m and m ∈ [1, r] .
1
One may proceed by investigating these or some other appropriate concrete bundles. Below,
we apply more general consideration, which admits extensions to a more abstract settings.
648 Valery Vasil’ev
We start with the proof that sequence {ys }∞ s=0 is convergent, and its limit is equal
to x∗ = limr→∞ xr . Fix an arbitrary ε > 0 and show that there exists a number s0
such that ρ∞ (ys , x∗ ) < ε for any s > s0 . To this end let us mention that due the
convergency xr → x∗ there exists r0 such that ρ∞ (xr , x∗ ) < ε/2 for any r > r0 .
Further, from xr → x∗ it follows also that limr→∞ δr = 0. In fact, by definition of
the numbers δr we get δr ≤ ρ∞ (xr , xr−1 ), r ≥ 1. But the right-hand sides of these
inequalities converge to zero, and, consequently, we get desired: δr → 0. Therefore,
there exists r1 such that δr < ε/2 for any r > r1 . Put s0 = er̄ = r̄(r̄ + 1)/2, where
r̄ = max {r0 , r1 } + 1. To estimate the distance ρ∞ (ys , x∗ ) we consider two different
cases: 1) s = er for some r ≥ r̄, and 2) s = er + m for some r ≥ r̄ and m ∈ [1, r]. In
the first case, due to the inequality s = er(s) > er̄ we get r(s) > r0 . Hence, by equality
yer(s) = xr(s) following from the definition of ys we get
∥ys − x∗ ∥∞ = ∥xr(s) − x∗ ∥∞ < ε/2 .
As to the second case, when s = er(s) + m > s0 with m belonging to the interval
m(s) m(s)
[1, r(s)], according to the formula (4) we have ys = xr(s)+1 . Since xr(s)+1 belongs to
the vicinity Ur(s)+1 of the imputation xr(s)+1 we get (due to the definition of Ur(s)+1
and obvious inequality r(s) + 1 > r1 )
m(s)
∥ys − x∗ ∥∞ ≤ ∥xr(s)+1 − xr(s)+1 ∥∞ + ∥xr(s)+1 − x∗ ∥∞ < δr(s)+1 + ε/2 < ε.
Thus, in both cases we get estimations desired, which complete the proof of convergency
ys → x∗ ∈ C(αv ).
To finalize the proof of Theorem 2 we have to show that for any s > 1 imputation
ys dominates together with the preceding element ys−1 some more distant previous
imputations ys−m , m ∈ [2, ks ] with ks → ∞. Put ks = r for any s ∈ [er , er+1 ), r ≥ 1. It
is clear that ks chosen tends to infinity. To prove that for any s ∈ [er , er+1 ) imputation
ys dominates at least r nearest preceding imputations of the sequence {ys }∞ s=0 we
consider two possible cases: 1)s = er , and 2) s = er + m with m ∈ [1, r]. In the first
case according to the formulae (3), (4), and αv -monotonicity of the sequence {xr }∞ r=0
we get: yer−1 = xr−1 αv xr = yer = ys and yer−1 +p = xpr αv xr = yer = ys for
all p ∈ [1, r − 1]. In the second case without loss of generality we consider situation
m = 1 only. Taking account our choice of vicinities Ur (see formula (2)), we obtain
(below, domination is realized via coalition Sr+1 ): ys−1 = xr αv x1r+1 = ys and, besides,
ycr−1 +p = xpr αv x1r+1 = ys for all p ∈ [1, r − 1].
Thus, the sequence {ys }∞s=0 meets all the requirements of Definition 3, and this fact
completes the proof of Theorem 2. ⊔
⊓
3 NTU Case: A Counterexample
To demonstrate that transferable utility assumption (namely, assumption that games
under consideration are TU games) is essential even if we deal with the weakest form
of accessibility, we give an example of NTU cooperative game with “black hole” being
a nonempty closed subset of dominated imputations, which contains all the monotonic
trajectories originating from its points2 .
2
A bit more complicated counterexample can be found, also, in [6].
On Strong Accessibility of the Core of TU Cooperative Game 649
Recall (see, e.g. [4]), that cooperative game with nontransferable utility (an NTU
cooperative game, for short) is a pair (N, G), where N = {1, . . . , n} is a set of players,
and G is a function that associates with each nonempty S ⊆ N a nonempty ∩ subset
G(S) of RS such that G(S) is (i) comprehensive, (ii) closed, and (iii) G(S) (xS +RS+ )
is bounded for every xS ∈ RS . Here comprehensiveness of G(S) means that for any
x ∈ G(S) and y ≤ x it holds y ∈ G(S). Besides, as usually, we put G(∅) = ∅.
We say that x ∈ G(N ) is an efficient payoff of G if there are no y ∈ G(N ) such that
yi > xi , i ∈ N. To introduce an analog of the set I(v) we deal with in TU case, we
propose the set I(G) defined below. Put gi = max {xi ∈ R{i} xi ∈ G({i})}, i ∈ N. An
element x = (x1 , . . . , xn ) ∈ G(N ) is said to be individually rational payoff of a game G
if xi ≥ gi , i ∈ N. We are now in position to define the following analog of imputation
set in case of of NTU game G
I(G) = {x ∈ G(N ) x is efficient and individually rational}.
Elements of I(G) are said to be imputations of NTU game G, and I(G) is said to be
imputation set of G. For the next step we introduce domination relation αG , an analog
of binary relation αv
x αG y ⇔ ∃S ∈ 2N \ {∅}[∀i ∈ S(xi < yi )&(yS ∈ G(S))], x, y ∈ I(G) ,
where yS ∈ RS is ordinary restriction of y = (yi )i∈N to S : (yS )i = yi , i ∈ S.
We introduce αG -core C(αG ) (the core C(αG ), for short) of NTU game G as the set
of un-dominated (maximal with respect to the binary relation αG ) elements of I(G)
C(αG ) = {x ∈ I(G) ̸ ∃y ∈ I(G)[ x αG y ]}
Finally, we present an analog of accessibility of the core in NTU case.
Definition 5. The core C(αG ) of NTU cooperative game G is called accessible if
C(αG ) ̸= ∅, and for any x ∈ I(G) \ C(αG ) there exists a convergent sequence of impu-
tations {xr }∞
r=0 of this game such that limr→∞ xr belongs to the core C(αG ), x0 = x,
and xr αG xr+1 for any r ≥ 0.
Passing on to the example of NTU cooperative game with the above-mentioned
“black hole” we consider a three-person NTU cooperative game G with imputation
set I(G) containing some closed subset B that doesn’t intersect the core C(αG ) and
meets the saturation condition (x ∈ B)&(x αG y) ⇒ y ∈ B. So, let N = {1, 2, 3} and
function G is defined by the formulae
∑
3
G({1, 2, 3}) = {x ∈ R{1,2,3} xi ≤ 7},
i=1
G({1, 2}) = {x ∈ R{1,2} x1 + x2 ≤ 5},
G({1, 3}) = {x ∈ R{1,3} x1 + x3 ≤ 5, x1 ≤ 3},
G({2, 3}) = {x ∈ R{2,3} x2 + x3 ≤ 6, x2 ≤ 4},
G({i}) = {xi ∈ R{i} xi ≤ 0}, i = 1, 2, 3 .
650 Valery Vasil’ev
First of all we show that the core C(αG ) of this game is a singleton. In fact, we prove
the formula
C(αG ) = {u} ,
where u = (3, 4, 0). It is clear that imputation u is un-dominated. To prove that any
imputation x ̸= u is dominated we note first that imputation set I(G) of the game G
under consideration is given by the formula
{1,2,3}
∑
I(G) = {x ∈ R+ | xi = 7}.
i∈N
Further, we consider separately two possible cases: 1) x3 = 0, and 2) x3 > 0. For the
first case let us check two subcases 1a) x1 < 3, and 1b) x1 > 3 (note, that x1 = 3 implies
x = u). It is clear that in case 1a) imputation x is dominated by y = (3, 2, 2) via the
coalition S = {1, 3}. As to the case 1b) we have x2 < 4. Hence, imputation y = (1, 4, 2)
dominates x via coalition S = {2, 3}. Further, in case 2) consider 3 subcases: 2a)
x3 ∈ (0, 2], x2 < 4; 2b) x3 ∈ (0, 2], x2 ≥ 4; and 2c) x3 > 2. In the first subcase
imputation x is, obviously, dominated by y = (1, 4 − δ, 2 + δ) with δ > 0 and 4 − δ > x2
via coalition S = {2, 3}. In the second subcase, due to the inequality x3 > 0, we have
x1 < 3 and, since x1 + x3 < 5 we get: imputation (x1 + δ, x2 − 2δ, x3 + δ) dominates
x via coalition S = {1, 3} provided that δ > 0 and δ ≤ min {2, 3 − x1 }. Finally,
in the third subcase we obtain: x is dominated by (x1 + δ, x2 + δ, 2) via S = {1, 2},
where δ = [5 − (x1 + x2 )]/2. Thus, summarizing all the cases considered we confirm
the equality C(αG ) = {(3, 4, 0)}.
To define so-called “black hole” put
B = {x ∈ I(G) x1 ≥ 1, x2 ≥ 2, x3 ≥ 2}.
It is clear that B ∩ C(αG ) = ∅. As B is closed, the only thing we need to prove
non-accessibility of the core C(αG ) is the following implication
(x αG y)&(x ∈ B) ⇒ y ∈ B.
Fix an arbitrary x ∈ B and some y ∈ I(G) such that x αG y. To prove y ∈ B let us
look through three possible situations, which correspond to the two-person dominating
coalitions S = {i, j} : (yi , yj ) ∈ G({i, j}), xi < yi , xj < yj .
1. S = {1, 2}. By definition of domination x by y via coalition S = {1, 2} it holds:
y1 > x1 ≥ 1, y2 > x2 ≥ 2. Further, due to relations y1 + y2 ≤ 5 and y1 + y2 + y3 = 7
we get y3 ≥ 2, which completes the proof of inclusion y ∈ B.
2. S = {1, 3}. Since directly by definition of domination via coalition S = {1, 3}
we get y1 > x1 ≥ 1, y3 > x3 ≥ 2, the only thing we have to prove is inequality
y2 ≥ 2. But by definition of the set G({1, 3}) we get y1 + y3 ≤ 5, and, consequently,
y2 = 7 − (y1 + y3 ) ≥ 2.
3. S = {2, 3}. By definition of domination via S = {2, 3} we have that y2 > x2 ≥
2, y3 > x3 ≥ 2. Further, since y2 + y3 ≤ 6, we get y1 = 7 − (y2 + y3 ) ≥ 1, which
completes the proof of inclusion y ∈ B.
On Strong Accessibility of the Core of TU Cooperative Game 651
Thus, in all possible situations x αG y and x ∈ B imply y ∈ B. Taking account
that B is closed and B ∩ C(αG ) = ∅, we complete the proof of non-accessibility of the
core C(αG ) of 3-player NTU cooperative game under consideration.
Acknowledgements The research was supported in part by Russian Fund for Ba-
sic Research (grant 16 - 06 - 00101). The author thanks Prof. P.Sudhölter for helpful
comments and remarks. Also many thanks to anonymous referees for useful recommen-
dations and suggestions.
References
1. Mashler, M., Peleg, B.: Stable Sets and Stable Points of Set-valued Dynamic Systems with
Applications to Game Theory. SIAM J. Control. Optim. 14, 985–995 (1976)
2. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton
Univ. Press, Princeton, NJ (1944)
3. Owen, G.: Game Theory. W.B.Sounders Company, Philadelphia-London-Toronto (1968)
4. Peleg, B., Sudhölter, P.: Introduction to the Theory of Cooperative Games. Kluwer Aca-
demic Publishers, Dordrecht-Boston-London (2003)
5. Vasi’ev, V.A.: Generalized von Neumann-Morgenstern Solutions and Accessibility of
Cores. Soviet Math. Dokl. 36, 374–378 (1988)
6. Vasil’ev, V.A.: Cores and Generalized NM-solutions for Some Classes of Cooperative
Games. In: Driessen, T.H., van der Laan, G., Vasil’ev, V.A.,Yanovskaya, E.B. (eds.) Rus-
sian Contributions to Game Theory and Equilibrium Theory,pp. 91–150, Springer-Verlag,
Berlin-Heidelberg-New York (2006)
7. Vasil’ev, V.A.: On k-Accessibility of the Core of T U -Cooperative Game. Mathematical
Game Theory and Its Applications. 8(2), 3-27 (2016) (in Russian)
8. Wu, L. S.-Y.: A Dynamic Theory for the Class of Games with Nonempty Cores. SIAM J.
Appl. Math. 32, 328–338 (1977)
Appendix: Outline of the Proof of Accessibility Theorem
For the sake of completeness, we propose a brief outline of the straightforward proof of
Accessibility Theorem, mentioned in the Introduction (for more details, see [6] ). Fix
an arbitrary n-person TU cooperative game v with nonempty core C(αv ). One of the
basic ideas of the proof of core-accessibility is to consider some suitable subsystems of
the set-valued dynamic system3 φv generated by v
φv (x) = αv (x) ∪ {x}, x ∈ I(v) ,
with αv (x) to be a collection of imputations dominating x
αv (x) = {y ∈ I(v) x αv y}, x ∈ I(v).
3
Here and below we apply terms from [1],[4].
652 Valery Vasil’ev
To construct the subsystems of φv required we exploit heavily lower semi-continuity
of the correspondence φv , which follows directly from the definition of domination αv ,
and apply so-called generalized Lyapunov functions [5]. To present their definition in a
more general context useful in the further presentation, consider an arbitrary complete
metric space X with metric d, and remind [1] that by dynamic systems (d.s.) on X we
mean correspondences φ : X → 2X for which φ(x) ̸= ∅ for all x ∈ X. By trajectories
of φ we mean sequences {xr }∞ r=0 such that xr+1 ∈ φ(xr ) for all r = 0, 1, . . . .
∪∞ For correspondence ψ : X → 2X let gr ψ = {(x,
∪ y) ∈ X × X y ∈ ψ(x)}, ψ∗ (x) =
m 1 m+1
m=1 ψ (x) with ψ (x) = ψ(x) and ψ (x) = y∈ψ m (x) ψ(y).
Definition 6. We say that a d.s. φ admits a generalized Lyapunov function if there
exists a bounded function l : gr φ∗ → R such that
(L1) l(x, y) ≥ d(x, y) for all x ∈ X, y ∈ φ(x) ;
(L2) l(x, z) ≥ l(x, y) + l(y, z) for all x ∈ X, y ∈ φ∗ (x), z ∈ φ∗ (y) .
It is worth to note that the existence of a generalized Lyapunov function doesn’t yet
ensure the convergence of any trajectory of a d.s. φ to some element of its set of
endpoints
Eφ = {x ∈ X φ(x) = {x}} .
At the same time, there exists, for lower semi-continuous d.s. φ, a standard way of
formation of subsystems ψ (gr ψ ⊆ gr φ) possessing the property mentioned and
satisfying equality Eψ = Eφ
Proposition 1. Let φ be a lower semi-continuous d.s. on X admitting a generalized
Lyapunov function. Let
ρφ (x) = sup{d(x, y) | y ∈ φ(x)}, x ∈ X .
Then for any δ ∈ (0, 1) all trajectories of the dynamic system
{
{x} , x ∈ Eφ ,
φδ (x) =
{y ∈ φ(x) d(x, y) > δρφ (x)} , x ∈ X \ Eφ ,
converge to elements of Eφ .
So, for the proof of accessibility of the core C(αv ) on the basis of Proposition 1 it
is enough to construct a lower semi-continuous subsystem ψ of d.s.φv that admits a
generalized Lyapunov function and satisfies the relation Eψ = C(αv ). Considering as
the desired subsystem of d.s. φv a dynamic system ψl of the form
ψl (x) = {y ∈ αv (x) l(x, y) > d(x, y)} ∪ {x}, x ∈ I(v) ,
with l to be some real-valued function on I(v) × I(v), one can obtain the following
sufficient condition of accessibility (see, e.g., [6]).
On Strong Accessibility of the Core of TU Cooperative Game 653
Theorem 3. Suppose there exists a bounded lower semi-continuous with respect to the
first argument function l : I(v) × I(v) → R+ such that
l(x, z) ≥ l(x, y) + l(y, z), x ∈ I(v), y ∈ φv∗ (x), z ∈ φv∗ (y) .
If, in addition, function l meets the requirement
∀ x ∈ I(v) \ C(αv ) ∃ y ∈ αv (x) [ l(x, y) > d(x, y)] ,
then the core C(αv ) is accessible.
Below, we apply the following useful corollary of Theorem 3.
Corollary 1. If there exists a continuous function u : I(v) → R+ such that
∀ x ∈ I(v) \ C(αv ) ∃ y ∈ αv (x) [ u(x) − u(y) > d(x, y)] ,
then the core C(αv ) of TU cooperative game v is accessible.
In order to apply Corollary 1 we put u = uv , where
uv (x) = 4nd(x, C(αv )), x ∈ I(v) ,
with d(x, C(αv )) to be the distance from x to the core C(αv ) in Euclidean norm ||x||2 =
( )
∑ 2 1/2
xi . To complete an outline we will only sketch the proof of the main lemma,
N
which plays a crucial role in justification of Accessibility Theorem.
Lemma 1. Function uv satisfies condition
∀x ∈ I(v) \ C(αv )∃y ∈ αv (x)[uv (x) − uv (y) > ||x − y||2 ] . (5)
Sketch of the proof of Lemma 1. First of all we may assume w.l.g. that v({i}) = 0
for all i ∈ N, and 0 ≤ v(S) ≤ v(N ) for all S ⊆ N. It follows directly from the definition
of C(αv ) that condition v(S) ≤ v(N ), S ⊆ N, implies that the core of 0-normalized
TU cooperative game v is given by the formula
C(αv ) = {x ∈ RN
+ x(N ) = v(N ), x(S) ≥ v(S), S ⊆ N} .
In order to prove (5) let us fix an arbitrary imputation x ∈ I(v) \ C(αv ). We will show
that there exists z ∈ I(v) satisfying inequality
uv (x) − uv (z) > ||x − z||2 (6)
and the following weak domination requirement
x α̃v z , (7)
where
x α̃v z ⇔ ∃S [(x(S) < z(S) ≤ v(S))&(xi ≤ zi , i ∈ S)] .
654 Valery Vasil’ev
If x α̃v z, then every neighborhood of z contains an element y ∈ I(v) , which dominates
x w.r.t. αv , and the inequality (6) , by continuity of uv , holds in some neighborhood
of z. Therefore the existence of z, satisfying (6) and (7) , proves the lemma .
In order to construct z, mentioned above, consider the imputation u ∈ C(αv ),
closest to x w.r.t. the norm || · ||2 . It is not very hard to verify that there exists a
coalition S ⊆ N such that x(S) < u(S) = v(S). Put
S1 = {i ∈ S xi < ui } ,
S2 = {i ∈ N \ S xi > ui } ,
T1 = {i ∈ S xi ≥ ui } ,
T2 = {i ∈ N \ S xi ≤ ui } .
If T1+ = {i ∈ T1 | xi > ui } = ∅ , then u may be used as the sought for imputation. If
T1+ ̸= ∅, then setting
e(x, S) = v(S) − x(S) ,
qj = e(x, S)/ u(Sj ) − x(Sj ) , j = 1, 2 ,
we define z ∈ RN by the formula
xi + q1 (ui − xi ) , i ∈ S1 ,
zi = xi + q2 (ui − xi ) , i ∈ S2 ,
xi , i ∈ T1 ∪ T2 .
Since q1 , q2 ∈ (0, 1], vector z clearly belongs to I(v). Taking account that S1 ̸= ∅ and
z(S) = x(S) + e(x, S) = v(S), xi = zi , i ∈ T1 ,
we have
x(S) < z(S) ≤ v(S), xi ≤ zi , i ∈ S .
By definition of the weak domination α̃v , these inequalities imply that imputation x is
α̃v -dominated by z via coalition S = S1 ∪ T1 .
In order to check the inequality (6), note that
√
||x − z||2 ≤ 2 e(x, S) , (8)
and the lower bound of the difference ||x − u||2 − ||z − u||2 has the following form
||x − u||2 − ||z − u||2 ≥ (Q1 + Q2 )/2||x − u||2 , (9)
where
∑
Qj = (2qj − qj2 ) · (xi − ui )2 , j = 1, 2 .
i∈Sj
On Strong Accessibility of the Core of TU Cooperative Game 655
Estimating denominator in the right hand side of (9) we have for the first step
∑
(xi − ui )2 ≤ (u(Sj ) − x(Sj ))2 , j = 1, 2 . (10)
i∈Tj
By Cauchy-Schwartz inequality , from (10) we obtain
∑ ∑
(xi − ui )2 ≤ |Sj | · (xi − ui )2 , j = 1, 2 .
i∈Tj i∈Sj
At last , by definition of Qj , we have
1/2
√ ∑
2
/
||x − u||2 ≤ n Qj (2qj − qj2 ) . (11)
j=1
So, applying definitions of q1 , q2 , and combining inequalities (8),(9) and (11), by lengthy,
but elementary calculations we obtain the sought for relationship
uv (x) − uv (z) ≥ 2e(x, S) > ||x − z||2 ,
which completes the sketch of the proof of Lemma 1. ⊓ ⊔
To conclude the outline of the proof of Theorem 1 we have to exploit some properties
of the dynamic system
{
{x} , x ∈ C(αv ) ,
φvδ (x) =
{y ∈ φv (x) uv (x) − uv (y) > ||x − y||2 > δρv (x)} , x ∈
/ C(αv ) ,
where δ is an arbitrary number from the interval (0, 1) and
ρv (x) = sup{||x − y||2 y ∈ φv (x), uv (x) − uv (y) > ||x − y||2 }, x ∈
/ C(αv ) .
Since by Lemma 1 the dynamic system φvδ admits Lyapunov function, and φv is lower
semi-continuous dynamic system, it is not very hard to verify (like in [6], for instance)
that all the trajectories of the system φvδ converge to the imputations from C(αv ). ⊓⊔