Глава 2. Антагонистические игры

Основными вопросами теории игр являются:

1. Какие свойства стратегий следует считать признаками оптимальности?

2. Существуют ли стратегии игроков, которые обладали бы свойствами оптимальности?

3. Как определить оптимальные стратегии, если они существуют?

2.1. Матричные игры в чистых стратегиях

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

Рассмотрим игру двух лиц с нулевой суммой.

Например, в случае игры в орлянку² каждый из игроков имеет по две стратегии, именуемые Орел и Решка. Если игроки выбирают одинаковые стра­тегии, т.е. в случаях, если оба говорят "Орел" или оба говорят "Решка", l-й иг­рок выигрывает 1 рубль, а второй игрок проигрывает 1 рубль. В ситуациях, ко­гда оба игрока выбирают различные стратегии, l-й игрок проигрывает 1 рубль, а 2-й игрок соответственно этот 1 рубль выигрывает.

Тогда матрица игры имеет следующий вид:

Возможные стратегии	(орел)	(решка)
(орел)	1	-1
(решка)	-1	1

В более компактной записи

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

Антагонистические игры, в которых выигрыш одного игрока равен проигрышу другого являются играми с нулевой суммой. Игра в орлянку, очевидно, является примером такой игры.

Рассмотрим пример задания матрицы выигрышей для игры с ненуле­вой суммой, называемой в литературе по теории игр дилемма заключенного³. Содержание игры следующее: два преступника ожидают приговора суда за со­вершенное злодеяние. Адвокат конфиденциально предлагает каждому из пре­ступников облегчить его участь (и даже освободить!), если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму за совершен­ное преступление на 10 лет. Если никто не сознается, то обоим угрожает за­ключение на определенный срок (скажем, 1 год) по обвинению в незначитель­ном преступлении. Если сознаются оба преступника, то, с учетом чистосердеч­ного признания, им обоим грозит попасть в тюрьму на 5 лет. Каждый заклю­ченный имеет на выбор 2 стратегии: не сознаваться или сознаться, выдав при этом сообщника.

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

Стратегии 2-го игрока

Стратегии l-го игрока

Ниже будем рассматривать модель конечной (с конечным числом стратегий) матричной игры двух сторон (игроков, участников) с нулевой суммой (выигрыш одного игрока равен проигрышу другого).

Матрица игры имеет вид

Игрок А	Игрок В
			…		…
			…		…
			…		…
…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…
			…		…

A_i – стратегии игрока A

B_k – стратегии игрока В

а_ik – выигрыши A (проигрыши B).

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

Игрок А	Игрок В						Минимумы строк
			…		…
			…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
Максимумы столбцов			…		…

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

.

Величина называется нижней ценой игры, которая обеспечивает гарантированный выигрыш игрока А. Стратегия , обеспечивающая получение такого выигрыша, называется максиминной.

Игрок В при выборе стратегии проиграет не более максимального значения из элементов k-го столбца, то есть величина проигрыша не больше . Игрок В выберет такую величину , которая максимальный проигрыш минимизирует, то есть

.

Величина называется верхней ценой игры, а соответствующая проигрышу стратегия – минимаксной.

Пусть выигрыш игрока А (цена игры) будет V, тогда его значение ограничено нижней и верхней ценами игры, то есть

.

Если же значения и совпадают, то есть

,

то такая игра называется игрой с седловой точкой.

Стратегии и называются оптимальными. Их совокупность ( , ) – решение игры. Элемент матрицы , стоящий на пересечении оптимальных стратегий называется седловой точкой. Значение этого элемента определяет цену игры.

Пример

Две фармацевтические компании А и В продают два вида лекарств против гриппа. Компания А рекламирует продукцию на радио (A₁), телевидении (А₂) и в газетах (А₃). Компания В, в дополнение к использованию радио (B₁), телевидения (В₂) и га­зет (В₃) рассылает также по почте брошюры (В₄.).

В зависимости от умения и интенсивности проведения рекламной кампа­нии, каждая из компаний может привлечь на свою сторону часть клиентов кон­курирующей компании. Приведенная ниже матрица характеризует процент клиентов, привлеченных или потерянных компанией А.

Компании	В1	В2	В3	В4
А1	8	-2	9	-3
А2	6	5	6	8
А3	-2	4	-9	5

Решение игры основано на обеспечении наилучшего результата из наи­худших для каждого игрока.

Компании	В1	В2	В3	В4	Минимумы строк
А1	8	-2	9	-3	-3
А2	6	5	6	8	5 – максимин
А3	-2	4	-9	5	-9
Максимумы столбцов	8	5 – минимакс	9	8

Если компания А выбирает стратегию А₁ то, неза­висимо от того, что предпринимает компания В, наихудшим результатом явля­ется потеря компанией А 3 % рынка в пользу компании В. Это определяется минимумом элементов первой строки матрицы платежей. Аналогично при вы­боре стратегии А₂ наихудшим исходом для компании А является увеличение рынка на 5 % за счет компании В. Наконец, наи­худшим исходом при выборе стратегии А₃ является потеря компанией А 9 % рынка в пользу компании В. Эти результаты содержатся в столбце "Минимумы строк". Чтобы достичь наи­лучшего результата из наихудших, компания А выбирает стратегию А₂, так как она соответствует наибольшему элементу столбца "Минимумы строк".

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

Оптимальным решением в игре является выбор стратегий А₂ и В₂, т.е. обеим компа­ниям следует проводить рекламу на телевидении. При этом выиг­рыш будет в пользу компании А, так как ее рынок увеличится на 5 %. В этом случае говорят, что цена игры равна 5 % и что компании А и В используют стратегии, соответствующие седловой точке.

Решение, соответствующее седловой точке, гарантирует, что ни од­ной из компаний нет смысла пытаться выбрать другую стратегию. Действи­тельно, если компания переходит к другой стратегии (В₂, В₃ или В₄), то компания А может сохранить свой выбор стратегии А₂, что приведет к большей потере рынка компанией В (6 или 8 %). По тем же причинам компании А нет резона использовать другую стратегию, если она приме­нит, например, стратегию А₃, то компания В может использовать свою стратегию В₃ и увеличить свой рынок на 9 %. Аналогичные выводы имеют ме­сто, если компания А будет использовать стратегию А₁.