Чистые и смешенные стратегии. Нижнее и верхнее значение игры

Игры называются антагонистическими, или с нулевой суммой, если интересы игроков прямо противоположны. Если множества действий игроков конечны, то игру удобно представлять в матричной форме. Действия каждого игрока нумеруются. После чего составляется матрица игры, в которой номер строки совпадает с номером действия первого игрока, а номер столбца – с номером действия второго. Элемент матрицы, стоящий на пересечении i-ой строки и j-го столбца, представляет собой функцию полезности первого игрока или, попросту, его выигрыш в случае выбора игроками действий i и j, соответственно. Выигрыш второго игрока в игре с нулевой суммой всегда противоположен по знаку выигрышу первого игрока: . В матрице он не указывается, но его легко получить, заменив знак у элемента матрицы. Сумма выигрышей игроков всегда равна нулю, откуда и происходит название этого класса игр. Поскольку функции полезности игроков отличаются только знаком, то удобно пользоваться только одной из них. Для этого принято использовать функцию полезности первого игрока. Ее называют функций выигрыша и обозначают v(i,j):

В матричной игре с матрицей значения функции выигрыша равны элементам матрицы:

Пример 1. Игра в чет/нечет. Игроки договариваются о следующих правилах игры. Каждый из них тайно загадывает натуральное число. Затем числа предъявляются и складываются. Если сумма оказывается четной, то второй игрок платит первому единицу денег, а если нечетной, то – наоборот. Понятно, что для каждого из игроков несущественно, какое именно число загадывать, существенно лишь то, является оно четным или нечетным. Поэтому для каждого из игроков можно ограничиться списком лишь из двух действий: четное или нечетное число. Матрица этой игры выглядит следующим образом:

		Второй	игрок
		чет	нечет
Первый	чет		-1
игрок	нечет	-1

В приведенном примере элемент матрицы игры равен единице. Это означает, что при выборе действий (1,1) первый игрок выигрывает единицу, а второй игрок проигрывает единицу.

Естественно, что каждый из игроков не хочет проигрывать, а стремится к тому, чтобы выиграть как можно больше. Главной задачей теории игр является выработка рекомендаций по выбору действий игроком, приводящих к наилучшему для него результату. Существенными моментами для выработки таких рекомендаций являются информированность игроков и количество повторений игры. Если игра чет/нечет разыгрывается однократно, то почти никаких рекомендаций дать невозможно. Если же она многократно повторяется, то появляется возможность говорить о стратегии поведения в такой игре. Есть два класса стратегий. Первый класс – это выбор действия по какому-то фиксированному правилу. Например, устойчивое повторение одного и того же действия называется чистой стратегией.. Второй класс стратегий – это смешанные стратегии. Стратегия называется смешанной, если выбор действия происходит по случайному закону с известным распределением вероятностей. Например, первый игрок может перед выбором действия бросать монетку и выбирать действие в зависимости от результата этого испытания. Теория показывает, что подобная стратегия обеспечивает игроку в среднем нулевой результат, а большего результата он себе гарантировать не может. В общем случае смешанная стратегия – это вектор вероятностей: , где n – число чистых стратегий (или число действий игрока), а - вероятность выбора соответствующего действия ( ).

Пример 2. Важное место в теории игр занимает понятие осторожной стратегии. Пусть имеется игра, определяемая матрицей:

Предположим, что первый игрок решил применить одну из чистых стратегий. Какая из чистых стратегий лучше? Для каждой из чистых стратегий (для каждой строки матрицы) определим наихудший исход для первого игрока и запишем полученное число в отдельном столбце справа от матрицы. Для этого в каждой строке надо выбрать минимальное число. В первой строке наихудшим исходом для первого игрока будет проигрыш единицы. Во второй – проигрыш двух единиц. В третьей – выигрыш одной единицы. Полученный нами столбец чисел – это столбец гарантированных результатов первого игрока в случае применения соответствующих чистых стратегий. Действительно, если первый игрок применяет первую стратегию, то меньше, чем (-1) он получить не может, это его гарантированный результат. Затем из полученных чисел выбираем наибольшее, то есть выбираем «лучшее из худших». В результате получаем единицу. Эта единица представляет собой максимальный гарантированный результат первого игрока.В общем случае его обозначают:

(2.1)

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

Рассмотрим ту же игру с точки зрения второго игрока. Найдем наихудшие для него результаты при выборе тех или иных чистых стратегий. Напомним, что элементы матрицы – суть выигрыши первого игрока, но, с другой стороны, это проигрыши второго. Следовательно, наихудший результат (максимальный проигрыш) второго игрока при использовании им стратегии j соответствует максимальному числу в j-ом столбце матрицы. Поэтому будем искать максимальное значение в каждом из столбцов матрицы.

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

(2.2)

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

Игра из примера 1 не имеет цены. Для нее справедливо:

(2.3)

В общем случае справедливо следующее утверждение:

Лемма. В любой матричной игре с конечной матрицей

Доказательство:

Обозначим: . Пусть i произвольная стратегия первого игрока. Тогда:

Беря минимум от обеих частей неравенства, получаем:

(2.4)

Теперь заметим, что в правой части неравенства (2.4) стоит константа, а i выбиралось произвольно. Поэтому выполняется равенство:

(2.5)

что доказывает лемму.

Вернемся к результату (2.3). Нижнее значение игры является наиболее пессимистическим прогнозом для первого игрока – это среднее значение его выигрыша в обстановке, когда он все время проигрывает. Верхнее значение, наоборот, наиболее оптимистический прогноз его выигрыша. Реальное среднее значение игры будет лежать где-то между нижним и верхним значениями. Не существует, однако, никакой чистой стратегии, которая гарантировала бы одному из игроков этот промежуточный результат. В этом смысле в игре чет/нечет не существует оптимальной чистой стратегии.