double arrow

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

1

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

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

Введение

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

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

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

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

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

Рассмотрим игру с двумя игроками А и В. Предположим, что игрок А имеет m стратегий А1, А2, …, Аm , а игрок В имеет n стратегий B1, B2, … ,Bn. Будем считать, что выбор игроком А стратегии Аi, а игроком В стратегии Bj однозначно определяет исход игры, т.е. выигрыш aij игрока А и выигрыш bij игрока В. Здесь i=1,2,…,m, j=1,2,…,n.

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




bij=-aij

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

Итак,

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

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

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

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

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

Итак,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a=b

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

v=a=b

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

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

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

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

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

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

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

Заказать ✍️ написание учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой
1

Сейчас читают про: