Решения игр в смешанных стратегиях

Понятие об игровых моделях.

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

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

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

3) выбор решений в условиях неопределенности, когда действия стороны имеют своим следствием множество исходов, вероятности которых вообще неизвестны.

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

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

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

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

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

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

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

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

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

Методы и модели решения игровых задач

Принцип минимакса

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m стратегий (А₁, А₂, ..., А_m), а игрок II — n стратегий (В₁, В₂, ..., В_n). Такая игра называется игрой размерностью m ´ n. Пусть каждая сторона определилась с выбором стратегии: игрок I — A_i (i = 1, 2, ..., m), игрок II — B_j (j = 1, 2, ..., n). Выигрыши игрока I — (A_i, B_j) и игрока II — (A_i, B_j) удовлетворяют соотношению (A_i, B_j) + (A_i, B_j) = 0.

Если игра состоит только из личных ходов, то выбор стратегии (A_i, B_j) однозначно определяет исход игры , т.е. выигрыш игрока I. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (A_i, B_j) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш — это среднее значение (математическое ожидание). Предположим, что значения a_ij известны для каждой пары стратегий (A_i, B_j). Построим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы — стратегиям игрока II, т.е. платежную матрицу. Каждый элемент (a_ij > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II. Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш. Платежная матрица имеет следующий вид:

I \ II B₁ B₂ ... B_j ... B_n

A₁ a₁₁ a₁₂ ... a_1j ... a_1n a₁

A₂ a₂₁ a₂₂ ... a_2j ... a_2n a₂

... ... ... ... ... ... ... ...

A_i a_i1 a_i2 ... a_ij ... a_in a_i

... ... ... ... ... ... ... ...

A_m a_m1 a_m2 ... a_mj ... a_mn a_m

Β_j b₁ b₂ ... b_j ... b_n

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий A₁, A₂, ..., A_m;

2) наилучшей (оптимальной) стратегии игрока II из стратегий B₁, B₂, ..., B_m.

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

Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию А₁, то игрок II может выбрать такую стратегию B_j, при которой выигрыш игрока I будет равен наименьшему из чисел a_1j:

.

Выбирая стратегию A_i, игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем a_i. Поэтому игрок I должен выбрать ту стратегию, для которой a_i максимально:

.

Величина a — гарантированный выигрыш, который может обеспечить себе игрок I при любом поведении игрока II. Величина a называется нижней ценой игры или максимином, а стратегия А_i игрока I, обеспечивающая получение нижней цены игры, называется максиминной чистой стратегией. При этом игрок I при любом поведении игрока II обеспечивает себе выигрыш, не меньше a: a_i ³ a (i = 1, 2, ..., m).

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

.

и среди этих значений выбрать наименьшее: .

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

b_j £ b (j = 1, 2, ..., n), причем всегда справедливо неравенство a £ b.

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

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

Пример 1. Дана платежная матрица. Найти решение игры: определить нижнюю и верхнюю цены игры и минимаксные стратегии:

I \ II B₁ B₂ B₃ B₄ a

A₁ 5 3 8 2 2

A₂ 1 6 4 3 1

A₃ 9 5 4 7 4

Β_j 9 6 8 7

Таким образом, нижней цене игры (a = 4) соответствует стратегия A₃ игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 при любом поведении игрока II. Верхней цене игры (b = 6) соответствует стратегия игрока II — В₂. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен а₃₃ = 4.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. a = b. Такие игры называются играми с седловой точкой.

В этом случае g = a = b называется чистой ценой игры, а стратегии игроков и , позволяющие получить это значение — оптимальными. Пара называется седловой точкой матрицы, так как элемент одновременно является минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии и и чистая цена являются решением игры в чистых стратегиях, т.е. без привлечения механизма случайного выбора.

Пример 2. пусть задана платежная матрица. Найти нижнюю и верхнюю цены игры.

I II B₁ B₂ B₃ a

A₁ 5 1 2 1

A₂ 2 6 2 2

A₃ 3 4 3 3

b 5 6 3

Следовательно a = b = g = 3.

Седловой точкой является пара альтернатив (А₃, В₃).

Решения игр в смешанных стратегиях

Если матричная игра содержит седловую точку, то ее решение находится по принципу минимакса. Если же платежная матрица не имеет седловых точек, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше a, а игрок II обеспечит себе проигрыш не больше b. Так как a < b, то игрок I стремится увеличить выигрыш, а игрок II уменьшить проигрыш. Если информация о действиях противной стороны будет отсутствовать, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией. Смешанная стратегия игрока — это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Для применения смешанных стратегий должны быть следующие условия:

1) в игре отсутствует седловая точка;

2) игроками используется случайная смесь чистых стратегий с соответствующими вероятностями;

3) игра многократно повторяется в одних и тех же условиях;

4) при каждом из ходов один игрок не информирован о выборе стратегии другим игроком;

5) допускается осреднение результатов игр.

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

Отсюда следует, что каждая конечная игра имеет цену, которую обозначим через g, средний выигрыш, приходящийся на одну партию, удовлетворяющий условию a £ g £ b. Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.

Чистые стратегии игроков в их оптимальных смешанных стратегиях называются активными.

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

Смешанные стратегии игроков S₁ и S₂ обозначим соответственно A₁ , A₂ , … A_m и B₁ , B₂ , B₃ … B_n , а вероятности их использования через p_A = (p₁, p₂, ..., p_m) и q_B = (q₁, q₂, ..., q_n), где p_i ³ 0, q_j ³ 0, при этом .

Тогда смешанная стратегия игрока I — S_I, состоящая из стратегий A₁, A₂, ..., A_m, имеет вид:

.

Соответственно для игрока II:

.

Зная матрицу А для игрока I можно определить средний выигрыш (математическое ожидание) :

,

Игрок I, применяя свои смешанные стратегии, стремится увеличить свой средний выигрыш, достигая

.

Игрок II добивается:

.

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

.

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

Решить игру — это означает найти цену игры и оптимальные стратегии.

Рассмотрим наиболее простой случай конечной игры 2 ´ 2 без седловой точки с матрицами:

,

С платежной матрицей

.

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

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

В игре 2 ´ 2, не имеющей седловой точки, обе стратегии являются активными.

Для игрока I имеем систему уравнений:

Для игрока II аналогично:

Если g ¹ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы не равен нулю, следовательно, эти системы имеют единственное решение.

Решая систему уравнений (10) и (11) находим оптимальные ешения , и g:

Пример: Дана платежная матрица:

Найти решение.

Решение. Так как a = 3, b = 5, то a ¹ b, то и матрица игра не имеет седловой точки. Следовательно, решение ищем в смешанных стратегиях. Запишем системы уравнений:

для игрока I:

для игрока II:

Решив эти системы находим:

Следовательно оптимальные стратегии игроков имеют вид:

,

Геометрический метод

Решение игры в смешанных стратегиях допускает наглядную геометрическую интерпретацию. Геометрический метод решения игры включает следующие этапы.

1. В декартовой системе координат по оси абсцисс откладывается отрезок А₁А₂, длина которого равна 1 (рис. 2.1.). Левый конец отрезка точка x = 0 соответствует стратегии A₁, правый, где х = 1,0 — стратегии А₂. Все промежуточные точки этого отрезка соответствуют смешанным стратегиям S₁ = (p₁, p₂).

2. По оси ординат от точки O откладываются выигрыши при стратегии А₁.

3. На линии, параллельной оси ординат, от точки 1 откладываются выигрыши при стратегии А₂ .

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

.

Если игрок II применяет стратегию В₁, то выигрыш игрока I при использовании чистых стратегий А₁ и А₂ составляет соответственно a₁₁ = 0,4 и a₂₁ = 0,6. Соединим эти точки прямой В₁В₁ .

Если игрок I при стратегии В₁ применяет смешанную стратегию , то средний выигрыш, определяемый по формуле математического ожидания g₁ = a₁₁p₁ + a₂₁p₂, изображается ординатой точки N на прямой B₁B₁. Прямая B₁B₁ называется стратегией В₁. Ордината любой точки отрезка B₁B₁ равна величине выигрыша игрока I при применении им стратегии A₁ и А₂ с соответствующими вероятностями p₁ и p₂.

Аналогично строим отрезок В₂В₂, соответствующий применению игроком II стратегии В₂ .

Ординаты точек отрезка определяют средний стратегий А₁ и А₂ с соответствующими вероятностями p₁ и p₂ и равных g₂ = a₁₂p₁ + a₂₂p₂.

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

Игрок II Игрок I
	0,4	0,9	0,4
	0,6	0,5	0,5
	0,6	0,9

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

Рис. 2.1. Геометрический метод решения игры

Оптимальная смешанная стратегия и цена игры ровны.

Гарантированный средний выигрыш составляет 0,57.