Теория игр. Часть 2. Кооперативные игры и игры в позиционной форме. Григорьева К.В. - 36 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

Составители: 

Рубрика: 

70 71
б)

yMxMUyx
i
,,
, т. е. любые две различные вершины
одного и того же ИМ имеют одинаковое количество альтернатив;
в) каждое ИМ пересекается только однажды с любым путем,
идущим из начальной позиции (вершины)
0
x
;
6) заданием для
2
n
Xx
распределения вероятностей

xP
1
, …,

xP
m
на множестве альтернатив, исходящих из вершины x:
 
.0,1
1
t
¦
xPxP
k
m
k
k
Замечание 6.2. Для различных x распределение вероятностей раз-
лично.
Замечание 6.3. Начальная вершина состоит только из одного ИМ.
Пример 6.1. Рассмотрим древовидный граф (см. рис. 6.5).
Множество
X
– это множество всех узлов;
3,1, iX
i
, – множе-е-
ство очередности игрока i;
4
X
– множество окончательных позиций;
5
X
– множество очередности случайного игрока.
1
2
II
II
2
1
I
12 1
I
23 1 2 1 2
1
III
III
2
¸
¸
¸
¹
·
¨
¨
¨
©
§
0
1
2
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
1
1
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
1
3
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
2
4
¸
¸
¸
¹
·
¨
¨
¨
©
§
2
3
7
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
3
5
¸
¸
¸
¹
·
¨
¨
¨
©
§
3
1
2
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
4
2
¸
¸
¸
¹
·
¨
¨
¨
©
§
1
2
6
0
x
Рис. 6.5
В окончательной позиции заданы три числа – выигрыши игроков.
Если игрок 3 не знает, что делал игрок 2, то две вершины объединяем
в одно ИМ. Игру начинает «случайный игрок» в вершине
0
x
. В зависи-
мости от его выбора альтернативы левая ветвь игры реализуется с веро-
ятностью
31
, а правая – с вероятностью
32
. Например, если случайный
игрок – «дождь» и известно, что дождь идет с вероятностью
31
, а с веро-
ятностью
32
дождя не будет, то если дождь пойдет, то реализуется левая
ветвь игры, если нет, то правая ветвь игры.
6.2. ВОЗМОЖНЫЕ ПОЗИЦИИ И СУЩЕСТВЕННЫЕ
ИНФОРМАЦИОННЫЕ МНОЖЕСТВА
Пусть
k
A
– множество всех вершин
X
x
, имеющих ровно k аль-
тернатив, т. е.
^
`
kFxA
xk
:. Пусть
`
^
i
j
i
j
i
i
XXXI :
– множествоо
всех ИМ игрока i.
Определение 6.4. Чистой стратегией игрока i называется функ-
ция
i
u
, отображающая
i
I
в множество положительных чисел:
^`
kXu
j
i
i
,1
, если
k
j
i
AX
.
При этом будем говорить, что стратегия
i
u
выбирает альтерна-
тиву l в позиции
,
j
i
Xx
если
,lXu
j
i
i
где l – номер альтернативы.
Напомним, что через Z мы обозначили некоторую партию в игре,
т. е. такую последовательность вершин от начальной до окончательной,
что каждая последующая принадлежит образу предыдущей.
Утверждение 6.1. Каждой ситуации
  
n
uuu ,...,
1
единствен-
ным образом соответствует партия Z, следовательно, и выигрыш в окон-
чательной позиции этой партии.
Определение 6.5. Позиция
X
x
называется возможной для чис-
той стратегии

i
u
, если существует ситуация

u
, содержащая эту стра-
тегию, в которой реализуется путь Z, содержащий эту позицию.
Очевидно, что партия Z возможна при данной стратегии

i
u
тог-
да и только тогда, когда эта стратегия выбирает альтернативы, соответ-
ствующие этой партии во всех ИМ, которые эта партия пересекает.
Отсюда следует справедливость следующей далее леммы [5, с. 212].
Лемма 6.1. Позиция
j
i
Xx
для стратегии

i
u
является возмож-ж-
ной тогда и только тогда, когда

i
u
выбирает альтернативы, лежащие на
отрезке партии
x
Z
от
0
x
до x во всех своих ИМ, пересекающих
x
Z
.

Страницы