Предмет и задачи теории игр. Основные понятия
Теория игр и принятия решений
Пример построения и решения уравнений Колмогорова для однородной непрерывной марковской цепи
Правила формирования уравнений Колмогорова
· В левой части каждого уравнения стоит производная вероятности состояния.
· Правая часть содержит столько членов, сколько стрелок связано с данным состоянием.
· Если стрелка направлена из состояния, соответствующий член имеет знак "минус".
· Если стрелка направлена в состояние, соответствующий член имеет знак "плюс".
· Каждый член равен произведению плотности вероятности перехода, соответствующей данной стрелке, и вероятности того состояния, из которого исходит стрелка.
· Сумма всех членов всех уравнений равна нулю.
Рассмотрим систему S с четырьмя возможными состояниями: S1, S2, S3, S4 и размеченным графом состояний, приведенном на рис. 11.
| S1 |
| S2 |
| S3 |
| S4 |
| 0.9 |
| 0.3 |
| 0.6 |
| 0.4 |
| 0.2 |
| 0.2 |
Рис. 11.
В момент t = 0 система находится в состоянии S1. Необходимо найти вероятности состояний системы в момент t = 10 и построить графики изменения вероятностей состояний на отрезке времени [0; 10].
Запишем на основе размеченного графа систему уравнений Колмогорова:
Сумма правых частей всех уравнений равна нулю.
Начальные условия:
Решим полученную систему обыкновенных дифференциальных уравнений на отрезке [0; 10]. Поскольку система содержит линейные дифференциальные уравнения с постоянными коэффициентами, возможно ее аналитическое решение. Однако на практике чаще требуется не аналитическое выражение для функций, описывающих вероятности состояний, а конкретные числовые значения. Поэтому воспользуемся численными методами решения, применимым как к однородным, так и к неоднородными непрерывным марковским цепям.
Решение уравнений Колмогорова в системе компьютерной математики MATLAB с использованием метода Рунге - Кутты с автоматическим выбором шага на отрезке [0; 10] дает следующие графики изменения вероятностей состояний системы (рис. 12):
Рис. 12.
Сумма значений вероятностей состояний в каждый момент времени равна единице.
Вероятности состояний в момент t = 10 равны (с точностью до 4 цифр после десятичной точки):
(сумма вероятностей равна единице).
Рассмотренные выше марковские цепи используются при для математического моделирования в случаях, когда условия операции содержат неопределенность, но относительно «хорошую», стохастическую, которая может быть учтена, если знать законы распределения или числовые характеристики фигурирующих в задаче случайных факторов (для марковских цепей – вероятности переходов или плотности вероятностей переходов из состояния в состояние).
Но возможен и гораздо худший вид неопределенности, когда некоторые параметры, от которых зависит успех операции, неизвестны, и нет никаких данных, позволяющих судить о том, какие их значения более, а какие – менее вероятны. Неопределенными могут быть как внешние, «объективные» условия операции, как и «субъективные» – сознательные действия противников, соперников или других лиц. Предсказывать, как себя поведут эти лица, еще труднее, чем предсказывать в области случайных явлений.
Такого рода задачами занимается специальный раздел математики, носящий название «теория игр и принятия решений». В некоторых (редких) случаях разработанные в нем методы дают возможность фактически найти оптимальное решение. Гораздо чаще эти методы позволяют попросту глубже разобраться в ситуации, оценить каждое решение с различных (иногда противоречивых) точек зрения, взвесить его преимущества и недостатки и, в конце концов, принять решение, если не единственно правильное, то, по крайней мере, до конца продуманное. Нельзя забывать, что при выборе решения в условиях неопределенности неизбежен некоторый произвол и элемент риска. Тем не менее, в сложной ситуации, плохо обозримой в целом, всегда полезно представить варианты в такой форме, чтобы сделать произвол выбора менее грубым, а риск – по возможности минимальным. Нередко задача ставится так: какой ценой можно заплатить за недостающую информацию, чтобы за ее счет повысить эффективность операции? Заметим, что иногда для выбора решения и не требуется точной информации об условиях, а достаточно только указать «район», в котором они находятся.
Наиболее простыми из ситуаций, содержащих «плохую» неопределенность, являются так называемые конфликтные ситуации. Так называются ситуации, в которых сталкиваются интересы двух (или более) сторон, преследующих разные (иногда противоположные) цели, причем выигрыш каждой стороны зависит от того, как себя поведут другие. Примеры конфликтных ситуаций:
· боевые действия;
· ряд ситуаций в области экономики;
· судопроизводство;
· спорт;
· межвидовая борьба;
· …
Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее задача – выработка рекомендаций по разумному поведению участников конфликта.
Каждая конкретная конфликтная ситуация очень сложна, и ее анализ затруднен наличием большого числа факторов. Чтобы сделать возможным математический анализ конфликта, строится его математическая модель. Такую модель называют игрой.
Игра – упрощенная модель конфликтной ситуации.
От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила указывают «права и обязанности» участников, а также исход игры — выигрыш или проигрыш каждого участника в зависимости от сложившейся обстановки.
Игроки– конфликтующие стороны (участники игры).
Выигрыш или проигрыш –исход игры, имеющий количественное выражение (если это не так, то всегда можно им его приписать, например, в шахматах считать «выигрыш» за 1, «проигрыш» за 0, «ничью» за 1/2).
В игре могут сталкиваться интересы двух или более участников; в первом случае игра называется «парной», во втором – «множественной».
Участники множественной игры могут образовывать коалиции (постоянные или временные). Одна из задач теории игр – выявление разумных коалиций во множественной игре и правил обмена информацией между участниками.
Партия – одно осуществление игры. Представляет собой ряд последовательных ходов участников.
Ход – выбор игроком одного из предусмотренных правилами игры действий и его осуществление. Ходы бывают:
· личные;
· случайные.
При личном ходе игрок сознательно выбирает и осуществляет тот или другой вариант действий (пример – любой ход в шахматах).
При случайном ходе выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора (бросание монеты, игральной кости, вынимание карты из колоды и т. п.).
Игры, состоящие только из случайных ходов, называются азартными. Ими теория игр не занимается.
Игры, в которых (может быть, наряду со случайными) есть личные ходы – стратегические. Цель теории игр – оптимизация поведения игрока в стратегической игре.
Стратегия игрока – совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации.
В зависимости от числа стратегий игры делятся на:
· конечные – если у каждого игрока имеется в распоряжении только конечное число стратегий;
· бесконечные – в противном случае.
Бывают игры (например, шахматы), где в принципе число стратегий конечно, но так велико, что полный их перебор практически невозможен.
Задача теории игр – выявление оптимальных стратегий игроков.
Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (или минимально возможный средний проигрыш). При выборе этой стратегии основой рассуждений является предположение, что противник по меньшей мере так же разумен, как и мы сами, и делает все для того, чтобы помешать нам добиться своей цели.
В теории игр все рекомендации вырабатываются исходя именно из этих принципов. Следовательно, в ней не учитываются просчеты и ошибки игроков, элемента азарта и риска и т.п.
Игра с нулевой суммой – сумма выигрышей всех игроков равна нулю (т.е. каждый игрок выигрывает только за счет других).
Антагонистическая игра – конечная парная игра с нулевой суммой. Теория антагонистических игр – наиболее развитый раздел теории игр, с четкими рекомендациями.
Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о «идеальной» разумности противника. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник «глуп», и воспользоваться этой глупостью в свою пользу. Схемы теории игр не включают элементов риска, неизбежно сопровождающего разумные решения в реальных конфликтах. В теории игр выявляется наиболее осторожное, «перестраховочное» поведение участников конфликта. Сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать аппарат теории игр как «совещательный» при выборе решения.