§2. Нижняя и верхняя цена игры. Принцип "мннимакса"

Рассмотрим игру mxn co следующей матрицей.

В А	В1	В2	….	Вп
А1	а11	а12	….	а1п
А2	а12	а22	….	а2п
….	….	….	….	….
Ат	а т2	ат2	….	атп

Будем обозначать буквой i номер стратегии игрока А; j- номер стратегии игрока В. Поставим задачу определить оптимальную стратегию. Проанализируем последовательно каждую из стратегий игрока А, начиная с А₁.

Выбирая стратегию А_i игрок А должен рассчитывать на то, что игрок В (противник) ответит на нее той же из стратегий B_j, для которой выигрыш игрока А - a_ij в i строке и обозначим его α_i:

.

Под знаком (минимум по j) обозначено минимальное из значений данного параметра при всех возможных j. Выпишем α_i рядом с матрицей справа в виде добавочного столбца:

В А	В1	В2	….	Вп	αi
А1	а11	а12	….	а1п	α1
А2	а12	а22	….	а2п	α 2
….	….	….	….	….	….
Ат	а т2	ат2	….	атп	α т
βj	β1	β2	…	βп

Выбирая какую-либо стратегию A_i надо рассчитывать на то, что в итоге разумных действий игрока В, игрок А не выиграет больше, чем α_i. Останавливаемся на той стратегии А_i; для которой число α_i является максимальным. Обозначим это число через α:

. (2)

Определение. Величина α называется нижней ценой игры; иначе - мак­симальным выигрышем или просто максимином.

Число α лежит в определённой строчке матрицы; та стратегия игрока А, ко­торая соответствует этой строчке, называется максиминной стратегией.

Очевидно, если мы будем придерживаться максиминной стратегии, то нам при любом поведении противника гарантирован выигрыш, во всяком случае не меньший α. Поэтому величина α называется «нижней ценой игры».

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

и найдем минимальное значение из β_j :

.

Величина β называется «верхней ценой игры» иначе «минимаксом». Соответствующая минимаксному выигрышу стратегия конкурента называется его «минимаксной стратегией».

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

Принцип осторожности, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр и её приложениях часто называют «принципом минимакса».

Наиболее осторожные максиминную и минимаксную стратегии игроков иногда обозначают общим термином «минимальные стратегии».

Пример 1. В нашем распоряжении имеется три вида вооружения: А_1, А₂, А₃; у противника три вида танков: В₁, В₂, В₃. Наша задача - поразить танк; задача противника - сохранить его не поражённым. При применении вооружения A₁ танки В₁, В₂, В₃ поражаются соответственно с вероятностями 0,9; 0,4 и 0,2; при вооружении А₂ - с вероятностями 0,3; 0,6 и 0,8; при вооружении А₃ - с вероятностями 0,5; 0,7 и 0,2. Требуется сформулировать ситуацию в терминах теории игр и составить матрицу игры. Определить нижнюю и верхнюю цену игры и минимаксные стратегии.

Решение. Ситуация может рассматриваться как игра 3x3 с двумя личными и одним случайным ходами. Наш личный ход - выбор типа вооружения; личный ход противника - выбор танка для участия в бою. Случайный ход - применение вооружения; этот ход может закончиться поражением или не поражением танка.

Наш выигрыш равен единице, если танк поражён, и равен нулю в противном случае. Нашими стратегиями являются три вида вооружения; стратегиями противника - три вида танков. Среднее значение выигрыша при каждой заданной паре стратегий есть не что иное, как вероятность поражения данного танка данным вооружением. Тогда матрица игры выглядит следующим образом.

В А	В1	В2	Вп	αi
А1	0,9	0,4	0,2	0,2
А2	0,3	0,6	0,8	0,3
Ат	0,5	0,7	0,2	0,2
βj	0,9	0,7	0,8

Нижняя цена игры α= 0,3; верхняя цена игры β= 0,7. Наша наиболее осто­рожная игра (максиминная) стратегия есть А₂, мы гарантируем, что будем поражать танк в среднем не менее чем в 0,3 всех случаев. Наиболее осторожной стратегией (минимаксной) противника является В₂, применяя этот танк, противник может быть уверен, что он будет поражаться не более чем в 0,7 всех случаев.

Замечание. В данном примере можно показать важное свойство минимакс­ных стратегий - их неустойчивость. Если мы применим свою наиболее осторожную (максиминную) стратегию В₂, то, придерживаясь этих стратегий, обе стороны будут иметь средний выигрыш 0,6, он будет уже больше нижней цены игры и меньше верхней цены игры: α=0,3 < 0,6 < 0,7 =β.

Если предположим, что игрок В узнал, что игрок А применяет стратегию А₂, то он на неё может ответить стратегией B₁ и сведёт выигрыш А к 0,3; но, в свою очередь, на стратегию противника В₁, игрок А может ответить стратегией А₁ которая даёт выигрыш 0,9 и так далее.

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

Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней: α=β.

Определение. Если нижняя цена игры равна верхней, то их общее значение называется чистой ценой игры (ценой игры) и обозначается буквой v.

Пример 2. Пусть дана игра 4x4 и задана её матрица. Произвести анализ игры.

Решение.

В А	В1	В2	В3	В4	α i
А1	0,4	0,5	0,9	0,3	0,3
А2	0,8	0,4	0,3	0,7	0,3
А3	0,7	0,6	0,8	0,9	0,6
А4	0,7	0,2	0,4	0,6	0,2
βj	0,8	0,6	0,8	0,9

Нижняя цена игры α= 0,6; верхняя цена игры β= 0,6.

Таким образом, α=β=v= 0,6 - чистая цена.

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

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

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

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

Отклонение игрока В от своей оптимальной стратегии в лучшем случае может оставить выигрыш неизменным, а в худшем случае - увеличить его.

Если игрок В придерживается своей оптимальной стратегии, а игрок А отклоняется от своей стратегии, то это ни коем образом не может быть выгодным для игрока А.

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

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

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

1. Если обе стороны придерживаются своих оптимальных стратегий, то средний выигрыш равен чистой цене игры v, одновременно являющейся её нижней и верхней ценой.

2. Если одна из сторон придерживается своей оптимальной стратегии, а другая отклоняется от своей, то от этого отклоняющаяся сторона может только потерять и ни в коем случае не может увеличить свой выигрыш.

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