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