Автор работы: Пользователь скрыл имя, 01 Марта 2013 в 15:21, доклад
Теория игр рассматривает ситуации, при которых сталкиваются интересы двух или более сторон, преследующих различные цели. Такие ситуации называют конфликтными. Сами эти стороны, участвующие в конфликте, называют игроками. Игроками могут быть как отдельные лица, так и группы лиц (партнёры в бизнесе, фирмы и т. д.). Последовательные действия каждого из игроков зависят от действий, предпринятых ранее другими игроками. Таким образом, теория игр – это математическая теория, изучающая конфликтные ситуации.
Везде в дальнейшем, если не оговорено противное под множеством стратегий игрока i будем подразумевать множество его смешанных стратегий. В противном случае будем особо отмечать, что рассматриваются чистые стратегии.
Пример 12. Рассмотрим матричную игру:
Очевидно, игра относится к классу не полностью определённых игр. В ней нет седловой точки в чистых стратегиях. Допустим, что первый игрок выбирает первую стратегию с вероятностью и вторую стратегию с вероятностью . Пусть второй игрок выбирает первую стратегию. Тогда средний ожидаемый выигрыш первого игрока равен . Изобразим на рисунке выигрыши при чистых стратегиях первого игрока отрезками и . Тогда при смешанной стратегии выигрыш будет равен длине отрезка :
Действительно, из подобия треугольников и следует:
.
Следовательно, отрезок показывает выигрыш первого игрока при выборе им смешанной стратегии и выборе вторым игроком чистой первой стратегии.
Аналогично можно построить рисунок для случая выбора вторым игроком чистой второй стратегии:
Теперь соединим эти два чертежа:
При выборе вторым игроком смешанной стратегии выигрыш первого игрока будет равен CD, где точка D принадлежит отрезку . Максминная стратегия первого игрока говорит о том, что минимальный (по различным стратегиям второго игрока) гарантированный выигрыш первого игрока (ломанная ) должен быть максимален (по различным стратегиям первого игрока). Максимум достигается в точке N, определяемой из системы уравнений:
Цена игры составляет .
Заметим, что координаты точки N можно получить также из решения задачи линейного программирования на максимум:
Аналогичным образом можно решать матричные игры и .
Рассмотрим матричную игру mxn с платёжной матрицей U. Пусть у игроков A и B имеются в распоряжении соответственно m и n чистых стратегий: и .
Пусть – произвольные смешанные стратегии игроков A и B, а v – платеж, получаемый игроком A от игрока B в конце игры. По аналогии с двумерным случаем задача эквивалентна задаче линейного программирования на максимум величины v на допустимом множестве, задаваемом системой неравенств:
Добавив ограничения неотрицательности и нормировки на p, получим:
Переменными в задаче являются . Целевая функция .
Если v>0, то размерность задачи линейного программирования можно уменьшить на единицу, введя новые переменные :
Оптимумом в задаче является нижняя цена игры .
Если условие v>0 не выполнено, то всегда можно перейти к игре с постоянной суммой, прибавив к матрице игры некоторую положительную константу, так чтобы это условие выполнялось. При этом на ту же константу увеличится и цена игры. Это однако не повлияет на решение игры (выбор стратегий). Нетрудно убедиться, что и более общее линейное преобразование платежной матрицы , где a>0; b – произвольные постоянные, не изменяют решения игры, а цена игры изменяется по тому же правилу: :
Пример 13. Решить игру:
Решение.
Решая эту задачу линейного программирования симплекс–методом, можно получить: . Из симметричности матрицы игры вытекает, что оптимальная стратегия второго игрока равна . Цена игры: v=0.
Возвращаясь к задаче линейного программирования , построим двойственную к ней задачу:
К этой же задаче мы пройдем путём рассуждений с позиций второго игрока, выбирающего свою смешанную стратегию так, чтобы при чистых стратегиях первого игрока проиграть не больше платежа v. Оптимальной будет такая стратегия второго игрока, которая минимизирует платеж v. Путём ввода новых переменных получим систему .
Из теоремы о дополняющей нежесткости вытекает важное заключение, часто упрощающее поиск оптимальной стратегии противника в том случае, когда решение задачи линейного программирования достигается в одной точке (вершине допустимого множества):
Если для найденной оптимальной стратегии первого игрока какое-то из неравенств системы выполняется как строгое неравенство ("больше"), то соответствующая двойственная переменная обращается в нуль, то есть соответствующая компонента в оптимальной стратегии второго игрока должна быть нулевой. Такую чистую стратегию назовём неактивной.
Для активных чистых стратегий в оптимальной смешанной стратегии первого игрока, то есть для стратегий с положительными вероятностями соответствующие им в двойственной задаче нестрогие неравенства выполняются как строгие равенства.
В следующем пункте мы увидим, как применяется это правило.
Пример 14. Решить матричную игру:
Нетрудно увидеть, что третья стратегия первого игрока строго доминируема его первой стратегией, а четвёртая – второй. Поэтому игра эквивалентна следующей:
Четвёртая стратегия второго игрока доминируема его второй стратегией. Получим эквивалентную матрицу:
Для доминируемых стратегий игроков положим равными нулю их вероятности:
.
Далее рассматриваем задачу линейного программирования:
Решаем её графически:
Ломнная (4) на графике определяется как . Наибольшее значение функция (от p) достигает при . Следовательно, для первого игрока оптимальной является стратегия . Из рисунка следует также, что ограничение не является эффективным в точке максимума. Это значит, что оно выполняется как строгое и третья стратегия второго игрока также оказалась неактивной, то есть . А поскольку первые две чистые стратегии первого игрока оказались активными, то соответствующие им нестрогие неравенства для второго игрока превращаются в строгие равенства:
Оптимальные стратегии игроков: ; . Цена игры V=3.
Пример 15. Решить матричную игру:
Решение. Имеем:
Решением игры является .
Пример 16. Решить матричную игру:
Решение. Имеем:
1 случай. a>4. Тогда максимум v достигает в точке . Третье ограничение неэффективно. Следовательно, .
2 случай. . Тогда эффективными становятся ограничения (2) и (3). Имеем:
.
Первое ограничение неэффективно. Следовательно,
.
3 случай. При -2<a<1 третья стратегия второго игрока становится доминирующей. Тогда .
4 случай. При a<-2 третья стратегия второго игрока доминирующая.
Тогда .
5 случай. a=4. Тогда , v=2. Кроме того, поскольку p>0, то
.
6 случай. a=1. Тогда , v=1. Кроме того, поскольку первое ограничение неэффективно, то . Далее:
.
7 случай. a=-2. Тогда .