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

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

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

3) Игра 2х2.

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

.

Предположим, что седловая точка отсутствует. Однако, согласно теореме Неймана, оптимальное решение игры существует и определяется парой смешанных стратегий S_A *=(p ₁*, p ₂*), S_B *=(q ₁*, q ₂*). Используя свойство 3 решения игр и элементарные алгебраические преобразования (подробный вывод мы опускаем), приходим к следующим формулам:

р ₁=(а ₂₂– а ₂₁)/(а ₁₁+ а ₂₂– а ₁₂– а ₂₁), р ₂=1– р ₁,

q ₁=(a ₂₂–a₁₂)/(a ₁₁+ a ₂₂– a ₁₂– a ₂₁), q ₂=1– q ₁, (2.7)

v_S =(a ₂₂· a ₁₁- a ₁₂· a ₂₁)/(a ₁₁+ a ₂₂– a ₁₂– a ₂₁).

При этом отсутствие седловой точки в игре гарантирует необращение в 0 знаменателей в приведенных формулах.

Пример 2.4. Найдем решение в смешанных стратегиях игры, рассмотренной в примере 2.1 о двух игроках с двумя монетами. Платежная матрица этой игры имеет вид:

Нижняя и верхняя цены этой игры a =–3 и b =2. Следовательно, седловая точка отсутствует.

Найдем оптимальные стратегии игроков и цену игры, применяя формулы (4.1.). Имеем:

р₁=(4–(–3))/(2+4–(–3)–(–3))=7/12, р₂=1–7/12=5/12,

q₁=(4–(–3))/(2+4–(–3)–(–3))=7/12, q₂=5/12,

v_S=(4×2–(–3)×(–3))/(2+4–(–3)–(–3))=–1/12.

Итак, решением игры является пара смешанных стратегий S_A *=(7/12,5/12), S_B *=(7/12,5/12), цена игры v_S =–1/12. Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая 1-ю стратегию (положить 1 руб.) с вероятностью 7/12, а 2-ю стратегию (положить 2 руб.) – с вероятностью 5/12.

Отрицательная цена игры v_S =–1/12 показывает, что при использовании игроками своих оптимальных стратегий, первый игрок проигрывает второму в каждой партии «в среднем» 1/12 рубля. Тем самым можно говорить об изначальной несправедливости условий игры.

4) Упрощение игр с помощью отбрасывания

доминируемых стратегий.

Стратегия А_i игрока А называется доминирующей над стратегией А_k (а стратегия А_k доминируемой стратегией А_i), если все элементы i -й строки платежной матрицы не меньше соответствующих элементов k -й строки, т. е. а_{i 1}³ a_{k 1}, a_{i 2}³ a_{k 2}, …, a_im ³ a_km (в том же смысле можно говорить и о доминировании строк).

Стратегия В_j игрока В называется доминирующей над стратегией В_l (а стратегия В_l - доминируемой стратегией В_j), если все элементы j -го столбца платежной матрицы не больше соответствующих элементов l -го столбца, т. е. a _{1 j} £ a _{1 l}, a _{2 j} £ a _{2 l},…, a_mj £ a_ml (здесь также можно говорить и о доминировании столбцов платежной матрицы).

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

Пример 2.5. Найдем оптимальное решение игры, заданной платежной матрицей

Результаты процесса отбрасывания доминируемых стратегий отобразим в таблице:

	В1	В2	В3	В4
А1		-2		-1
А2
А3		-1
А4

Комментарии:

1) Строка А ₂ доминирует над строкой А₁ (4³3, 0³–2, 6³5, 1³–1); следовательно, строку А ₁ отбрасываем (вычеркиваем).

2) В оставшейся части матрицы столбец В ₂ доминирует над столбцами В ₃ и В ₄ (0£6, –1£3, 3£7 и 0£1, –1£2, 3£4); следовательно, вычеркиваем столбцы В ₃ и В ₄.

3) Наконец, в полученной матрице строка А ₂ доминирует над строкой А ₃ (4³2, 2³–1); вычеркиваем строку А ₃.

Оставшаяся матрица

не имеет доминируемых стратегий и относится к классу игр 2х2.

Используя формулы (2.7), найдем оптимальные смешанные стратегии игроков в полученной игре, а также ее цену:

=(3–1)/(4+3–1–0)=2/6=1/3, =1–1/3=2/3, =(3–0)/(4+3–1–0)=1/2,

=1–1/2=1/2, =(4×3–0×1)/(4+3–1–0)=2.

Итак, =(1/3,2/3), =(1/2,1/2) – оптимальное решение игры, заданной матрицей . Учитывая вычеркнутые доминируемые стратегии игроков, запишем оптимальное решение исходной игры: S_A *=(0,1/3,0,2/3), S_B* =(1/2,1/2,0,0). Цена игры - та же v *=2.

3. Графический метод решения игр 2хn и mх2.

Рассмотрим подробно случай 2х n - игр. Пусть игрок А имеет в своем распоряжении две чистых стратегии, а игрок В – n чистых стратегий. Матрица выигрышей игрока А имеет вид:

.

Смешанная стратегия игрока А задается вектором S_А =(р ₁, р ₂), где р ₁+ р ₂=1, р ₁³0, р ₂³0. Положим р ₁= р, тогда р ₂=1- р, где р Î[0, 1]. Поэтому S_А =(р, 1- р), т. е. смешанная стратегия игрока А однозначно определяется екоторым числом р Î[0, 1].

Если игрок В применит свою чистую стратегию В_j (j =1,…, n), то средний выигрыш игрока А в одной партии при использовании стратегии S_A =(p, 1- p) определяется выражением H (S_A, B_j)= a _{1 j} × p + a _{2 j} ×(1- p)= z_j (p) при всех j =1,…, n..

Функции z_j (p) – линейные функции на отрезке р Î[0,1]. Изобразим их графики на рисунке.

Каждой чистой стратегии В_j игрока В соответствует своя прямая Н = z_j (p). Игрок В стремится к уменьшению своего проигрыша. Следовательно, при фиксированной стратегии S_A =(p,1- p) его противника игрок В выбирает ту стратегию В_j, для которой график функции Н = z_j (p) при данном р расположен ниже других.

Таким образом, наименьшим выигрышам игрока А при неблагоприятных для него действиях игрока В соответствует нижняя огибающая всех прямых Н = z_j (p) на рисунке.

С другой стороны, целью игрока А является достижение наибольшего гарантированного выигрыша при любых действиях партнера. Значит, он будет выбирать ту стратегию S_A *=(p *,1- p *), которая определяется точкой р *, соответствующей максимуму нижней огибающей. Именно эта стратегия и является оптимальной для игрока А, а само значение максимума огибающей определяет цену игры.

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

Случай 1. Нижняя огибающая имеет ровно одну максимальную точку (р *, Н *). При этом заметим, что если в исходной матрице отсутствуют доминируемые стратегии, то точка максимума р * является внутренней точкой отрезка [0, 1].

Итак, пусть р *Î(0, 1). Тогда в пиковой точке нижней огибающей пересекается не менее двух прямых, из которых одна имеет положительный наклон, а другая – отрицательный.

Выделим любую пару таких прямых, например, z = z_k (p) и z =z_l(p), которым соответствуют чистые стратегии В_k и В_l. Нетрудно показать, что для минимизации собственного проигрыша игроку В достаточно использовать только эти стратегии, а от применения других чистых стратегий воздержаться. Тем самым получим вспомогательную игру с платежной матрицей:

(матрица получается из Н вычеркиванием всех столбцов, кроме k -го и l -го). Оптимальная стратегия S_B =(q ₁, q ₂) игрока В и цена игры в получившейся игре 2х2 могут быть найдены с помощью формул (2.7). Тогда оптимальной стратегией игрока В в первоначальной задаче является стратегия S_B *, в которой k -й и l -й компоненты равны соответственно q ₁ и q ₂, а остальные компоненты равны нулю. Цена вспомогательной игры совпадает с ценой v_S исходной игры. Аналогично могут быть рассмотрены и другие пары прямых, проходящих через пиковую точку и имеющих разнознаковые наклоны.

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

Случай 2. Нижняя огибающая содержит горизонтальный участок, соответствующий отрезку [ p ₁*, p ₂*] на оси абсцисс.

Тогда любая стратегия вида S_A *=(p, 1-p), где р Î[ p ₁*, p ₂*], является оптимальной для игрока А. Игрок В обладает единственной чистой стратегией, которой соответствует прямая, содержащая данный горизонтальный участок.

Пример 2.6. Решим игру с платежной матрицей:

Сначала упростим матрицу с помощью отбрасывания доминируемых стратегий. Стратегия В ₆ доминирует над стратегиями В ₄, В ₅ и В ₇. Следовательно, вычеркиваем 4-й, 5-й и 7-й столбцы. Стратегия В ₂ доминирует над стратегией В ₃. Поэтому 3-й столбец матрицы также можно отбросить.

Оставшаяся матрица

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

Смешанная стратегия А имеет вид S_A =(p, 1-p). Составим функции средних выигрышей игрока А при условии, что игрок В выбирает свои чистые стратегии , , игре с матрицей :

Н ₁=0× p +13×(1- p)=13-13× p, Н ₂=5× p +4×(1- p)=4+ p, Н ₃=10× p +1×(1-p)=1+9×p.

Построим графики этих функций на отрезке р Î[0, 1].

Выделяем нижнюю огибающую этих графиков. Находим самую высокую точку этой огибающей. Эта точка – результат пересечения прямых Н =13 - 13 р и Н =4+ р. Найдем ее координаты аналитически. Для этого решим уравнение 13-13× р =4+ р. Получим 14× р =9, откуда р *=9/14»0.642, 1- р *=5/14»0.358. Следовательно, оптимальная смешанная стратегия игрока А имеет вид S_A *=(9/14,5/14).

Подставляя значение р *=9/14 в любую из функций Н =13 - 13 р или Н =4+ р, находим цену игры v_S = 13 - 13×9/14 = 65/14» 4.642.

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

q ₁=(4 - 5)/(4+0 - 13 - 5)=1/14»0.074, q ₂=1 - 1/14=13/14»0.926.

Цена игры =(0×4+13×5)/(4+0 - 13 - 5)=65/14»4.642 совпадает с ранее найденной ценой v_S. Учитывая вычеркнутые стратегии игрока В, окончательно запишем оптимальные стратегии игроков для исходной игры S_A *=(9/14,5/14), S_B *=(1/14,13/14,0,0,0,0,0); цена игры v_S =65/14.

Решение игры m х2 производится аналогично. Перечислим лишь основные этапы решения. Пусть исходная игра задается матрицей

.

Будем искать смешанную стратегию игрока В в виде S_В =(q, 1- q)

Для каждой стратегии А_i игрока А находим средние выигрыши

H (A_i, S_B)= a_{i 1} q + a_{i 2}(1- q) (i =1,2,…, m).

Строим графики этих выигрышей на координатной плоскости.

Выделяем верхнюю огибающую построенных графиков, соответствующую наименее благоприятным для игрока В ситуациям.

Отмечаем точку минимума этой огибающей q *, которая определяет оптимальную стратегию игрока В; при этом сам минимум задает цену игры v.

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

Для полученной игры 2х2 находим оптимальную стратегию игрока А, применяя формулы (2.7).

Записываем оптимальную стратегию игрока А, учитывая вычеркнутые строки.

Метод сведения матричной игры

к задаче линейного программирования.

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

Пусть имеется игра m х n без седловой точки и без доминируемых стратегий, заданная матрицей

.

Априорно допустим, что цена этой игры положительна. Это значение заранее неизвестно, но, согласно свойству 2 из п.2.2, v_S ³ a, где a - нижняя цена игры. Так что при a >0 условие v_S >0 выполнено. Если же a £0, то выполнение такого условия можно гарантировать, прибавив, например, ко всем элементам матрицы Н число с >- a и получив матрицу Н¢ новой игры. Согласно свойству 1 из п. 2.2, новая игра имеет то же самое решение, что и исходная игра, а ее цена v_S '= v_S + c.

Итак, пусть v_S >0. Мы хотим найти две оптимальные смешанные стратегии S_A *=(р ₁,…, р_m) и S_B *=(р ₁,…, р_n), дающие каждому игроку максимально возможные для него средние выигрыши. Найдем S_A *. Уже известно, что, если игрок А применяет свою оптимальную стратегию, то игрок В не может улучшить свое положение, отступая от своей оптимальной стратегии: H (S_A *, S_B)³ H (S_A *, S_B *)= v_S для всех S_B (проигрыш В будет не меньше, чем v_S). В частности, если игрок В пользуется какой-либо чистой стратегией В_j, то:

H (S_A *, B_j)= a _{1 j} × p ₁+…+ a_mj×p_m ³ v_S при всех j =1,…, n.

Получим следующую систему неравенств:

(2.8)

Так как v_S >0, то при почленном делении левых и правых частей неравенств (2.8) на v_S знаки неравенств не изменятся. Вводя, кроме того, обозначения x_j = p_j/v_S, перепишем систему (2.8) в виде:

(2.9)

Условие р ₁+ р ₂+…+ р_m =1 равносильно условию x ₁+ x ₂+…+ x_m =1/ v_S.

Но v_S – гарантированный выигрыш игрока А. Целью игрока А в игре является максимизация этого значения и, следовательно, минимизация выражения 1/ v_S. Получили следующую задачу линейного программирования:

Найти неотрицательные значения x ₁, x ₂,…, x_m, которые удовлетворяют линейным ограничениям – неравенствам (2.9) и обращают в минимум целевую функцию L = x ₁+ x ₂+…+ x_m.

Полученная задача может быть решена, например, симплекс-методом. Пусть (x ₁*, x ₂*,…, x_m *) - некоторое решение этой задачи, L * - минимальное значение целевой функции L. Тогда цена игры v_S =1/ L *, а компоненты оптимальной стратегии игрока А равны: p_j *= x_j */ L * (j =1,…, m).

Оптимальная стратегия игрока В находится аналогично. В результате приходим к задаче линейного программирования, двойственной к первой:

y ₁+ y ₂+…+ y_n ® max

(2.10)

Решение (y ₁*, y ₂*,…, y_n *) этой задачи и компоненты q ₁*, q ₂*,…, q_n * оптимальной стратегии игрока В связаны соотношениями: q_i *= y_i */ L *, где L * - максимальное значение целевой функции задачи (2.10), совпадающее с минимальным значением предыдущей задачи.

Пример 2.7. Найти решение игры, заданной матрицей

.

Во-первых, заметим, что данная игра не имеет доминируемых стратегий, так что сокращение размерности матрицы невозможно. Далее проверим, не имеет ли матрица седловую точку. Найдем нижнюю и верхнюю цены игры:

, . Так как a < b, то седловая точка отсутствует. Приступаем к поиску решения игры в смешанных стратегиях, используя метод сведения игры к задаче линейного программирования.

Прибавим ко всем элементам матрицы Н модуль ее наименьшего отрицательного элемента, т. е. 2. Получим матрицу

,

которая задает игру с заведомо положительной ценой v_S ¢. Для нахождения оптимальной смешанной стратегии игрока А составим следующую задачу линейного программирования:

L = x ₁+ x ₂+ x ₃ ® min

(2.11)

Для нахождения оптимальной стратегии игрока В составим двойственную задачу:

L ₁= y ₁+ y ₂+ y ₃ ® max

(2.12)

Симплекс-методом удобнее решать задачу (2.12). Опуская процесс расчетов этим методом, запишем лишь результат: у ₁*=1/4, у ₂*=5/4, у ₃*=0 – решение задачи (2.12), максимальное значение целевой функции L ₁*=3/2. Отсюда находим компоненты оптимальной смешанной стратегии игрока В: q ₁*=(1/4):(3/2)=1/6, q ₂*=(5/4):(3/2)=5/6, q ₃*=0; цена игры v_S ¢=1/ L ₁*. При решении задачи линейного программирования симплекс-методом в итоговой симплекс-таблице содержится также и решение двойственной задачи, в нашем случае - задачи (2.11): х ₁*=0, х ₂*=1/2, х ₃*=1. Учитывая, что L *= L ₁*, отсюда получим: p ₁*=0:(3/2)=0, p ₂*=(1/2):(3/2)=1/3, p ₃*=1:(3/2)=2/3. Согласно свойству 1 решения матричных игр (п.2.3), оптимальные смешанные стратегии исходной игры совпадают с найденными оптимальными стратегиями: S_A *=(0,1/3,2/3), S_B *=(1/6,5/6,0). Цена v_S исходной игры и найденная цена v_S ¢ вспомогательной игры связаны соотношением v_S ¢= v_S +2. Поэтому v_S =2/3-2=-4/3.

4.5. Итерационный метод Брауна – Робинсон.

Основная идея метода состоит в следующем.

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

Рассмотрим реализацию этого метода на примере.

Пример 2.8. Найти приближенное решение игры, заданной матрицей

.

Игра не имеет доминируемых стратегий и поэтому не может быть сведена к игре меньшей размерности. Нижняя цена игры a =4, А ₃ - соответствующая максиминная стратегия игрока А; верхняя цена игры b =6, В ₂ – соответствующая минимаксная стратегия игрока В. Оформим расчеты методом Брауна в виде таблицы.

k	Ai	B 1	B 2	B 3	Bj	A 1	A 2	A 3	v *	v *	vS
1	2	3	4	5	6	7	8	9	10	11	12
	A3			4*	B3	8*			4.00	8.00	6.00
	A1	10*			B1	11*			5.00	5.50	5.25
	A1	13*			B1		20*		4.33	6.67	5.55
	A2		21*		B2		24*		5.25	6.00	5.63
	A2			24*	B3	28*			4.80	5.60	5.20
	A1		31*		B2	34*			5.17	5.67	5.32
	A1	37*			B1		39*		5.29	5.86	5.58
	A2		41*		B2			44*	5.13	5.50	5.31
	A3		46*		B2	49*			5.11	5.37	5.24
	A1		52*		B2	55*			5.20	5.50	5.35
…	…	…	…	…	…	…	…	…	…	…	…

Здесь:

· k – номер партии (пары выборов игроками своих стратегий);

· А_i – стратегия, выбранная игроком А в этой партии;

· в следующих трех столбцах – «накопленный выигрыш» за первые k партий при тех стратегиях, которые применяли игроки в предыдущих партиях и при стратегиях В ₁, В ₂, В ₃ в данной партии (получается прибавлением элементов соответствующей строки к тому, что было строкой выше);

· из этих накопленных выигрышей выделяется минимальный (если их несколько, то – любой из них), выделенное число определяет ответный выбор игрока В в данной партии – он выбирает ту стратегию, которая соответствует выделенному числу; таким образом, определяется оптимальная в данной партии стратегия В_j игрока В;

· в следующих трех столбцах дается накопленный выигрыш за k партий соответственно при стратегиях А ₁, А ₂, А ₃ игрока А (получается прибавлением столбца В_j к тому, что было строкой выше); из этих значений выделяется максимальное; оно определяет выбор стратегии игрока А в следующей партии;

· v_* - нижняя оценка цены, равная минимальному накопленному выигрышу, деленному на k;

· v^* - верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k;

· v_S – среднее арифметическое v_* и v ^*.

Рассмотрим подробно несколько шагов методом Брауна в данной игре. В 1-й партии игрок А может выбрать любую из своих чистых стратегий, но лучше, если это будет максиминная стратегия А₃ (вносим это выражение во 2-й столбец). Этой стратегии соответствует 3-я строка матрицы выигрышей (7 5 4), соответствующих стратегиям В₁, В₂, В₃ игрока В (заносим их в 3-й, 4-й и 5-й столбцы). Среди этих чисел выделяем значком "_*" минимальное. Оно соответствует наиболее выгодной для игрока В стратегии В₃ в этой партии. Этой стратегии соответствует 3-й столбец платежной матрицы (8 2 4)^Т. Заносим эти значения в 7-й, 8-й и 9-й столбцы, выделяя среди них значком ^* максимальное, соответствующее наибольшему выигрышу игрока А. Поэтому в начале 2-й партии игрок А выбирает стратегию А ₁, которой соответствует 1-я строка (3 6 8) матрицы Н. «Накопленный выигрыш» при этой и предыдущей стратегиях равен (3 6 8) + (7 5 4) = (10 11 12). Именно эти значения и заносим в 3-й, 4-й и 5-й столбцы. Минимальному из них значению соответствует стратегия В ₁, т. е. 1-й столбец (3 9 7)^Т. С учетом предыстории «накопленный выигрыш» игрока А равен (3 9 7)^Т + (8 2 4)^Т = (11 11 11)^Т. Заполняем этими значениями 7-й, 8-й и 9-й столбцы таблицы и т. д.

В таблице приведены первые 10 шагов методом Брауна-Робинсон. В результате игрок А применял 5 раз стратегию А ₁, 3 раза - стратегию А ₂, 2 раза – стратегию А ₃; игрок В – 3 раза стратегию В ₁, 5 раз – стратегию В ₂, 2 - раза стратегию В ₃. Поэтому оптимальные стратегии игроков, приближенно вычисленные по относительным частотам использования своих чистых стратегий, имеют вид: S_A ^p=(0.5, 0.3,0.2), S_B ^p=(0.3,0.5,0.2).

Нижняя и верхняя оценки цены игры равны соответственно v _*=5.2 и v ^*=5.5 (вычисляются делением соответственно минимального и максимального накопленных выигрышей (52 и 55) на количество сыгранных партий (10)). Приближенная цена игры v_S ^p=(5.2+5.5)/2=5.35.

После 20-ти шагов методом Брауна аналогичные результаты выглядят следующим образом: приближенные оптимальные стратегии S_A ^p=(0.4,0.1,0.5), S_B ^p=(0.25,0.6,0.15), приближенная цена игры v_S ^p=5.275. При этом точное решение игры, которое может быть получено методом сведения игры к задаче линейного программирования, имеет вид: S_A *=(0.4,0,0.6), S_B *=(0.2,0.8,0), v_S =5.4.

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

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

2) Сходимость приближенных решений, рассчитанных методом Брауна, к точному решению происходит довольно медленно.

2.5. Игры с природой.

До сих пор рассматривались модели таких конфликтных ситуаций, в которых противники были равноправны и, стремясь к противоположным целям, одинаково придерживались осторожного принципа минимакса. Однако в реальной действительности довольно часто возникают качественно иные ситуации конфликта двух сторон. Они по-прежнему формально описываются матрицей выигрыша Н =|| а_ij || _{i =1,…, m , j =1,…, n} одного из игроков (А), который, как обычно, выбирает свои стратегии сознательно, стремясь к увеличению своего выигрыша. Но второй игрок (В) особенный. О нем известно, что:

- либо он придерживается фиксированной смешанной стратегии S_B =(q ₁,…, q_n) (случай стохастической определенности),

- либо о том, чем именно руководствуется игрок В, вообще ничего не известно (случай неопределенности).

Такие ситуации называются «играми с природой», игрок В («природа») чаще всего представляет собой не конкретное лицо, а объективную реальность. Его стратегиями В_j служат состояния «природы» (тип погодных условий, спрос на определенную продукцию и. т. п.). Целью исследования такой игры является поиск разумных правил выбора игроком А каких-либо из своих возможных стратегий.

Рассмотрим некоторые способы такого выбора в зависимости от специфики той или иной ситуации.

Случай 1. Пусть смешанная стратегия S_B =(q ₁,…, q_n) «природы» известна, т. е. известны вероятности их состояний В ₁,…, В_n (например, на основании статистических данных).

Вычислим средние выигрыши (математические ожидания) игрока А при применении им каждой из его чистых стратегий:

при А ₁ имеем Н (A ₁, S_B) = a ₁₁× q ₁+…+ a _{1 n} × q_n = v ₁,

……………………………………………

при А_m имеем Н (А_m, S_B) = a_{m 1}× q ₁+…+ a_mn × q_n = v_m.

Остается сравнить полученные значения и выбрать среди них наибольшее v *=max(v ₁,…, v_m). Чистая стратегия А_{i *}, соответствующая этому значению, является оптимальной для игрока А. При этом нетрудно показать, что применение каких-либо смешанных стратегий игроку А не выгодно, так как это может привести только к уменьшению среднего выигрыша v *.

Случай 2. Пусть стратегии «природы» неизвестны, но они по-прежнему могут быть смешанными, т. е. количество партий с природой неограниченно. Рассмотрим два возможных подхода к решению этой задачи.

а) Принцип недостаточного основания Лапласа. Если нет никаких оснований считать, что какая-либо стратегия «природы» имеет большую частоту, чем любая другая стратегия, то мы можем предположить, что вероятности всех стратегий В ₁,…, В_n одинаковы: q ₁=…= q_n =1/ n. Тогда гипотетические средние выигрыши игрока А при использовании его чистых стратегий А ₁,…, А_m определяются соответственно равенствами:

v₁^L = 1/ n ×(a ₁₁+…+ a _{1 n} ), …, v_m^L = 1/ n ×(a_{m 1}+…+a_mn).

Сравнивая полученные значения, выбираем среди них наибольшее v^L *=(v ₁ ^L,…, v_m^L). Стратегия А_{i *}, соответствующая этому значению, объявляется оптимальной.

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

Пример 2.9. Сельскохозяйственное предприятие планирует посев трех культур – А ₁, А ₂, А ₃. Считаем, что при прочих равных условиях урожаи культур зависят от погоды, а сама погода может иметь 3 различных состояния: В ₁- засушливое лето, В ₂ – нормальное лето, В ₃ – дождливое лето, Расчеты прибыли с/х предприятия (в у. е.) в зависимости от состояний погоды сведены в матрицу

.

Найти оптимальную стратегию предприятия, если: а) вероятности состояний В ₁, В ₂, В ₃ погоды известны q ₁=0.2, q₂=0.3, q ₃=0.5; б) придерживаться принципа недостаточного основания Лапласа; в) ориентироваться на наименее благоприятную погоду.

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

а) В данном случае смешанная стратегия «природы» известна S_B =(0.2,0.3,0.5). Найдем средние прибыли предприятия при использовании им оставшихся стратегий А ₂ и А ₃: H (A ₂, S_B)=8×0.2+5×0.3+3×0.5=4.6, H (A ₃, S_B)=2×0.2+3×0.3+7×0.5=4.8. Второе значение больше, поэтому следует выбрать стратегию А ₃.

б) В силу отсутствия информации о состояниях «природы», априорно примем q ₁= q ₂= q ₃=1/3. В случае использования стратегий А ₂ и А ₃ получим следующие оценочные «выигрыши»: v ₂ ^L =1/3×(8+5+3)=16/3, v ₃ ^L =1/3×(2+3+7)=4. Здесь, напротив, больше первое значение, и оптимальной стратегией является А ₂.

в) Ориентация на наименее благоприятную погоду предполагает рассмотрение «природы» как разумного и равноправного противника, стремящегося минимизировать прибыль предприятия. Поэтому оптимальная стратегия предприятия может быть найдена обычными методами решения матричных игр, например, графическим методом. Опуская промежуточные расчеты, запишем лишь результат решения этой «игры»: S_A =(2/3,1/3) - оптимальная смешанная стратегия предприятия, v_S =13/3»4.33 - цена «игры». Интерпретировать этот результат можно следующим образом: с/х предприятию рекомендуется 2/3 всех площадей засеять культурой А ₂ и 1/3 площадей – культурой А ₃. При этом можно гарантировать среднюю прибыль в 4.33 у.е.

Случай 3. Предположим, что, как и в случае 2, ничего о состояниях природы неизвестно. Однако игра с «природой» проводится один лишь раз, так что употребление смешанных стратегий ни игроком А, ни «природой» не имеет смысла. В этом случае при поиске оптимального решения чаще всего используются критерии Вальда, Сэвиджа и Гурвица.

А) Критерий Вальда (максиминный критерий).

Игрок А исходит из пессимистической оценки ситуации и предполагает, что «природа» играет с ним в антагонистическую игру. Его цель -–гарантированный выигрыш или нижняя цена игры

Его оптимальная стратегия - максиминная стратегия А_i*, при которой достигается W (см. п.2.2).

Б) Критерий Сэвиджа (критерий минимального риска).

Риском r_ij игрока А при пользовании стратегией А_i в условиях состояния «природы» B_j называется разность между максимально возможным выигрышем игрока А при данном состоянии природы и выигрышем а_ij при выбранной стратегии А_i, т. е. r_ij=b_j - a_ij, где - максимальный элемент в j -м столбце. Риск – это «плата за отсутствие информации». В результате получаем матрицу, составленную из чисел r_ij, - матрицу риска R.

Оптимальной стратегией по критерию Сэвиджа является та стратегия А_{i *}, при которой величина риска имеет минимальное значение в самой неблагоприятной ситуации:

В) Критерий Гурвица (критерий учета степени оптимизма).

Здесь представляется логичным, чтобы при выборе решения вместо двух крайностей в оценке событий ситуации придерживаться некоторого компромисса, учитывающего возможность как наихудшего, так и наилучшего поведения «природы». В соответствии с этим критерием следует выбрать ту стратегию А_{i *}, при которой достигается следующий максимум:

где t Î[0,1] – субъективный показатель оптимизма, обычно близкий к 0,5.

Заметим, что при t =0 (крайний пессимизм!) критерий Гурвица переходит в критерий Вальда.

Пример 2.10. Игра с «природой» задана матрицей

.

Найдите оптимальные стратегии, руководствуясь критериями Вальда, Сэвиджа и Гурвица с t =0.6.

Для применения перечисленных критериев удобнее выполнить предварительные расчеты в таблице:

	В 1	В 2	В3	minj aij	maxj aij
A 1
A 2
A 3
A 4
bj=maxi aij

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

Найденный максимум достигается при i =3, т.е., исходя из критерия Вальда, следует осуществлять стратегию А ₃.

б) Критерий Сэвиджа. Сначала составим матрицу рисков R. Для этого определяем максимальные элементы в каждом столбце матрицы Н (нижняя строка таблицы). Затем находим элементы матрицы R по формуле r_ij = b_j - a_{i j}. Получим матрицу:

.

Затем находим

Минимум достигается при i =2 и i =3. Значит, по критерию Сэвиджа оптимальными являются стратегии А ₂ и А ₃.

в) Критерий Гурвица с t =0.6. Найдем минимальные и максимальные числа в каждой строке матрицы Н (последние два столбца таблицы). Для каждого номера i =1, 2, 3, 4 находим значение:

при t =0.6.

Имеем: G ₁=0.4×15+0.6×30=24, G ₂=0.4×20+0.6×75=53,

G ₃=0.4×25+0.6×80=58, G ₄=0.4×5+0.6×85=53.

Находим максимальное из полученных значений. Это – G ₃=58. Оно соответствует стратегии А ₃, которое и является оптимальной по критерию Гурвица.

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

Список рекомендуемой литературы.

Вентцель Е.С. Элементы теории игр. – М.: Наука, 1961.

Вентцель Е.С. Исследование операций. Задачи, принципы, методология. - М.: Наука, 1980.

Воробьев Н.Н. Теория игр. Лекции для экономистов-кибернетиков. – Л., Изд-во Ленингр. ун-та, 1974.

Зайченко Ю.П. Исследование операций. - Киев: Выща школа, 1986.

Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник. – М.: МГУ им. М.В. Ломоносова, Изд-во «ДИС», 1998.

Исследование операций в экономике: Учебное пособие / Под ред. Кремера Н.Ш./ - М.: Банки и биржи, ЮНИТИ, 1999.

Карлин С. Математические методы в теории игр, программировании и экономике. – М.: Мир, 1964.

Косоруков О.А., Мищенко А.В. Исследование операций: Учебник. - М.: Экзамен, 2003.

Моделирование марковских процессов и элементы теории массового обслуживания: Методические указания / Сост. М.Б. Ермолаев. – Иваново: Иван. гос. хим.-технол. ун-т, 2005.

Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. – М.: Наука, 1970.

Оуэн Г. Теория игр. – М.: Наука, 1971.

Экономико-математические методы и модели: Учебное пособие / В.Ю.Киселев, Иван. гос. энерг. ун-т. – Иваново, 1998.

Элементы теории игр: Методические указания / Сост. М.Б. Ермолаев. – Иваново: Иван. гос. хим.-технол. ун-т, 2001.