Прямоугольные игры

Рассмотрим простейшую модель игры двух лиц, имеющих право на один ход каждому. Пусть эти ходы состоят в выборе одной из конечного числа альтернатив, возможно, собственных для каждого из игроков. Выбор альтернатив осуществляется партнерами в условиях полного отсутствия информации о выборе противника. Партия в подобной игре заканчивается платежом аij IIго игрока Iму , если первый игрок выбрал альтернативу Аi из набора А1, А2, …, Аm, а IIой – альтернативу Вj из набора В1, В2, …, Вn. Таким образом, данная игра полностью определяется матрицей платежа

 

А [mxn] =

 

Отметим, что числа аij могут быть отрицательными, что соответствует случаю выплаты Iго игрока IIму . Таким образом, игра имеет нулевую сумму.

Пример 1. (двухпальцевая игра Мора). В этой игре каждый из игроков одновременно выбрасывает один или два пальца руки, произнося при этом число один или два – предполагаемое число пальцев, которое, по его мнению, выбросит партнер. Если один из игроков угадал число пальцев, показанных противником, то он получает от него сумму, равную сумме пальцев, показанных им и партнером; в противном случае – ничья.

Обозначим альтернативы игроков двумя числами (i, j), i – число пальцев, показанных им, j – его партнером. Теперь матрица платежей имеет вид

 

 

(1,1) (1,2) (2,1) (2,2)

А =

 

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

Представим себе в случае произвольной прямоугольной игры с матрицей платежей А[mxn] размышления каждого из игроков. Первый может рассуждать так: если я выберу альтернативу А1, то партнер заплатит мне не менееa1j, если-А2, то – не менее a2j, и т.д.

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

 

а1j = а i*j = a

 

Альтернатива Ai*гарантирует первому игроку платеж a независимо от действий второго игрока.

Число a называют нижней ценой игры.

Рассуждения второго игрока симметричны. Его платеж при выборе альтернативы В1 не превосходит аi1 независимо от действий партнера, при – В2 – не более аi2 и т.д. Следовательно, независимо от действий его партнера существует стратегия Вj*, для которой

 

аij = аij* =

 

Она обеспечивает ему минимальные выплаты. Число называется верхней ценой игры. Можно показать, что для прямоугольной игры справедливо неравенство

Так в примере 1

= -2, = 2.

В частном случае, когда = = , возникает устойчивая ситуация, когда отклонение игрока I от выбора альтернативы Ai* может быть наказано игроком II и наоборот. В случае же строгого неравенства между нижней и верхней ценами игры, ситуация становится неустойчивой. Так, в примере 1 на упорное применение игроком I альтернативы (1,2) игрок II может ответить применением альтернативы (1,1), которая обеспечит ему выигрыш в 2 единицы.

Одним из результатов теории прямоугольных игр является

Теорема 1 Условие = = выполняется тогда и только тогда, когда существует пара альтернатив (Аi*, Bj*) для которых

 

аij* ≤ аi*j* , для всех i =

 

аi*j* ≤ ai*j , для всех j =

 

Эта пара образует седловую точку, обеспечивающую устойчивый выбор альтернатив для каждого из партнеров.

Итак, прямоугольная игра с cедловой точкой допускает выбор рациональных стратегий для каждого из игроков. Обратимся к играм без cедловой точки, подобных игре из примера 1. Удивительным является факт существования рациональных стратегий, представляемых в более широком смысле.

Распространим понятие стратегии от выбора определенной альтернативы до случайного выбора одной из альтернатив. Теперь нам будет удобно убрать буквы А и В из обозначений альтернатив, оставив лишь только индексы.

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

 

Х m
Р р1 р2 рm

 

которая приводит к выбору альтернативы i с вероятностью рi (i = ).

 

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

 

У n
Р q1 q2 ... qn

 

Предыдущие (чистые) стратегии соответствуют случаю выбора фиксированной альтернативы и определяются рядом распределения вероятностей, в котором одно из чисел р, q равняется единице.

Теперь в качестве характеристики результатов применения игроком I смешанной стратегии Х, а игроком II – стратегии У естественно рассмотреть средние ожидаемые выплаты игрока II игроку I.

М (Х,У) = аij pi qj

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

Если окажется, что для некоторых стратегий Х* и У* справедливы неравенства

 

М (Х, У*) ≤ М (Х**) ≤ М (Х*,У)

 

для всех стратегий Х, У, то пару (Х*, У*) называют оптимальными смешанными стратегиями, а величину М (Х*, У*) – ценой игры. В этом случае пара (Х*, У*) является решением игры или стратегической седловой точкой, так как ее существование является основанием для устойчивого выбора поведения каждого из игроков.

Поразительным фактом теории прямоугольных игр является

Теорема 2. Любая прямоугольная игра имеет стратегическую седловую точку (Х**), т.е.

 

М (Х,У) = М(Х1У) = М(Х**)

 

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