Основные предположения для игр двух лиц с нулевой суммой

Игра для двух лиц с нулевой суммой задается следующими условиями:

- имеются два игрока, стратегии одного из которых расположены по строкам (первый игрок), а другого по столбцам (второй игрок);

- каждый игрок выбирает одну из своих стратегий независимо от другого: первый одну из m стратегий, второй одну из n стратегий;

- если первый игрок выбирает стратегию i, а второй стратегию j, то первый игрок получает выигрыш a_ij, который интерпретируется как платеж от второго игрока.

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

Таблица 12.1

	Стратегия 1 игрока 2	Стратегия 2 игрока 2	¼	Стратегия n игрока 2
Стратегия 1 игрока 1	a₁₁	a₁₂	¼	a₁_n
Стратегия 2 игрока 1	a₂₁	a₂₂	¼	a_2n
¼	¼	¼	¼	¼
Стратегия m игрока 1	a_m₁	a_m2	¼	a_mn

В табл. 12.2 приведена конкретная матрица игры, согласно которой, например, выигрыш первого игрока составит 2 единицы, если первый игрок выберет свою вторую стратегию, а второй игрок свою первую стратегию.

Таблица 12.2

	Стратегия 1 игрока 2	Стратегия 2 игрока 2	Стратегия 3 игрока 2	Стратегия 4 игрока 2
Стратегия 1 игрока 1				-1
Стратегия 2 игрока 1			-2

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

Верхнее и нижнее значение игры, условие седловой точки.

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

Таблица 12.3

	Стратегия 1	Стратегия 2	Стратегия 3	Минимум по строкам
Стратегия 1
Стратегия 2
Стратегия 3
Максимум по столбцам

Как должен играть первый игрок? Если первый игрок выберет свою первую стратегию, то второй игрок, очевидно, выберет первую или ворую стратегию, поскольку в этом случае его потери будут минимальными - 4 единицы. Значение «4» является минимальным в первой строке. Если первый игрок выбирает вторую стратегию, то второй выбирает третью стратегию, проигрывая при этом 1 единицу. Если первый игрок выбирает третью стратегию, то второй выбирает стратегию 2 с проигрышем 5 единиц. В последнем столбце таблицы записаны минимумы по строкам. Логично предположить, что первый игрок будет выбирать стратегию, обеспечивающую ему выигрыш максимального из этих значений.

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

Рассмотренная матрица удовлетворяет условию седловой точки:

max (минимумы по строкам) = min (максимум по столбцам). (12.1)

Говорят, что если выполнено условие (12.1), то игра имеет седловую точку. В строго математическом виде это можно переписать как

. (12.2)

Справедлива следующая теорема:

Теорема 1. Для любой конечной игры выполнено соотношение

. (12.3)

Доказательство. Очевидно, что

Откуда получаем

Так как в этом неравенстве слева стоит конкретное число, а справа – выражение, зависящее от j, то справедливо следующее неравенство

что и требовалось доказать.

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

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

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

Если a = b, то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий – седловой точкой матрицы. В этом случае элемент a_ij = v называется ценой игры. Он одновременно является минимальным в i -й строке и j -й столбце.

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

Смешанные стратегии

Рассмотрим пример игры «четное – нечетное». Два игрока вынимают из колоды по одной игральной карте. Если сумма очков обеих карт четная, то первый игрок получает от второго 1 рубль. Если сумма очков нечетная, то первый игрок платит второму 1 рубль. Платежная матрица данной игры представлена в табл. 12.4.

Таблица 12.4

	Стратегия 1	Стратегия 2	Минимум по строкам
Стратегия 1	-1	+1	-1
Стратегия 2	+1	-1	-1
Максимум по столбцам	+1	+1

Данная игра не имеет седловой точки, поскольку не выполняется условие (7.2) равенство максимина минимаксу.

Если платежная матрица не имеет седловой точки, т.е. a < b, то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами (вероятностями). Такая сложная стратегия называется смешанной.

Пусть: х ₁ – вероятность, с которой первый игрок вынимает карту с нечетным числом очков; х ₂ – вероятность, с которой первый игрок вынимает карту с четным числом очков; у ₁ – вероятность, с которой второй игрок вынимает карту с нечетным числом очков; у ₂ – вероятность, с которой второй игрок вынимает карту с четным числом очков.

Если х ₁ и х ₂ таковы, что , , , то (х ₁, х ₂) – смешанная, или случайная, стратегия первого игрока. Аналогично (у ₁, у ₂) – смешанная, или случайная, стратегия второго игрока, если , , .

В общем случае смешанные стратегии есть векторы ` х = (х ₁, х ₂, ¼, х_m) и ` у = (у ₁, у ₂, ¼, у_n), для которых

, (12.4)

. (12.5)

Если смешанная стратегия (х ₁, х ₂, ¼, х_m) такова, что одно из значений х_i = 1, а следовательно, остальные равны нулю, то такая стратегия называется чистой стратегией игрока. Чистая стратегия уже не является случайной. Вспоминая игру в чистых стратегиях, можно записать оптимальную стратегию первого игрока, как х ^* = (0, 0, 1), а второго, как у ^* = (0, 1, 0).

Подход к определению решения игры при смешанных стратегиях также основывается на критерии минимакса. Единственная разница заключается в том, что первый игрок выбирает х_i так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам, тогда как второй игрок выбирает y_j с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически критерий минимакса при смешанных стратегиях описывается следующим образом. Первый игрок выбирает стратегию, обеспечивающую

где переменные х и у удовлетворяют соотношениям (12.4) и (12.5), а второй игрок выбирает стратегию, обеспечивающую

Эти величины определяются соответственно как среднеожидаемые максиминные и среднеожидаемые минимаксные платежи.

Если х ^* _i и у ^* _j – оптимальные решения для обоих игроков, то каждому элементу платежной матрицы a_ij соответствует вероятность х ^* _iу ^* _j. Следовательно, оптимальное ожидаемое значение игры

Справедлива следующая основная теорема теории матричных игр с нулевой суммой (теорема фон Неймана).

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

Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры: .

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

Справедлива теорема об активных стратегиях.

Теорема 3. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш останется неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

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

12.3. Аналитическое решение игры 2´2

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

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

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

Пусть игра задана платежной матрицей

Средний выигрыш первого игрока, если он использует оптимальную смешанную стратегию , а второй игрок – чистую стратегию, соответствующую первому столбцу платежной матрицы, равен цене игры v:

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

Решая эту систему, получим оптимальную стратегию

и цену игры

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

Тогда оптимальная стратегия второго игрока определяется по формулам:

, .

Рассмотрим пример. Пусть задана платежная матрица игры с нулевой суммой

Следовательно, оптимальной стратегией первого игрока будет такая, что .

Поскольку a ¹ b, то имеем игру в смешанных стратегиях. Оптимальная стратегия первого игрока:

Исходя из равенства , имеем . Следовательно, .

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

Исходя из равенства , имеем . Следовательно, .

Цена игры:

При этом выполнено условие : .

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

Доминирование стратегий

Говорят, что некоторая стратегия i первого игрока (задаваемая i -й строкой платежной матрицы) доминируется некоторой другой стратегией k первого игрока, если все элементы строки i не больше соответствующих элементов строки k, а именно: .

Аналогичное определение можно привести для стратегий второго игрока, а именно: некоторая стратегия j второго игрока (задаваемая j -м столбцом платежной матрицы) доминируется некоторой другой стратегией k второго игрока, если все элементы столбца j не меньше соответствующих элементов столбца k, а именно: .

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

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

Рассмотрим игру, представленную платежной матрицей:

a ¹ b.

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

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

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

; ;

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