Матричные игры с нулевой суммой
Рассмотрим парную игру с нулевой суммой. Пусть игрок I имеет стратегий (1, 2,…,m), а игрок II - стратегий (1, 2,…, n). Такая игра называется матричной игрой размерности .
Предположим, игрок I выбрал одну из своих возможных стратегий ( ), а игрок II, не зная результата выбора игрока I, - стратегию ( ). Выигрыши игрока I и игрока II в результате выбора стратегий удовлетворяют соотношению ; таким образом, если ввести обозначение , то .
Элементы для каждой пары стратегий считаются известными и записываются в платежную матрицу (табл. 5.1), строки которой соответствуют стратегиям игрока I, а столбцы - стратегиям игрока II. Каждый положительный элемент матрицы определяет величину выигрыша игрока I и, соответственно, проигрыша игрока II при применении ими соответствующих стратегий. Естественно, целью игрока I является максимизация своего выигрыша, тогда как игрока II - минимизация своего проигрыша.
Таблица 5.1Платежная матрица парной игры с нулевой суммой
II
I
|
|
| …
| n
|
|
|
| …
|
|
|
|
| …
|
| …
| …
| …
| …
| …
| m
|
|
| …
|
|
Решение парных матричных игр с нулевой суммой. Принцип минимакса
Используя платежную матрицу парной игры с нулевой суммой (табл. 5.1), определим наилучшую стратегию игрока I среди стратегий i ( i = ) и наилучшую стратегию игрока II среди стратегий j (j= ).
В теории игр предполагается, что противники, участвующие в игре, одинаково разумны, и каждый из них делает все возможное для того достижения своей цели.
Проанализируем стратегии игрока I. Игрок I, выбирая стратегию , должен рассчитывать, что игрок II ответит на нее той из своих стратегий , для которой выигрыш игрока I будет минимальным. Найдем минимальное число в каждой строке матрицы и, обозначив его , запишем в добавочный столбец платежной матрицы (см. табл. 5.2):
. (5.1)
Зная числа (свои выигрыши при применении i-х стратегий и разумном ответе игрока II), игрок I должен выбрать такую стратегию, для которой максимально. Обозначив это максимальное значение как
(т.е. и используя (5.1), получим
(5.2)
Таблица 5.2
II
I
|
|
| . . .
| n
|
|
|
|
| . . .
|
|
|
|
|
| . . .
|
|
| . . .
| . . .
| . . .
| . . .
| . . .
| . . .
| m
|
|
| . . .
|
|
|
|
|
| . . .
|
|
|
Величина представляет собой гарантированный выигрыш, который может обеспечить себе игрок I; она называется нижней ценой игры (максимином). Стратегия, обеспечивающая получение нижней цены игры , называется максиминной стратегией. Если игрок I будет придерживаться своей максиминной (перестраховочной) стратегии, то ему гарантирован выигрыш, не меньший при любом поведении игрока II.
В свою очередь, второй игрок стремится уменьшить свой проигрыш или, что то же самое, выигрыш игрока I обратить в минимум. В связи с этим, для выбора своей наилучшей стратегии он должен найти максимальное значение выигрыша игрока I в каждом из столбцов и среди этих значений выбрать наименьшее. Обозначим через максимальный элемент в каждом столбце и запишем эти элементы в дополнительной строке табл. 5.2. Наименьшее значение среди обозначим через ; эта величина представляет собой верхнюю цену игры (минимакс), которая определяется по формуле
. (5.3)
Стратегия игрока II, обеспечивающая «выигрыш» , является его минимаксной стратегией. Выбор минимаксной стратегии игроком II гарантирует ему проигрыш не больше .
В теории игр доказывается, что для нижней и верхней цены игры всегда справедливо неравенство
Игры, для которых нижняя цена равна верхней, т.е. , называются играми с седловой точкой.
Общее значение нижней и верхней цены игры в играх с седловой точкой называется чистой ценой игры , а стратегии , позволяющие достичь этого значения, - оптимальными чистыми стратегиями; элемент является одновременно минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии определяют в игре положение равновесия, поскольку каждому из игроков невыгодно отходить от своей оптимальной стратегии. Чистую цену игры в игре с седловой точкой игрок I не может увеличить, а игрок II ‑ уменьшить. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.
Игры без седловых точек
Итак, если матрица игры содержит седловую точку, то ее решение находится по принципу минимакса. Рассмотрим методику решения игры, в платежной матрице которой отсутствует седловая точка. Применение минимаксных стратегий каждым из игроков обеспечивает первому выигрыш не меньше , а второму проигрыш не больше . Учитывая, что , естественно для игрока I желание увеличить выигрыш, а для игрока II – уменьшить проигрыш. Поиск такого решения приводит к применению сложной стратегии, состоящей в случайном применении двух и более чистых стратегий с определенными вероятностями. Такая сложная стратегия в теории игр называется смешанной. Смешанные стратегии игроков I и II будем обозначать, соответственно,
и
где , ‑ вероятности применения соответствующих чистых стратегий. Очевидно, должны выполняться условия нормировки для вероятностей
Одна из основных теорем теории игр утверждает, что любая конечная игра двух лиц с нулевой суммой имеет, по крайней мере, одно решение, возможно, в смешанных стратегиях. Из этой теоремы следует, что каждая конечная игра имеет цену. Обозначим ее так же, как чистую цену игры, через . Цена игры – средний выигрыш, приходящийся на одну партию, – всегда удовлетворяет условию , т.е. лежит между нижней ( ) и верхней ( ) ценами игры. Следовательно, каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях, так же как и решение в чистых стратегиях, характеризуется тем, что каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.
Стратегии игроков, входящие в их оптимальные смешанные стратегии, называются активными.
5.5 Использование линейной оптимизации при решении матричных игр
Пусть игра не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует .
Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что >0.
Будем искать решение игры в смешанных стратегиях
;
Применение игроком I оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры .
Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I – свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен
Учитывая, что не может быть меньше , запишем условия:
(5.4)
Разделив левую и правую части каждого из неравенств (5.4) на цену игры , получим
(5.5)
При использовании обозначений
(5.6)
неравенства (5.5) примут вид
где, очевидно, все , так как .
Из равенства
и в силу определения (5.6) следует, что переменные ( ) удовлетворяют условию
Учитывая, что игрок I стремится максимизировать , получаем линейную функцию
(5.8)
Таким образом, задача решения игры свелась к следующей задаче линейной оптимизации: найти неотрицательные значения переменных минимизирующие линейную функцию (5.8) и удовлетворяющие ограничениям (5.7).
Из решения задачи линейной оптимизации легко найти цену игры и оптимальную стратегию игрока I:
В свою очередь, оптимальная стратегия игрока II
может быть найдена из выражения
где - неотрицательные переменные задачи линейной оптимизации
которая является двойственной по отношению к задаче, представленной условиями (5.7) и (5.8).
В этой системе неравенств переменные
Таким образом, оптимальные стратегии
и
игры с платежной матрицей ( ) могут быть найдены путем решения симметричной пары двойственных задач линейной оптимизации.
Исходная задача Двойственная задача
Цена игры и вероятности применения стратегий игроками I и II равны
5.6 Задачи для самостоятельного решения
Путем сведения двойственных задач линейного программирования найти оптимальные смешанные стратегии и цену игры матричных игр с такими платежными матрицами:
1)
| -8
|
| 2)
| -2
| -5
| 3)
| -1
|
| 4)
|
| -6
| 5)
| -3
|
|
|
| -8
|
| -4
|
|
|
| -4
|
| -3
|
|
|
| -1
|
6)
| -3
|
|
| 7)
|
|
|
| 8)
|
|
| -1
| 9)
|
|
| -1
|
| -5
|
| -3
|
|
|
|
|
|
|
|
|
| -1
|
|
|
|
| -9
|
|
|
|
|
|
|
| -1
|
|
| -2
| -3
|
|
ЛИТЕРАТУРА
1. Сборник задач по высшей математике для экономистов: Учебное пособие /Под ред. В.И.Ермакова. – М.: ИНФРА-М, 2001 (и поздние издания)
2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн: Вышэйшая школа,2001
3. Налбандян Ю.С. Руководство к решению задач по линейной алгебре. Метод. указания для студентов специальности «Менеджмент организаций». - Ростов-на-Дону: 2007.
4. Общий курс высшей математики для экономистов: Учебник/Под ред. В.И.Ермакова. – М.: ИНФРА-М, 2000 (и поздние издания).
5. Исследование операций в экономике / Под ред. Н.Ш.Кремера – М.: ЮНИТИ, 1997 (и поздние издания).
6. Солодовников А.С., Бабайцев П.А., Браилов А.В Математика в экономике. Ч.1. М.: Финансы и статистика, 2001
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|