Прогнозирование устойчивости. Жигулин Г.П - 11 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

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

Рубрика: 

13
Покажем, что минимаксные стратегии в данном примере являются
неустойчивыми. Действительно, пусть, например, противник (игрок
B
) выбрал
одну из своих минимаксных стратегий
1
B и придерживается её. Узнав об этом,
мы (игрок
A
) перейдём к стратегии
3
A и будем выигрывать 4 единицы. На это
противник ответит стратегией
2
B
и будет выигрывать 5 единиц, на это мы, в
свою очередь, ответим стратегией
2
A и будем выигрывать 4 единицы и т.д.
Следовательно, положение, при котором оба игрока пользуются своими
минимаксными стратегиями, является неустойчивым и может быть нарушено
поступившими сведениями о стратегии, которую применяет противная сторона.
Пример 2. Пусть игра
44 × задана матрицей (табл. 1.7.):
Таблица 1.7.
A
i
B
j
B
1
B
2
B
3
B
4
i
α
A
1
0,4 0,5 0,9 0,3 0,3
A
2
0,8 0,4 0,3 0,7 0,3
A
3
0,7 0,6 0,8 0,9 0,6
A
4
0,7 0,2 0,4 0,6 0,2
j
β
0,8 0,6 0,9 0,9
Нижняя цена игры максимин
6,0minmax
=
=
ij
i
j
a
α
;
Верхняя цена игры минимакс
6,0maxmin
=
=
ij
i
j
a
β
.
Как видим, в данном примере, нижняя цена игры равна верхней цене игры,
т.е.
6,0==
β
α
. В таких случаях говорят, что игра имеет чистую цену игры
β
α
=
=
.
Такие игры занимают особое место в теории игр и называются играми с
седловой точкой. В матрице такой игры существует элемент, который является
одновременно минимальным в своей строке и максимальным в своём столбце, в
нашем примере элемент
6,0
32
=a . Такой элемент называется седловой точкой
(по аналогии с седловой точкой, где достигается минимум по одной координате
и максимум по другой). Седловой точке соответствует пара минимаксных
стратегий. Эти стратегии называются оптимальными, а совокупность
оптимальных стратегий является решением игры.
Решение игры обладает следующим свойством: если одна из сторон
придерживается своей оптимальной стратегии
, то для другой стороны не может
быть выгодным отклоняться от своей оптимальной стратегии (такое отклонение
либо оставит положение неизменным, либо ухудшит его). Действительно, пусть
в игре с седловой точкой игрок
A и игрок
B
придерживаются своих
оптимальных стратегий, в нашем примере
3
A и
2
B
, тогда выигрыш остаётся
постоянным и равным чистой цене игры
6,0
=
. Теперь предположим, что
B

Страницы