Игра в чистых стратегиях

Математические методы и модели в экономике

Матричные игры

Введение

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

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

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

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

Игра в чистых стратегиях

Рассмотрим игру с двумя игроками А и В. Предположим, что игрок А имеет m стратегий А₁, А₂, …, А_m, а игрок В имеет n стратегий B₁, B₂, …,B_n. Будем считать, что выбор игроком А стратегии А_i, а игроком В стратегии B_j однозначно определяет исход игры, т.е. выигрыш a_ij игрока А и выигрыш b_ij игрока В. Здесь i=1,2,…,m, j=1,2,…,n.

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

b_ij=-a_ij

Это равенство означает, что выигрыш одного из игроков равен проигрышу другого. В этом случае достаточно рассматривать лишь выигрыши одного из игроков, например, игрока А.

Каждой паре стратегий А_i и B_j соответствует выигрыш a_ij игрока А. Все эти выигрыши удобно записывать в виде так называемой платежной матрицы

Строки этой матрицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. В общем случае такая игра называется (m×n)-игрой.

Пример 1. Два игрока А и В бросают монету. Если стороны монеты совпадают, то выигрывает А, т.е. игрок В платит игроку А некоторую сумму, равную 1, а если не совпадают, то выигрывает игрок В, т.е. наоборот, игрок А платит игроку В эту же сумму, равную 1. Сформировать платежную матрицу.

Решение. По условию задачи

	Орел	Решка
Орел	1	-1
Решка	-1	1

Таким образом, платежная матрица имеет вид

Пример 2. Известна следующая платежная матрица

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

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

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

Очевидно, что игрок А остановит свой выбор на второй стратегии, дающей ему гарантированный выигрыш, равный 1. Очевидно также, что игрок В остановит свой выбор на первой стратегии, при которой максимальный выигрыш игрока А минимален.

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

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

Рассмотрим произвольную (m×n)-игру

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

Рассмотрим оптимальные действия игрока А. В каждой строке платежной матрицы вычисляется минимальный элемент

Полученные числа приписываются в качестве правого столбца платежной матрицы

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

Итак,

Ясно, что это число является одним из элементов платежной матрицы.

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

Рассмотрим теперь оптимальные действия игрока В. В каждом столбце платежной матрицы вычисляется максимальный элемент

Полученные числа приписываются в качестве нижней строки платежной матрицы

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

Итак,

Ясно, что это число является также одним из элементов платежной матрицы.

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

Пример 3. Найти максиминную и минимаксную стратегию игроков, если платежная матрица имеет вид

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

Это означает, что какой бы выбор по столбцам ни сделал игрок В, выигрыш игрока А, который свои стратегии выбирает по строкам, в худшем случае составит соответственно: 2, -3, 1, 3. Ясно, что игрок А предпочтет выбрать такую стратегию (строку), для которой достигается максимальный выигрыш, независимо от того, какую стратегию (столбец) выбрал игрок В, т.е.

Таким образом, максиминной стратегией игрока А является стратегия А₄.

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

Это означает, что какой бы выбор по строкам ни сделал игрок А, проигрыш игрока В, который свои стратегии выбирает по столбцам, составит соответственно: 8, 7, 5, 9. Ясно, что игрок В предпочтет выбрать такую стратегию (столбец), для которой достигается минимальный проигрыш, независимо от того, какую стратегию (строку) выбрал игрок А, т.е.

Таким образом, минимаксной стратегией игрока В является стратегия В₃.

Заметим, что в нашем примере a<b.

Оказывается, справедлива следующая

Теорема. В матричной игре нижняя цена игры не превосходит верхней цены, т.е. a≤b.

Доказательство. По определению

Объединяя эти неравенства, получаем

Следовательно,

Это неравенство справедливо для любых индексов i и j. Значит,

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

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

Если для чистых стратегий А_i и B_j игроков А и В имеет место равенство

a=b

то такую пару стратегий называют седловой точкой матричной игры. Элемент a_ij, на котором достигается это равенство, называют седловым элементом платежной матрицы. Число

v=a=b

называют чистой ценой игры.

Пример 4. Исследовать платежную матрицу на наличие седловой точки и найти цену игры

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

Нижняя цена игры

Верхняя цена игры

Оказалось, что нижняя и верхняя цены игры совпали. Значит, чистая цена игры v=5.

В нашем примере седловой элемент а₃₂=5 находится на пересечении третьей строки и второго столбца платежной матрицы. Следовательно, оптимальной стратегией игрока А является третья стратегия, а игрока В - вторая стратегия.