Процессы управления и устойчивость

будут давать постоянное число. При этом эксцессы дополняющих ко-

алиций в сумме дают 0, следовательно, приравниваемые минималь-

ные эксцессы отрицательны.

Пусть у нас приравнивается k эксцессов по единичным коалициям

и один эксцесс по множеству оставшихся игроков:

¯

e(x, i

s

) = 2x

i

s

− v(N ) + v(N \i

s

),

¯

e(x, N \ ∪ i

s

) = 2x(N \ ∪ i

s

) − v(N \ ∪ i

s

) − v(N ) + v( ∪ i

s

).

(1)

Решая систему уравнений (1), получаем

p =

v(N )(1 − k)

k + 1

+

v(N \i

s

)

k + 1

−

v(N \ ∪ i

s

)

k + 1

+

v(∪i

s

)

k + 1

< 0.

Следовательно,

v(N ) >

v(N \i

s

) − v(N \ ∪ i

s

) + v(∪i

s

)

|1 − k|

, k = 1.

Таким образом,

x

i

s

=

v(N )

k + 1

+

v(N \i

s

) − v(N \ ∪ i

s

) + v(∪i

s

) − (k + 1)v(N \i

s

)

2(k + 1)

,

s = 1, k, k = 2, n − 1.

Остальные величины x

j

, j ∈ N \ ∪ i

s

будут найдены из равен-

ства эксцессов, сумма которых будет постоянной при фиксирован-

ных x

i

s

, s = 1, k. В этом случае в выражении для x

j

, j ∈ N \ ∪ i

s

,

коэффициент перед v(N) будет изменяться, как и остальные коэф-

фициенты, и не будет единой формулы для вычисления x

i

, i = 1, n.

Единая формула для всех компонент вектора выигрышей SM-ядра

будет в том случае, если k = n − 1, то есть являются минималь-

ными и приравниваются все эксцессы одиночных коалиций. Тогда

аналитическая формула для вычисления SM-ядра имеет вид

µ

∗

i

=

v(N )

n

+

j=i

v(N \j)

2n

−

(n − 1)v(N \i)

2n

.

(2)

Можно сравнить (2) с аналитической формулой для компонент

вектора Шепли

607

ϕ

i

=

S i

(s − 1)!(n − s)!

n!

(v(S) − v(S\i)).

(3)

Итак, вектор Шепли и SM-ядро в общем случае не совпадают. Срав-

нив формулы (2) и (3) для n = 3, можно убедиться, что исключение

составляет случай, когда n = 3. Приведем контрпример.

Пример 2. "Рынок перчаток при n = 4". Пусть игрок 1 владеет

правой перчаткой, у игроков 2, 3, 4 имеется по одной левой перчатке.

Тогда v(1) = v(2) = v(3) = v(4) = v(23) = v(24) = v(34) = v(234) = 0,

v(12) = v(13) = v(14) = v(123) = v(124) = v(134) = v(1234) = 1.

Вектор Шепли: (

3

4

,

1

12

,

1

12

,

1

12

),

SM-ядро: (

7

10

,

1

10

,

1

10

,

1

10

).

Замечание 1. В случае, когда k = 1, получим равенство экс-

цессов дополняющих коалиций, тогда все эксцессы равны 0, чего не

может быть.

Замечание 2. Если вместо равенства эксцессов от одиночных

коалиций рассмотреть равенство дополняющих коалиций, т.е. |S| =

n − 1, то получим такое же решение, только с другим неравенством:

v(N ) <

v(N \i

s

) − v(N \ ∪ i

s

) + v(∪i

s

)

|1 − k|

, k = 1.

Литература

1. Печерский С.Л., Яновская Е.Б. Кооперативные игры: решения и

аксиомы. СПб.: Изд-во ЕУСПб, 2004. 460 с.

2. P. Sudholter. The modified nucleolus: Properties and axiomatizations

// International Journal of Game Theory. № 26, 1997. P. 147–182.

3. Четвертаков В.С. Анализ модифицированного N-ядра. Диплом-

ная работа, выполнена на ф-те ПМ–ПУ СПбГУ (рукопись), 2004.

608

Старцев И.А.

Санкт-Петербургский экономико-математический институт РАН

Эгалитарные значения игр с неделимыми

выигрышами и понятие разрушающего игрока

Рекомендовано к публикации профессором Яновской Е.Б.

Введение. Данная статья развивает идеи работы ван ден Бринка

[1] и распространяет их на пространство игр с неделимыми выигры-

шами (далее НДМ-игры). Нами определены три значения НДМ-игр,

по-разному отражающие принцип эгалитаризма (равного распреде-

ления результатов кооперации); на базе понятия разрушающего иг-

рока, т.е. игрока, присутствие которого в коалиции обнуляет е¨е силу

(ценность), определены две аксиомы разрушающего игрока, путем

комбинирования которых с другими аксиомами значений НДМ-игр,

получены шесть аксиоматических характеризаций рассмотренных в

работе эгалитарных значений НДМ-игр.

1. Основные определения. Пусть N – произвольное конечное

множество игроков. Игрой с неделимыми выигрышами называется

упорядоченная тройка (N, v, U), где: U – множество предметов, под-

лежащих распределению среди игроков; v : 2

N

→ 2

U

– характери-

стическая функция, при этом v(S) ⊆ U для любой коалиции S ⊆ N и

v(∅) = ∅. Пусть G

N

(U) – пространство НДМ-игр с множеством игро-

ков N . Значением на пространстве G

N

(U) называется отображение

f : G

N

(U) → 2

U n

, ставящее каждой НДМ-игре (N, v) ∈ G

N

(U) в

соответствие вектор-функцию f (N, v, U) = (f

i

(N, v, U))

i∈N

⊆ 2

U n

.

Рассмотрим классические аксиомы значений НДМ-игр, анало-

гичные соответствующим аксиомам значений ТП-игр. Пусть f –

значение на пространстве G

N

(U). Будем говорить, что значение

f удовлетворяет эффективности (Eff ), если для каждой игры

(N, v) ∈ G

N

(U) верно

i∈N

f

i

(N, v) = v(N ); глобальной эффек-

тивности (GEff ), если для каждой игры (N, v) ∈ G

N

(U) верно

i∈N

f

i

(N, v) =

S⊆N

v(S); симметрии (Sym), если для каждой

игры (N, v) ∈ G

N

(U) верно f

i

(N, v) = f

j

(N, v) для любой пары сим-

метричных в игре (N, v) игроков i, j ∈ N (т.е. игроков, для которых

выполняется равенство v(S ∪{i}) = v(S ∪{j}) для всех коалиций S ⊆

N \{i, j}); аддитивности (Add), если f

i

(N, v∪w) = f

i

(N, v)∪f

i

(N, w)

для всех игроков i, j ∈ N , и всех пар игр (N, v), (N, w) ∈ G

N

(U),

609

где игра (N, v ∪ w) ∈ G

N

(U) определяется следующим образом

(v ∪ w)(S)

def

= v(S) ∪ w(S) для всех S ⊆ N.

Также нам понадобится ослабленный вариант аксиомы симмет-

рии, который мы по аналогии с Малавски [2] будем использовать в

теореме 1. В [2] отмечено, что в аксиоматизациях Шепли [4] и Янга

[6] вектора Шепли аксиому симметрии можно ослабить до аксиомы

симметрии взаимозависимых игроков, введ¨енной Новаком и Раджи-

ком в [3].

Игроки i, j ∈ N называются взаимозависимыми в НДМ-игре

(N, v) ∈ G

N

(U), если v(S \ {i}) = v(S \ {j}) = v(S \ {i, j}) для всех ко-

алиций T ⊆ N , содержащих игроков i, j. Будем говорить, что значе-

ние f на пространстве НДМ-игр G

N

(U) удовлетворяет аксиоме сим-

метрии взаимозависимых игроков (ETD), если f

i

(N, v) = f

j

(N, v)

для каждой пары взаимозависимых в игре (N, v) игроков i, j ∈ N .

Для НДМ-игр не существует [5] значения, удовлетворяющего ак-

сиомам Sym, Eff и назначающего каждый элемент из U не более чем

одному игроку. Поэтому разумно рассматривать значения НДМ-игр,

которые распределяли бы все элементы из U поровну среди игроков

из N . В этой работе будем исследовать три таких значения НДМ-

игр, введ¨енных автором:

• сильного эгалитаризма HE

def

= v(N );

• глобального сильного эгалитаризма HEG

def

=

S⊆N

v(S);

• глобального компромиссного эгалитаризма CEG

def

=

S⊆N

S i

v(S).

2. Понятие разрушающего игрока и аксиомы разруша-

ющего игрока. Игрок i ∈ N в игре (N, v) ∈ G

N

(U) называется

разрушающим, если его присутствие в коалиции обнуляет е¨е силу

(ценность), т.е. верно v(S ∪ {i}) = ∅ для всех S ⊆ N .

По аналогии с ТП-играми будем говорить, что произвольное зна-

чение f на пространстве G

N

(U) удовлетворяет аксиоме разрушаю-

щего игрока (ZPP), если f

i

(N, v) = ∅ для всех НДМ-игр (N, v) и

всех разрушающих в ней игроков i.

Отметим, что если значение f на пространстве G

N

(U) удовлетво-

ряет Eff, то оно удовлетворяет ZPP.

Пусть в некоторой игре (N, v) некоторый игрок i является раз-

рушающим. Аксиома ZPP предписывает назначить такому игроку

610

нулевой выигрыш f

i

(N, v) = ∅. Однако, разрушающий игрок может

использовать сво¨е ”вредное” для других (неразрушающих) игроков

свойство и ”шантажировать” их и их коалиции своим участием в

этих коалициях. Поэтому неразрушающие игроки могут согласить-

ся заплатить откуп всем разрушающим игрокам, чтобы те не участ-

вовали в ”большой” коалиции. Величина этого откупа может быть

произвольной, но должна отражать идеи справедливости и рацио-

нальности.

Далее, для удобства, обозначим через Z(N, v) – множество всех

разрушающих игроков в игре (N, v). Определим размер откупа, как

множество всех тех общих элементов из U, которые назначаются

неразрушающим игрокам:

R(N, v)

def

=

j∈N \Z(N,v)

f

j

(N, v).

Только при таком определении размера откупа он будет равным

для всех неразрушающих игроков, и при этом разрушающие игро-

ки должны будут удовлетвориться им, так как не смогут потребо-

вать большего, при сохранении условия равенства размера откупа

для всех неразрушающих игроков, а также в силу того, что из сооб-

ражений справедливости выигрыш разрушающего игрока не может

превышать выигрыш любого неразрушающего, ибо в этом случае

неразрушающий игрок не заинтересован быть таковым (не разру-

шающим).

На основе этой идеи мы получили модификацию аксиомы раз-

рушающего игрока. Будем говорить, что произвольное значение f

на пространстве G

N

(U) удовлетворяет аксиоме разрушающего иг-

рока с откупом (ZPPwR), если f

i

(N, v) = R(N, v) для всех игр

(N, v) ∈ G

N

(U) и всех разрушающих в ней игроков i ∈ Z(N, v).

Влияние такого перехода от идеи справедливости к идеи рацио-

нальности можно будет увидеть в теореме 1. При этом выигрыши

всех игроков увеличатся. Стоит отметить, что в этом случае игроки

должны будут поделить поровну среди всех игроков даже те элемен-

ты, которые не являются достижимыми некоторыми игроками, что,

очевидно, сомнительно с точки зрения справедливости.

3. Аксиоматизации эгалитарных значений. Согласно [5],

для каждой НДМ-игры (N, v) ∈ G

N

(U) существует е¨е разложение

в виде объединения:

611

v(S) =

∅=T ⊆N

E

v(T )

T

(S) для всех S ⊆ N,

(1)

где игра (N, E

A

T

) определяется по правилу E

A

T

(S)

def

=

A, при S = T ;

∅, при S = T.

Теперь можно сформулировать и доказать основной результат

этой статьи.

Теорема 1. Для каждого из следующих наборов аксиом сущест-

вует единственное значение f : G

N

(U) → (2

U

)

n

, ему удовлетворя-

ющее:

1. Eff,

Sym или ETD,

Add,

2. GEff,

ZPPwR,

Sym или ETD,

Add,

3. GEff,

ZPP,

Sym или ETD,

Add

это HE, HEG и CEG-значение соответственно.

Доказательство. Очевидно, что эгалитарные значения удовле-

творяют условиям теоремы. Покажем единственность HE-значения.

Для всех игроков i ∈ N верна следующая цепочка равенств:

f

i

(N, v)

(1), Add

=

T ⊆N

f

i

(N, E

v(T )

T

) = f

i

(N, E

v(N )

N

) ∪

T ⊂N

f

i

(N, E

v(T )

T

) =

Z(N,E

v(T )

T

)=∅

=

f

i

(N, E

v(N )

N

)

Sym, Ef f

=

E

v(N )

N

(N )

(1)

= v(N ) = HE

i

(N, v).

Покажем единственность HEG-значения. Рассмотрим произволь-

ную коалицию T ⊆ N и v(T )-сужение элементарной игры (N, E

v(T )

T

).

В этой игре Z(N, E

v(T )

T

) = N \ T , игроки k ∈ T являются симмет-

ричными. Отсюда для всех игроков i ∈ N \ T и всех k ∈ T вер-

на следующая цепочка равенств: f

i

(N, E

v(T )

T

)

ZP P wR

=

R(N, E

v(T )

T

) =

j∈T

f

j

(N, E

v(T )

T

) = f

k

(N, E

v(T )

T

)

GEf f

=

v(T ). Теперь для всех иг-

роков i ∈ N верна следующая цепочка равенств: f

i

(N, v)

(1), Add

=

T ⊆N

f

i

(N, E

v(T )

T

)

GEf f

=

∅=T ⊆N

v(T ) = HEG

i

(N, v).

Покажем единственность CEG-значения. Для всех игроков i ∈ N

верна следующая цепочка равенств:

612

f

i

(N, v)

(1), Add

=

T ⊆N, T i

f

i

(N, E

v(T )

T

) ∪

T ⊆N \{i}

f

i

(N, E

v(T )

T

)

ZP P

=

=

T ⊆N, T i

f

i

(N, E

v(T )

T

)

Sym, GEf f

=

T ⊆N, T i

E

v(T )

T

(T )

(1)

= CEG

i

(N, v).

Для тр¨ех случаев с аксиомой ETD доказательство аналогично.

В тех местах, где используется аксиома Sym, игроки являются не

только симметричными, но и взаимозависимыми, а именно, в играх

(N, E

v(T )

T

) при T ⊆ N . Логическая независимость аксиом в условии

теоремы тривиальна. Теорема доказана.

Замечание. Учитывая связь между характеризациями эгали-

тарного значения и вектора Шепли в [1], и опирающуюся на замену

аксиом, связанных с понятием нулевого игрока, т.е. игрока, вклад

v(S ∪ {i}) − v(S) которого в любую коалицию равен v({i}), на аксио-

мы, связанные с понятием разрушающего игрока, необходимо найти

значение, которое удовлетворяло бы аксиоме нулевого игрока (т.е.

f

i

(N, v) = ∅ для всех нулевых игроков i в игре (N, v)) и аксиомам

Sym, Eff, Add. Однако, такого значения НДМ-игр не существует [5].

Литература

1. Brink R. Null or Zero Players: The Difference between the Shapley

value and the Egalitarian Solution // Tinbergen Institute Discussion

Paper, 2004. № 127/1.

2. Malawski M. Equal treatment, symmetry and Banzhaf value

axiomatizations // Int. J. Game Theory, 2002. № 31. P. 47–67.

3. Nowak A., Radzik T. On axiomatizations of the weighted Shapley

values // Games and Economic Behavior, 1995. № 8. P. 389–405.

4. Shapley L.S. A value for n-person games // Annals of Mathematics

Studies / Ed. by H.W.Kuhn, A.W.Tucker. Princeton, New Jersey:

Princeton University Press, 1953. № 28. P. 307–317.

5. Sun H. Contributions to set game theory: Ph.D. thesis. The University

of Twente, Enschede, The Netherlands. 2003.

6. Young H.P. Monotonic solutions of cooperative games // Int. J. Game

Theory, 1985. № 14. P. 65–72.

613

Стенин П.Н.

Санкт-Петербургский государственный университет

К обоснованию технического анализа

в процессе принятия решения

Рекомендовано к публикации профессором Прасоловым А.В.

Современные методы прогнозирования в экономике часто осно-

ваны на использовании информации о динамике социально-экономи-

ческих показателей. Такая информация накапливается и хранится в

специальных базах данных. Особенностью этих баз данных явля-

ется то, что вектор показателей имеет огромную размерность, не

позволяющую устанавливать зависимости между показателями для

всей системы целиком. Поэтому встает проблема выбора подсисте-

мы показателей по некоторым правилам автоматически, то есть, без

участия экспертов или руководителей. Для решения этой проблемы

существует ряд методов, каждый из которых имеет свои преимуще-

ства и недостатки. Например, одним из наиболее известных методов

является метод пошагового отбора наиболее информативных пере-

менных, основанный на использовании коэффициента детерминации

R

2

. Его суть заключается в пошаговом добавлении переменных до

тех пор, пока увеличивается соответствующий (скорректированный)

коэффициент детерминации R

2

. Однако даже увеличение скоррек-

тированного коэффициента детерминации R

2

при введении в модель

новой объясняющей переменной не всегда означает улучшение каче-

ства регрессионной модели (для этого нужно выполнение еще ряда

условий).

В данной статье рассматривается построение альтернативного

алгоритма выбора наиболее существенных объясняющих показате-

лей (далее будем называть их ассоциированными показателями), ко-

торый может применяться как отдельно, так и в совокупности с дру-

гими методами для получения более надежного результата.

Рассмотрим векторный временной ряд X(k) = {x

i

(k)}

k=1,N

i=1,n

, ко-

торый представляет собой данные о состоянии n показателей, изме-

ренных N раз в определенные промежутки времени. Предположим,

что нужно выбрать к показателю с индексом i

0

набор ассоциирован-

ных показателей.

614

Для выбранного показателя строим линейную авторегрессию в

виде

x

i

0

(k + 1) = ax

i

0

(k) + b,

а в качестве критерия оптимальности рассматриваем сумму квадра-

тов отклонений модели от реальных данных:

S(a, b) =

N −1

k=1

x

i

0

(k + 1) − ax

i

0

(k) − b

2

,

S

0

= S(a, b).

Таким образом, S

0

характеризует качество модели.

На втором этапе добавляем в авторегрессионную модель один из

оставшихся показателей:

S

1

(a

0

, a

1

, b, j) =

N −1

k=1

x

i

0

(k + 1) − a

0

x

i

0

(k) − a

1

x

j

(k) − b

2

,

S

1

(a

0

, a

1

, b , j) = min

a

0

,a

1

,b

S

1

(a

0

, a

1

, b, j) = S

1

(j),

S

1

(j ) = min

j

S

1

(j) ⇒ i

1

= j ,

т. е. из всех оставшихся показателей выбираем тот (с номером i

1

),

который дает наилучшее качество модели.

Далее, добавляем второй показатель:

S

2

(a

0

, a

1

, a

2

, b, j) =

N −1

k=1

x

i

0

(k +1) − a

0

x

i

0

(k) − a

1

x

i

1

(k) − a

2

x

j

(k) − b

2

,

S

2

(a

0

, a

1

, a

2

, b , j) =

min

a

0

,a

1

,a

2

,b

S

1

(a

0

, a

1

, a

2

, b, j) = S

2

(j),

S

2

(j ) = min

j

S

2

(j) ⇒ i

2

= j .

Продолжая действовать аналогичным образом, получаем выра-

жение для m-го члена:

615

S

m

(a

0

, . . . , a

m

, b, j) =

N −1

k=1

x

i

0

(k + 1) − a

0

x

i

0

(k)−

−a

1

x

i

1

(k) − a

2

x

i

2

(k) · · · − a

m

x

j

(k) − b

2

,

S

m

(a

0

, . . . , a

m

, b , j) =

min

a

0

,...,a

m

,b

S

1

(a

0

, . . . , a

m

, b, j) = S

m

(j),

S

m

(j ) = min

j

S

m

(j) ⇒ i

m

= j .

Теорема. Построенная последовательность S

0

, . . . , S

m

убывает

и конечна.

Доказательство. Очевидно, что S

0

≥ . . . ≥ S

m

, так как модель

с одним показателем есть частный случай модели с m показателями,

в которой коэффициенты при соответствующих членах равны нулю.

Конечна она в силу того, что количество показателей m есть конеч-

ное число.

Как было показано выше, наилучшее качество модели достигает-

ся при использовании всех показателей, но, так как целью является

уменьшение размерности рассматриваемой системы, надо добавить в

алгоритм критерий остановки. Простейшим вариантом является си-

туация, когда известно точное количество требуемых ассоциируемых

показателей (например, когда поставлена задача найти 4 ассоцииро-

ванных показателя к выбранному главному). Тогда останавливаем

алгоритм при достижении этого значения. Если же не задано точ-

ное количество ассоциированных показателей, то введем следующий

критерий остановки.

Построим последовательность D

1

, . . . , D

m

следующим образом:

D

1

= a

(1)

0

x

i

0

(k) + a

(1)

1

x

i

1

(k) + b

(1)

,

D

2

= a

(2)

0

x

i

0

(k) + a

(2)

1

x

i

1

(k) + a

(2)

2

x

i

2

(k) + b

(2)

−

−a

(1)

0

x

i

0

(k) + a

(1)

1

x

i

1

(k) + b

(1)

,

· · ·

616

D

m

= a

(m)

0

x

i

0

(k) + a

(m)

1

x

i

1

(k) + . . . + a

(m)

m

x

i

m

(k) + b

(m)

−

−a

(m−1)

0

x

i

0

(k) + a

(m−1)

1

x

i

1

(k) + . . . + a

(m−1)

m−1

x

i

m−1

(k) + b

(m−1)

.

Тогда алгоритм выбора набора ассоциированных показателей к глав-

ному показателю состоит в следующем: добавляем по одному пока-

зателю к модели до тех пор, пока D

i

< S

i

, или, другими словами,

пока добавление в модель нового члена не перестанет приводить к

значимому улучшению качества модели. Это условие обязательно

выполняется на некотором шаге в силу построения D

i

и S

i

.

Данный алгоритм реализован на ЭВМ и анализ результатов его

работы планируется опубликовать в отдельной статье. Таким обра-

зом, в данной работе рассмотрен алгоритм выбора наиболее суще-

ственных объясняющих переменных в авторегрессионной модели. С

его помощью, к одному выбранному для прогнозирования показа-

телю, из большого набора данных выделяется часть показателей, в

совокупности с которыми и рассматривается динамика выбранного

показателя и в дальнейшем строится разностное уравнение для про-

гнозирования.

Литература

1. Крамер Н.Ш., Путко Б.А. Эконометрика. М.: Изд-во Юнити,

2005. 155 с.

2. George E.I. The variable selection problem. Austin: University of

Texas, 2000. P. 1–12.

3. Demirer R., Eksioglu B. Subset selection in multiple linear regression:

a new mathematical programming approach // School of business

working paper № 284, Lawrence: University of Kansas, 1998. P. 1–23.

4. Thompson M.L. Selection of variables in multiple regression: Part I.

A review and evaluation // International Statistical Review, 1978.

P. 1–46.

617

Строкан П.В.

Санкт-Петербургский государственный университет

Информационные равновесия

в коммуникационных системах

Рекомендовано к публикации профессором Петросяном Л.А.

Введение. В данной работе рассмотрено усовершенствование

стандартной модели знания, введённой M. Bacharach [1, 2]. Модель

описывает процесс коммуникации игроков и, как результат, достиже-

ние информационного равновесия.

Предположим, что есть некоторое конечное множество игроков,

конечное множество элементарных событий (состояний), а также из-

вестна вероятность возникновения каждого из элементарных собы-

тий. Каждому элементарному событию игрока ставится в соответ-

ствие некое множество элементарных событий, в котором игрок не

может различать элементы. Эти множества называются информаци-

онными множествами игрока. На множестве игроков задан протокол

(правило), по которому происходит процесс взаимодействия.

Происходит некоторое событие Х, состоящее из множества элемен-

тарных событий. Далее игра идёт во времени, первый игрок (опреде-

ляется протоколом) некоторым образом реагирует на событие Х и

посылает сообщение о своей реакции второму игроку (определяется

протоколом). Второй игрок, получив сообщение, перестраивает своё

информационное множество, в соответствии с полученной информа-

цией, и строит свою реакцию на событие и посылает сообщение сле-

дующему игроку и т.д.

Через несколько шагов наступает момент, когда информацион-

ные множества игроков перестают изменяться при приёме сообще-

ний, это и есть тот момент, когда информационное равновесие до-

стигнуто.

Автором построена компьютерная модель данного коммуникаци-

онного процесса. Программа показывает данные игрока (информа-

ционные множества, реакции на событие, сообщения) на каждом ша-

ге игры и вычисляет равновесие.

Алгоритм реализован в виде динамической библиотеки (.NET),

что позволяет использовать её в качестве модуля для Windows- и

618

Web-приложений. Для реализации программы использовалась среда

VC# 7.1.

Модель. N – конечное множество игроков, i – игрок.

Пространство состояний – конечное непустое множество, элемен-

ты которого будем называть состояниями. Обозначим пространство

состояний через Ω . Элементы Ω будем обозначать ω .

Событие – это подмножество пространства состояний. Будем го-

ворить, что событие F произошло в состоянии ω, если ω ∈ F .

Структура доверия – это пара < Ω, (B

i

)

i∈N

>, где Ω – простран-

ство состояний, а (B

i

)

i∈N

– класс операторов доверия. Доверие опре-

деляет часть события F , которой игрок i доверяет.

Событие F называется несомненным событием игрока i, если ω ∈

T ⊆ B

i

T .

Структура уверенности – это тройка < Ω, (A

i

), (B

i

) >, где

< Ω, (B

i

) > – структура доверия, а (A

i

) — класс операторов уве-

ренности, удовлетворяющих аксиоме:

B

i

F ∪ B

i

(Ω \ B

i

F ) ⊆ A

i

F.

Аксиома показывает, уверенность игрока i в событии F . Будем

говорить, что игрок i самоуверен в событии F , если F ⊆ A

i

F .

Информационная структура – это класс отображений P

i

, кото-

рые каждому состоянию ω ставят в соответствие пересечение всех

несомненных событий T (ω ∈ T ):

P

i

(ω) = ∩

T ∈2

Ω

{T |ω ∈ T ⊆ B

i

T }.

Если события T , для которого выполняется ω ∈ T ⊆ B

i

T , не

существует, то множество P

i

(ω) будем считать неопределённым.

µ(ω) > 0 – вероятность появления события ω ∈ Ω. Определим

последствие q

i

как отображение из 2

Ω

× Ω в [0, 1], которое каждой

паре (X, ω) ставит в соответствие µ(X ∩ A

i

(X)|P

i

(ω)). Для каждого

q

i

определим [q

i

] = {ω ∈ Ω|q

i

(X, ω) = q

i

}, q

i

– последствие события

X для игрока i в состоянии ω, если ω ∈ [q

i

].

Функция принятия решения игрока i – отображение из Ω в R.

Будем говорить, что функция принятия решения удовлетворяет

принципу деловой стабильности, если для двух непересекающихся

событий S и T таких, что если f

i

(S) = f

i

(T ) = d, то f

i

(S ∪ T ) = d.

619

Функция принятия решения выпуклая, если для двух непересекаю-

щихся событий S и T существуют числа a, b ∈ (0, 1) такие, что

f

i

(S ∪ T ) = af

i

(S) + bf

i

(T ), a + b = 1.

Если f

i

сузить до вероятности последствия:

f

i

(F ) = µ(X ∩ A

i

(X)|F ), µ(F ) > 0.

Игроки общаются путем обмена сообщениями, получатель и от-

правитель сообщения определяются протоколом.

Протокол — это отображение из множества целых неотрицатель-

ных чисел в N × N , т.е. каждому неотрицательному числу t ставится

в соответствие пара (s(t), r(t)). В данном случае, t – время, s(t) и r(t)

– это отправитель сообщения и получатель соответственно.

Определение. Коммуникационный процесс π пересмотра зна-

чений

функции

принятия

решения

(f

i

)

i∈N

–

это

тройка

< P r, (Q

t

i

)

(i,t)∈N ×Z

+

, (f

i

)

i∈N

>, где P r(t) = (s(t), r(t)) – это прото-

кол, где для любого t, r(t) = s(t + 1). Коммуникационный процесс

периодичен.

Q

t

i

определим индуктивно:

Q

0

i

= P

i

,

Предположим, что Q

t

i

определено.

Через d

t

i

(ω) обозначим значение f

i

(Q

t

i

(ω))

W

t

i

– это отображение, которое ставит в соответствие каждому

ω событие W

t

i

(ω), состоящее из таких состояний ξ, для которых

d

t

i

(ξ) = d

t

i

(ω).

B

t

i

– это оператор доверия, который определяется так:

B

t

i

(F ) = {ω ∈ Ω|Q

t

i

(ω) ⊆ F }.

A

t

i

определяется следующим образом:

A

t

i

(F ) = B

t

i

(F ) ∪ B

t

i

(Ω \ B

t

i

(F )).

Игрок-отправитель i = r(t) отправляет сообщение B

t

i

(W

t

i

(ω)) в

момент времени t + 1, когда ω ∈ B

t

i

(W

t

i

(ω)), и не отправляет в про-

тивном случае.

Q

t+1

i

вычисляется так:

620

1. Если игрок i не является получателем сообщения в момент вре-

мени t + 1 , то

Q

t+1

i

= Q

t

i

.

2. Если игрок i – получатель, то

Q

t+1

i

= Q

t

i

∩ B

t

i

(W

t

i

(ω)).

Процесс

коммуникации

прерывается

в

состоянии

ω,

если

ω /

∈ B

t

i

(W

t

i

(ω)).

Равновесие. Семейство Q

t

i

(ω), t = 0, 1, . . . – это убывающая по-

следовательность, поэтому равновесие существует в каждом состоя-

нии, в котором процесс коммуникации непрерывен. Таким образом,

существует достаточно большое T , для которого t > T, Q

t

i

= Q

T

i

,

т.к. Ω – конечное.

Пример. Игроки (A, B, C) обмениваются сообщениями согласно

протоколу: A → B → C → A.

Функция принятия решения у всех игроков одинакова и удовле-

творяет принципу деловой стабильности.

Ω = {ω

1

, . . . , ω

9

},

µ(ω) =

1

9

.

Информационные множества игроков:

Игрок A :

Q

0

A

(ω

1

) = Q

0

A

(ω

3

) = {ω

1

, ω

2

, ω

3

}; Q

0

A

(ω

2

) = {ω

2

};

Q

0

A

(ω

4

) = Q

0

A

(ω

8

) = {ω

4

, ω

5

, ω

7

, ω

8

}; Q

0

A

(ω

5

) = Q

0

A

(ω

7

) = {ω

5

, ω

7

};

Q

0

A

(ω

6

) = Q

0

A

(ω

9

) = {ω

6

, ω

9

}.

Игрок B :

Q

0

B

(ω

1

) = Q

0

B

(ω

4

) = Q

0

B

(ω

7

) = {ω

1

, ω

4

, ω

7

};

Q

0

B

(ω

2

) = {ω

2

}; Q

0

B

(ω

5

) = Q

0

B

(ω

8

) = {ω

5

, ω

8

};

Q

0

B

(ω

3

) = Q

0

B

(ω

6

) = Q

0

B

(ω

9

) = {ω

3

, ω

6

, ω

9

}.

Игрок C :

Q

0

C

(ω

1

) = {ω

1

}; Q

0

C

(ω

2

) = Q

0

C

(ω

4

) = {ω

1

, ω

2

, ω

4

};

Q

0

C

(ω

3

) = Q

0

C

(ω

5

) = {ω

3

, ω

5

}; Q

0

C

(ω

7

) = {ω

3

, ω

5

, ω

7

};

Q

0

C

(ω

8

) = {ω

8

}; Q

0

C

(ω

6

) = Q

0

C

(ω

9

) = {ω

6

, ω

9

}.

621

Событие X :

X = {ω

1

, ω

2

, ω

5

, ω

8

}.

Далее для удобства ω

i

будем обозначать через соответствующий

индекс i, т.е. в новых обозначениях X = {1, 2, 5, 8}.

Сообщение игрока А:

d

0

A

(ω)

=

µ(X ∩ A

A

(X)|Q

0

A

(ω))

=

µ({2, 5, 8}|Q

0

A

(ω)),

т.к. A

A

(X) = {2, 4, 5, 6, 7, 8, 9}.

Таблица. Сообщение игрока А

t = 1

ω

1

ω

2

ω

3

ω

4

ω

5

ω

6

ω

7

ω

8

ω

9

d

0

A

1

3

1

1

3

1

2

1

2

0

1

2

1

2

0

W

0

A

13

2

13

4578

4578

69

4578

4578

69

B

0

A

(W

0

A

)

∅

2

∅

4578

4578

69

4578

4578

69

Игрок A посылает сообщение игроку В в момент времени t =

1. Игрок В, получив сообщение, преобразует своё информационное

множество:

Q

1

B

(ω

4

) = Q

1

B

(ω

7

) = {ω

4

, ω

7

}; Q

1

B

(ω

2

) = {ω

2

};

Q

1

B

(ω

5

) = Q

1

B

(ω

8

) = {ω

5

, ω

8

}; Q

1

B

(ω

6

) = Q

1

B

(ω

9

) = {ω

6

, ω

9

}.

Таблица. Сообщение игрока B

t = 2

ω

1

ω

2

ω

3

ω

4

ω

5

ω

6

ω

7

ω

8

ω

9

d

1

B

×

1

×

0

1

0

0

1

0

W

1

B

×

258

×

4679

258

4679

4679

258

4679

B

1

B

(W

1

B

)

×

258

×

4679

258

4679

4679

258

4679

Игрок В посылает сообщение игроку С.

Информационное множество игрока С после получения сообще-

ния от игрока В:

Q

2

C

(ω

2

) = {ω

2

}; Q

2

C

(ω

4

) = {ω

4

}; Q

2

C

(ω

7

) = {ω

7

};

Q

2

C

(ω

8

) = {ω

8

}; Q

2

C

(ω

6

) = Q

2

C

(ω

9

) = {ω

6

, ω

9

}.

Таблица. Сообщение игрока C

t = 3

ω

1

ω

2

ω

3

ω

4

ω

5

ω

6

ω

7

ω

8

ω

9

d

2

C

×

1

×

0

×

0

0

1

0

W

2

C

×

28

×

4679

×

4679

4679

28

4679

B

2

C

(W

2

C

)

×

28

×

4679

×

4679

4679

28

4679

Игрок С посылает сообщение игроку А.

Информационное множество игрока А после получения сообще-

ния от игрока С:

Q

3

A

(ω

2

) = {ω

2

}; Q

3

A

(ω

4

) = Q

3

A

(ω

7

) = {ω

4

, ω

7

};

Q

3

A

(ω

8

) = {ω

8

}; Q

3

A

(ω

6

) = Q

3

A

(ω

9

) = {ω

6

, ω

9

}.

622

Таблица. Сообщение игрока A

t = 4

ω

1

ω

2

ω

3

ω

4

ω

5

ω

6

ω

7

ω

8

ω

9

d

3

A

×

1

×

0

×

0

0

1

0

W

3

A

×

28

×

4679

×

4679

4679

28

4679

B

3

A

(W

3

A

)

×

28

×

4679

×

4679

4679

28

4679

Игрок A посылает сообщение игроку В в момент времени t = 4.

Информационное множество игрока B:

Q

4

B

(ω

4

) = Q

4

B

(ω

7

) = {ω

4

, ω

7

}; Q

4

B

(ω

2

) = {ω

2

};

Q

4

B

(ω

5

) = Q

4

B

(ω

8

) = {ω

5

, ω

8

}; Q

4

B

(ω

6

) = Q

4

B

(ω

9

) = {ω

6

, ω

9

}.

Таблица. Сообщение игрока B

t = 5

ω

1

ω

2

ω

3

ω

4

ω

5

ω

6

ω

7

ω

8

ω

9

d

4

B

×

1

×

0

×

0

0

1

0

W

4

B

×

28

×

4679

×

4679

4679

28

4679

B

4

B

(W

4

B

)

×

28

×

4679

×

4679

4679

28

4679

Игрок B посылает сообщение игроку C в момент времени t = 5.

Информационное множество игрока С после получения сообще-

ния от игрока В:

Q

2

C

(ω

2

) = {ω

2

}; Q

2

C

(ω

4

) = {ω

4

};

Q

2

C

(ω

7

) = {ω

7

}; Q

2

C

(ω

8

) = {ω

8

};

Q

2

C

(ω

6

) = Q

2

C

(ω

9

) = {ω

6

, ω

9

}.

При дальнейшем обмене сообщениями изменений информацион-

ных множеств не будет. Таким образом, равновесие достигнуто.

Литература

1. Bacharach M. The epistemic structure of a theory of a game // Theory

and Decision, 1994. Vol. 37, № 1. P. 7–48.

2. Bacharach M. Some extensions of a claim of Aumann in an axiomatic

model of knowledge // Journal of Economic Theory, 1985. № 37.

P. 167–190.

623

Тимофеева О.С., Хитров Г.М.

Санкт-Петербургский государственный университет

О сильно транзитивных бинарных отношениях

Статья посвящена развитию матричного метода в теории бинар-

ных отношений и, как следствие, теории графов. Основным содер-

жанием работы является доказательство матричным методом уже

доказанной в [1] теоремы о сильно транзитивных отношениях. Пред-

лагаемое в статье доказательство дает не только наглядное пред-

ставление о нормальной форме матрицы ([2], стр. 373) сильно тран-

зитивного отношения, но и указывает явный вид фигурирующих в

условиях теоремы подмножеств. Кроме того, в статье указан про-

стой матричный критерий проверки, является ли данное отношение

транзитивным. Как следствие получается и критерий сильной тран-

зитивности бинарного отношения.

Определение 1 ([1], стр. 16). Бинарным отношением R на мно-

жестве X = {x

1

, . . . , x

n

} называется подмножество R ∈ X × X, то

есть подмножество упорядоченных пар < x

i

, x

j

> декартова произ-

ведения множества X на себя.

Если важно подчеркнуть, что бинарное отношение R задано

на множестве X, то будем обозначать это бинарное отношение

< R, X >. Принадлежность пары < x

i

, x

j

> подмножеству R в тео-

рии бинарных отношений записывается x

i

Rx

j

и читается “x

i

нахо-

дится в отношении R с x

j

”.

Сопоставим каждой паре < x

i

, x

j

> элемент

a

ij

=

1, < x

i

, x

j

>∈ R,

0, < x

i

, x

j

> /

∈ R.

Из элементов a

ij

построим матрицу, которую будем обозначать

A(R) и называть матрицей бинарного отношения R.

Определение 2 ([1], стр. 16). Бинарное отношение на X (|X| =

n) (дальше просто отношение) называется пустым (обозначается ∅),

если оно не выполняется ни для одной пары (x, y) ∈ X × X.

Для пустого отношения ∅ справедливо: матрица A(∅) — такая,

что a

ij

(∅) = 0 для всех i и j, т.е. A(∅)=0.

Определение 3 ([1], стр. 16). Отношение называется полным

(обозначается U ), если оно выполняется для всех пар (x, y) ∈ X × X.

624

Для полного отношения U справедливо: матрица A(U ) — такая,

что a

ij

(U ) = 1 для всех i и j. Матрицу полного отношения в даль-

нейшем будем также обозначать буквой U .

Введем операцию произведения отношений.

Определение 4 ([1], стр. 22–23). Назовем произведением R

1

и

R

2

отношение, определяемое следующим образом: xR

1

· R

2

y, если

существует z ∈ X, для которого xR

1

z и zR

2

y, где R

1

· R

2

– символ

произведения отношений.

Очевидно, что после того, как определено произведение двух от-

ношений, так сразу же определено произведение любого числа от-

ношений, когда сначала умножается пара отношений, затем про-

изведение умножается на третье отношение, полученный резуль-

тат умножается на следующее отношение и т.д. Нетрудно показать,

что произведение отношений ассоциативно, то есть (R

1

· R

2

) · R

3

=

R

1

· (R

2

· R

3

). Действительно, если x(R

1

· R

2

) · R

3

y, то существует

z такое, что xR

1

· R

2

z и zR

3

y. Из того, что xR

1

· R

2

z, следует, что

существует u такое, что xR

1

u и uR

2

z. Далее, из uR

2

z и zR

3

y следует,

что uR

2

· R

3

y. А из xR

1

u и uR

2

· R

3

y следует, что xR

1

· (R

2

· R

3

)y. И

так показано, что если x(R

1

·R

2

)·R

3

y, то xR

1

·(R

2

·R

3

)y. Аналогично

показывается, что из xR

1

· (R

2

· R

3

)y следует, что x(R

1

· R

2

) · R

3

y. Тем

самым показано, что (R

1

· R

2

) · R

3

= R

1

· (R

2

· R

3

).

Нетрудно видеть, что A(R

1

· R

2

) = A(R

1

) ˙

×A(R

2

); знак ˙

× здесь

и далее означает булево умножение матриц (обычное умножение

сомножителей и булево сложение слагаемых).

Нетрудно показать, что булево произведение (0,1)-матриц будет

ассоциативным.

Определение 5 ([1], стр. 25). Отношение R называется тран-

зитивным, если R

2

⊆ R. Раскрывая это включение, приходим к

следующему: если xRz и zRy, то xRy. Отсюда по индукции получа-

ем: если xRz

1

, z

1

Rz

2

, . . . z

k−1

Ry, то xRy. Это означает, что R

k

⊆ R

для любого k

2.

Определение 6 ([3], стр. 250).

n

k=1

R

k

называется транзитив-

ным замыканием бинарного отношения R, заданного на множестве

X мощности n (т.е. |X| = n).

Из определения 6 и сказанного выше относительно транзитивного

отношения следует очевидное замечание, которое ввиду его важно-

сти сформулируем в виде утверждения.

Утверждение 1. Отношение R будет транзитивным отноше-

625

нием тогда и только тогда, когда оно совпадает со своим транзи-

тивным замыканием, то есть когда R =

n

k=1

R

k

.

Очевидно, что полное и пустое отношения являются транзитив-

ными.

Замечание 1. Из определения транзитивного отношения следу-

ет, что сужение транзитивного отношения будет транзитивным от-

ношением.

Для матрицы A(R) транзитивного отношения R справедливо сле-

дующее соотношение A(R) ˙

×A(R)

A(R) (следует непосредственно

из определения).

Сформулируем теперь матричный аналог утверждения 1.

Утверждение 2. Матрица A(R) будет матрицей транзитив-

ного отношения тогда и только тогда, когда выполняется следую-

щее равенство: A(R) = ˙

+

n

k=1

A

×k

(R) (A(R) равно булевской сумме

булевских степеней матрицы A(R)).

Проверка равенства A(R) = ˙

+

n

k=1

A

˙

×k

(R) может быть легко ре-

ализована на компьютере и поэтому может служить критерием, яв-

ляется ли данное бинарное отношение транзитивным или нет.

Если воспользоваться понятиями разложимой и неразложимой

матрицы, то про матрицу транзитивного отношения можно сказать

следующее.

Утверждение 3. Если матрица транзитивного отношения

A(R) неразложима, то A(R) = U .

Действительно, возьмем любую пару индексов (i, j). Из неразло-

жимости матрицы A(R) следует, что существуют такие a

ii

1

, a

i

1

i

2

, . . . ,

a

i

k−1

j

, что a

ii

1

a

i

1

i

2

· . . . · a

i

k−1

j

= 1 ([4], стр. 150). Из транзитивности

тотчас же следует, что a

ij

= 1. Поскольку пару (i, j) можно выбрать

произвольной, то этим и завершается доказательство.

Замечание 2. Пусть теперь матрица транзитивного отношения

A(R) разложима. Тогда с помощью перестановки рядов (перестанов-

ки строк и такой же перестановки столбцов) она может быть при-

ведена, например, к верхнему блочно-треугольному виду (нули сни-

зу) ([2], стр. 373). При этом вдоль диагонали будут стоять блоки,

представляющие собой либо неразложимые матрицы, либо нулевые

матрицы первого порядка (возможно объединенные в квадратные

блоки). В этом случае диагональные блоки, представляющие собой

626

неразложимые матрицы, будут являться матрицами U соответству-

ющих размерностей (в силу утверждения 3).

Введем еще два необходимых в дальнейшем понятия.

Определение 7 ([1], стр. 26). Отношение R называется отрица-

тельно транзитивным, если его дополнение ¯

R транзитивно. Дру-

гими словами, R отрицательно транзитивно тогда и только тогда,

когда ¯

R

2

⊆ ¯

R или когда выполнено A( ¯

R) ˙

×A( ¯

R)

A( ¯

R).

Определение 8 ([1], стр. 16). Отношение R называется сильно

транзитивным, если оно одновременно транзитивно и отрицательно

транзитивно.

Замечание 3. Сужение сильно транзитивного отношения будет

сильно транзитивным отношением.

Структуру сильно транзитивных отношений (и тем самым струк-

туру соответствующих им графов) описывает следующая теорема.

Теорема 1 ([1], стр. 27). Пусть < R, X > – сильно транзи-

тивное отношение на X, |X| < ∞. Тогда существует разбиение

X =

k

i=1

X

i

, X

i

∩ X

j

= ∅, i = j, такое, что

1) xRy, если x ∈ X

i

, y ∈ X

j

, i < j;

2) сужение отношения R на любое из X

i

является либо пу-

стым, либо полным отношением на X

i

.

Доказательство. Полное отношение, очевидно, является силь-

но транзитивным отношением. Для него утверждение теоремы спра-

ведливо.

Если теперь матрицу полного отношения U представить в виде

суммы двух квазитреугольных матриц верхней и нижней, с диаго-

нальными квадратными блоками, состоящими или из одних нулей,

или одних единиц, то каждая из матриц-слагаемых будет являть-

ся матрицей сильно транзитивного отношения. (Действительно, для

таких матриц, являющихся взаимно дополнительными, выполняют-

ся соответствующие матричные неравенства). Теорема утверждает,

что других сильно транзитивных отношений, то есть отношений, не

сводящихся к указанным, не существует.

Пусть < R, X > – сильно транзитивное отношение на X и A(R)

– матрица этого отношения. Предположим, что A(R) разложимая и

что перестановкой рядов (перестановкой строк и такой же переста-

новкой столбцов) она приведена к виду ([2], стр. 373):

627

˜

A(R) = P A(R)P =









A

11

A

12

. . . A

1m

0

A

22

. . . A

2m

. . .

. . .

. . . . . .

0

0

. . . A

mm







 ,

(1)

то есть к виду, указанному в замечании 2.

Матрица перестановки P , приводящая матрицу A(R) к виду (1),

фактически задает разбиение столбца ˜

X = P X в соответствии с раз-

биением матрицы ˜

A(R) на блоки (столбец X – упорядочение множе-

ства X, при котором отношению R сопоставлена матрица A(R)). Тем

самым можно говорить о разбиении исходного множества X на неко-

торые подмножества. Покажем, что это и есть искомое, указанное в

теореме, разбиение.

Другими словами, покажем, что с помощью преобразования Р-

подобия матрица сильно транзитивного отношения может быть при-

ведена к виду (1), где все блоки, стоящие над диагональю, состоят

из единиц, а диагональные блоки соответствуют матрицам пустых

или полных отношений.

Начнем доказательство со случая m = 2, предполагая, что

A(R) = A изначально имеет вид (1), то есть

A =

A

11

A

12

0

A

22

.

(2)

Обозначим через U

ij

матрицу, состоящую из одних единиц и име-

ющую ту же размерность, что и матрица-блок A

ij

. Тогда наши пред-

положения о диагональных матрицах-блоках можно записать в виде:

либо A

ii

= 0, либо A

ii

= U

ii

.

Изучим, когда матрица, имеющая вид (2), будет являться мат-

рицей транзитивного отношения. Для этого рассмотрим матричное

неравенство

A ˙

×A =

A

11

A

12

0

A

22

˙

×

A

11

A

12

0

A

22

=

=

A

11

˙

×A

11

A

11

˙

×A

12

˙

+A

12

˙

×A

22

0

A

22

˙

×A

22

A

11

A

12

0

A

22

.

628

Так как в нашем случае A

ii

˙

×A

ii

= A

ii

(i = 1, 2), то изучение

выписанного матричного неравенства сводится к изучению неравен-

ства

A

11

˙

×A

12

˙

+A

12

˙

×A

22

A

12

.

Разберем все возможные варианты.

1. A

11

= 0, A

22

= 0. В этом случае для любой матрицы A

12

нера-

венство выполняется.

2. A

11

= U

11

, A

22

= 0. В этом случае должно выполняться

U

11

˙

×A

12

A

12

. В левой части последнего неравенства стоит мат-

рица, у которой все элементы k-го столбца равны булевой сумме

элементов k-го столбца матрицы A

12

. Следовательно, в этом случае

неравенство U

11

˙

×A

12

A

12

может выполняться только в форме ра-

венства, причем матрица A

12

может состоять только из столбцов,

состоящих или из одних нулей, или из одних единиц.

3. A

11

= 0, A

22

= U

22

. По аналогии со случаем 2 делаем заклю-

чение, что в этом случае искомое неравенство выполняется только в

форме равенства, и строки матрицы A

12

состоят или из одних нулей,

или из одних единиц.

4. A

11

= U

11

, A

22

= U

22

. В этом случае неравенство возможно

только в форме равенства, когда A

12

= 0 или A

12

= U

12

.

Итак, можно говорить, что матрица A является матрицей тран-

зитивного отношения тогда и только тогда, когда выполнено одно из

условий 1 – 4 с вытекающими требованиями к матрице A

12

.

Рассмотрим теперь условия, при которых матрица (2) будет мат-

рицей сильно транзитивного отношения.

Для этого положим ¯

A

ij

= U

ij

− A

ij

и рассмотрим матрицу

¯

A =

¯

A

11

¯

A

12

U

21

¯

A

22

.

Матрица A будет матрицей сильно транзитивного отношения то-

гда и только тогда, когда одновременно выполняются два неравен-

ства:

A ˙

×A =

A

11

A

12

0

A

22

˙

×

A

11

A

12

0

A

22

=

=

A

11

˙

×A

11

A

11

˙

×A

12

˙

+A

12

˙

×A

22

0

A

22

˙

×A

22

A

11

A

12

0

A

22

,

629

¯

A ˙

× ¯

A =

¯

A

11

¯

A

12

U

21

¯

A

22

˙

×

¯

A

11

¯

A

12

U

21

¯

A

22

=

=

¯

A

11

˙

× ¯

A

11

˙

+ ¯

A

12

˙

×U

21

¯

A

11

˙

× ¯

A

12

˙

+ ¯

A

12

˙

× ¯

A

22

U

21

˙

× ¯

A

11

˙

+ ¯

A

22

˙

×U

21

U

21

˙

× ¯

A

12

˙

+ ¯

A

22

˙

× ¯

A

22

¯

A

11

¯

A

12

U

21

¯

A

22

.

По сути, остается рассмотреть второе матричное неравенство при

условии, что первое матричное неравенство выполнено. Второе мат-

ричное неравенство сводится к четырем неравенствам:

a) ¯

A

11

˙

× ¯

A

11

˙

+ ¯

A

12

˙

×U

21

¯

A

11

,

b) U

21

˙

× ¯

A

11

˙

+ ¯

A

22

˙

×U

21

U

21

,

c) ¯

A

11

˙

× ¯

A

12

˙

+ ¯

A

12

˙

× ¯

A

22

¯

A

12

,

d) U

21

˙

× ¯

A

12

˙

+ ¯

A

22

˙

× ¯

A

22

¯

A

22

.

Следовательно, необходимо рассмотреть полученные ранее 4

условия в сочетании с четырьмя неравенствами.

1’. A

11

= 0, A

22

= 0 ⇒ ¯

A

11

= U

11

, ¯

A

22

= U

22

.

В этом случае неравенства a), b), d) выполняются вне зависимо-

сти от вида матрицы ¯

A

12

. Неравенство c) выполнено тогда и только

тогда, когда ¯

A

12

= 0, или ¯

A

12

= U

12

.

Поскольку в случае 1 на матрицу A

12

не накладывалось никаких

требований, то в этом случае оба матричные неравенства выполня-

ются, когда A

12

= 0 или A

12

= U

12

.

2’. A

11

= U

11

, A

22

= 0 ⇒ ¯

A

11

= 0, ¯

A

22

= U

22

.

В этом случае из неравенства a) следует, что ¯

A

12

= 0 (или, что

тоже самое, A

12

= U

12

); при этом условии остальные неравенства b),

c), d) выполняются.

3’. A

11

= 0, A

22

= U

22

⇒ A

11

= U

11

, A

22

= 0.

В этом случае из неравенства d) следует, что ¯

A

12

= 0; при этом

условии остальные неравенства a), b), c) выполняются.

4’. A

11

= U

11

, A

22

= U

22

⇒ ¯

A

11

= 0, ¯

A

22

= 0.

В этом случае из неравенства a) ( или d)) следует, что ¯

A

12

= 0;

при этом условии остальные неравенства b), c), d) выполняются.

Подведем итог. Для того чтобы ненулевая матрица

A =

A

11

A

12

0

A

22

была матрицей сильно транзитивного отношения, необходимо и до-

статочно, чтобы A

12

= U

12

, а диагональные матрицы были матрица-

ми пустого или полного отношений.

630

Пусть теперь m = 3.

Рассмотрим матрицу

A =





0 U

12

0

0 U

22

U

23

0 0

0



 .

(3)

Все ее блочные главные миноры второго порядка удовлетворяют

условиям 1) – 4) и a) – d).

Рассмотрим матрицу

¯

A =





U

11

0

U

13

U

21

0

0

U

31

U

32

U

33





и покажем, что она не является транзитивной. Для этого вычислим

¯

A ˙

× ¯

A =





U

11

U

12

U

13

U

21

0

U

23

U

31

U

32

U

33



 .

Очевидно, что отношение ¯

A ˙

× ¯

A

¯

A не выполняется. Т.е. матрица A

не является матрицей сильно транзитивного отношения.

Однако, если в матрице A на месте A

13

вместо нуля будет стоять

U

13

, то обе матрицы

A =





0 U

12

U

13

0 U

22

U

23

0 0

0





и

¯

A =





U

11

0

0

U

21

0

0

U

31

U

32

U

33





будут транзитивными. В этом случае матрица A является матрицей

сильно транзитивного отношения.

Завершение доказательства теоремы теперь сводится к несколь-

ким замечаниям.

Если диагональный блок A

ii

в матрице A сильно транзитивного

отношения, имеющей вид (1), ненулевой, то блоки, расположенные

631

вправо по строке и вверх по столбцу от A

ii

, будут состоять из одних

единиц (вытекает из замечания, что сужение сильно транзитивного

отношения будет сильно транзитивным отношением, и из требования

выполнения условий 1) – 4) и a) – d) для главных блочных подматриц

второго порядка).

Если в сильно транзитивной матрице (1) два диагональных ну-

левых блока идут друг за другом, то наддиагональный блок, соот-

ветствующий блоку A

12

в (2), должен быть ненулевой. В противном

случае, упомянутые нулевые диагональные блоки вместе с нулевы-

ми наддигональным и поддиагональным блоками могут быть объ-

единены в один нулевой блок большей размерности, что приведет к

другому блочному разбиению.

Нулевой блок, расположенный выше главной диагонали, гипоте-

тически может появиться только во второй и выше блочной наддиа-

гонали. Но тогда он может быть включен в главный минор третьего

порядка, имеющий вид (3). И по тем же соображениям, что и при

рассмотрении примера (3), нулевой блок должен быть заменен на

блок из одних единиц.

Окончательно получаем вывод, что матрица вида (1) будет мат-

рицей сильно транзитивного отношения тогда и только тогда, когда

у нее все блоки расположенные выше блочной диагонали состоят из

одних единиц, а диагональные блоки являются матрицами пустых

или полных отношений. Теорема доказана полностью.

Литература

1. Макаров И.М., Виноградская Т.М., Рубчинский А.А., Соколов

В.Б. Теория выбора и принятия решений. М.: Наука, 1982.

328 с.

2. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. 576 с.

3. Оре О. Теория графов. М.: Наука, 1968. 352 с.

4. Никайдо Х. Выпуклые структуры и математическая экономика.

М.: Мир, 1972. 520 с.

632

 

 

 

Кузютин

 

Вячеслав

 

Федотович

 

(1939-2006) 

Вячеслав Федотович Кузютин

10 апреля 2006 года трагически погиб в результате нелепой слу-

чайности профессор кафедры высшей математики нашего факуль-

тета Вячеслав Федотович Кузютин.

Вся трудовая деятельность В. Ф. Кузютина была связана с Санкт-

Петербургским государственным университетом. Вячеслав Федото-

вич в 1957 году поступил, а в 1962 году окончил математико-

механический факультет нашего университета. Будучи еще студен-

том, он опубликовал научную статью в Вестнике ЛГУ. Талантливо-

го молодого человека оставили в университете для преподавания и

продолжения научной работы в лаборатории теории управляющих

устройств и механизмов, которую тогда возглавлял основатель фа-

культета ПМ – ПУ профессор В. И. Зубов.

В середине шестидесятых годов В. Ф. Кузютин был направлен в

Алжир для преподавания математических дисциплин. С этим Вяче-

слав Федотович блестяще справился и опубликовал там несколько

учебных пособий на французском языке. Вернувшись домой, Вяче-

слав Федотович сразу же активно включился в процесс становления

нового факультета прикладной математики – процессов управления.

В 1970 году его назначили куратором первого, принятого на факуль-

тет, курса. Всю жизнь он сохранял деловые и дружеские отношения

с выпускниками нашего факультета, учившимися на этом курсе, но

так повезло очень и очень многим курсам, так как Вячеслав Федото-

вич более двадцати лет после этого являлся заместителем декана по

работе со студентами нашего факультета. Он прекрасно помнил всех

студентов, знал их печали и радости, всегда помогал, если только это

было возможно. Своей человечностью он снискал вечную память,

знавших его людей.

С 1971 по 1980 год Вячеслав Федотович являлся также первым

ученым секретарем кафедры высшей математики и сыграл большую

роль в ее становлении.

В. Ф. Кузютин был известным специалистом по теории аппрокси-

мации и численным методам интегрирования, написал десятки на-

учных и популярных статей, монографии, учебник по геометрии для

высших учебных заведений.

В. Ф. Кузютин был всегда деятельным и неравнодушным чело-

веком, любое дело он выполнял творчески, с душой. Последние де-

сять лет он являлся членом методической комиссии университета,

им опубликовано более ста научных работ.

633

Большая научная, организационная и методическая работа Вя-

чеслава Федотовича не осталась незамеченной. Он был награжден

медалью "За трудовое отличие а в юбилейный 275-й год нашего Уни-

верситета в 1999 году ему присвоили звание "Заслуженный работник

высшей школы Российской Федерации".

Вячеслав Федотович навсегда останется в истории нашего фа-

культета, Университета и в наших сердцах.

Зав. кафедрой высшей математики,

проф. А. М. Камачкин

Основные научные труды В. Ф. Кузютина

1. Об оценке ошибки квадратурной формулы // Методы вычисле-

ний. Л., 1963. Вып. 2. С. 60–66.

2. Тригонометрические функции. Бумердес (Алжир), 1967 (на франц.

языке).

3. Погрешность кубатурной формулы с равными коэффициентами

и равноотстоящей сеткой узлов на некоторых классах функций

// Известия АН Казахской ССР. Сер. физ.-мат. Алма-Ата, 1980.

№ 8. С. 75–76.

4. Погрешности приближенных формул интегрирования. Учебное

пособие. Л.: Изд-во ЛГУ, 1982. 131 с.

5. Погрешности приближенных формул интегрирования на некото-

рых классах периодических функций // Математическая физика.

Л., 1984. С. 38–42.

6. Элементы векторного анализа, теории кривых и поверхностей.

Учебное пособие. СПб., Изд-во СПбГУ, 1993. 68 с.

7. Элементы выпуклого анализа. Учебное пособие / Н. А. Зенкевич,

В. Ф. Кузютин. СПб.: Изд-во СПбГУ, 1993. 81 с.

8. Аппроксимация функций и численное интегрирование. Учебное

пособие / В. В. Жук, В. Ф. Кузютин. СПб.: Изд-во СПбГУ, 1995.

351 с.

9. Геометрия / В. Ф. Кузютин, Н. А. Зенкевич, В. В. Еремеев. СПб.:

Изд-во СПбГУ, 2002. 322 с.

10. Геометрические места точек на плоскости: 100 задач / В. Ф. Ку-

зютин, В. В. Еремеев. СПб.: Изд-во СПбГУ, 2002. 52 с.

11. Геометрия / В. Ф. Кузютин, Н. А. Зенкевич, В. В. Еремеев. СПб.,

М., Краснодар: Изд-во Лань, 2003. 416 с.

634

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: