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



жүктеу 30.48 Mb.
Pdf просмотр
бет56/57
Дата27.12.2016
өлшемі30.48 Mb.
1   ...   49   50   51   52   53   54   55   56   57

Доказательство. Если построить хотя бы одну компоненту век-

тора выигрышей SM-ядра и показать, что она не совпадает в общем

случае с соответствующей компонентой вектора Шепли, то утвер-

ждение будет доказано.

Следует заметить, что SM-ядро можно построить, если среди ми-

нимальных приравниваемых эксцессов ¯

e(x, S) будут присутствовать

эксцессы по единичным коалициям ¯

e(x, i) (или обратные к ним экс-

цессы ¯

e(x, N \i )) и в сумме приравниваемые минимальные эксцессы



606

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

алиций в сумме дают 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

1   ...   49   50   51   52   53   54   55   56   57


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет