Игры с седловой точкой

Рассмотрим общие принципы решения игр двух лиц с нулевой суммой. На основании принципа разумности рекомендуется выбирать в качестве наилучшей стратегии ту, которая обеспечивает наибольший гарантированный выигрыш (то есть выигрыш, не зависящий от действий противника, выигрыш, который противник никоим образом не может уменьшить). Пусть игра определяется матрицей: . Игрок A имеет m чистых стратегий A_i, а игрок B – n чистых стратегий B_j, . Паре стратегий

(A_i, B_j) соответствует платеж C_ij, выплачиваемый игроком B игроку A в конце игры, то есть выигрыш игрока A.

Если игрок A использует стратегию A_i, то он получит выигрыш, по крайней мере равный , где минимум берется по всем стратегиям игрока B. И так как игрок A свободен в выборе своей стратегии, то для него естественно стремится к тому, чтобы сделать возможно большим; то есть стремится выбрать такую стратегию A_{i 0}, чтобы получить выигрыш не меньше, чем , где максимум берется по всем стратегиям игрока A.

Стратегия A_{i 0} называется максиминной стратегией игрока A. Это его наиболее осторожная стратегия, применение которой при любом поведении игрока B гарантирует игроку A выигрыш C_ij не менее α. Величина α называется нижней ценой игры или максимином.

Игрок B, рассуждая таким же образом, выбирает стратегию B_{j 0}, при которой игрок A получит выигрыш не более чем . Стратегия B_{j 0} называется минимаксной стратегией игрока B. Это его наиболее осторожная стратегия, применение которой дает гарантию игроку B в том, что игрок A при любом своем поведении получает выигрыш не более чем . Величина называется верхней ценой игры или минимаксом.

Таким образом, при наиболее острожной игре игрок A должен применить максиминную, а игрок B минимаксную стратегии.

Принцип осторожности, которой диктует игрокам выбор таких стратегий называется принципом минимакса, а обе стратегии обобщенно минимаксными.

Таким образом, в рекомендациях теории игр не учитываются элементы риска, а также возможные просчеты и ошибки игроков. А в реальной конфликтной ситуации имеются и элементы риска и ошибки.

В каком же отношении находятся верхняя и нижняя цены игр. Можно показать, что для этих величин всегда справедливо неравенство

, то есть нижняя цена игры всегда не больше верхней α ≤ β.

Если нижняя цена игры равна верхней, то есть если α = β , то те значения i 0, j 0 при которых это равенство достигается указывают оптимальные стратегии игроков A_{i 0} и B_{j 0}. В этом случае игрок A придерживаясь своей максиминной стратегии получает не менее чем v, а игрок B придерживаясь своей минимаксной стратегии помешает игроку A получить больше чем v.

Всякое отклонение от оптимальных стратегий невыгодно обоим игрокам, так как для любых стратегий A_i и B_j справедливы неравенства:

C_{i,j 0} ≤ C_{i 0, j 0} ≤ C_{i 0, j}.

Элемент C_{i 0, j 0} называется седловой точкой матрицы C. Это название соответствует тому, что элемент C_{i 0, j0} матрицы C является одновременно минимальным в своей строке и максимальным в своем столбце.

Этот элемент C_{i 0, j 0} = v называется ценой игры, а сама игра называется игрой с седловой точкой.

Пример. Рассмотрим игру с платежной матрицей:

Bj Ai	B 1	B 2	B 3
A 1				α 1=26
A 2				α 2=10
A 3				α 3=15
	β 1 = 50	β 2 = 75	β3 = 26	α= 26 β= 26

α=β=v= 26
Игрок A имеет три стратегии, игрок B – 3 и каждый из них не знает какую стратегию применит противник.

Проверим, есть ли у этой матрицы седловая точка.

Для этого в каждой строке выберем минимальный элемент (и запишем в последний столбец таблицы), а в каждом столбце выберем максимальный элемент (и запишем в последнюю строку таблицы).

Затем находим нижнюю и верхнюю цену игры, для этого выбираем максимальный элемент в последнем столбце и минимальный элемент в последней строке. Получим:

,

то есть верхняя и нижняя цены равны. Платежная матрица имеет седловую точку: C _1,3. Следовательно, пара стратегий (A ₁, B ₃) является оптимальной и цена игры равна 26. Это и есть решение данной игры.

Действительно, если игрок A будет придерживаться стратегии A ₁, он выиграет не менее 26, а может выиграть и больше, если игрок B отклонится от своей оптимальной стратегии B ₃.

Поиск по сайту: