Модели теории игр

Лекция 5 Модели теории игр Изучаемые вопросы: 1. Основные понятия теории игр 2. Парная игра с нулевой суммой 3. Игры в чистых и смешанных стратегиях 4. Игры с природой Литература: 1. Основная литература [1 - 4]. 2. Дополнительная литература [1, 3 - 5, 7-9]. Основные понятия Теория игр – это наука построения математических моделей конфликтных ситуаций и разработки методов решения возникающих в этих ситуациях задач. Антагонистическая игра двух лиц с нулевой суммой –это игра, в которой имеются два участника и выигрыш одного равен проигрышу другого. • Стратегией игрока называется система правил, однозначно определяющих поведение игрока на каждом ходе в зависимос­ти от ситуации, сложившейся в процессе игры • Оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш. Парная игра с нулевой суммой Игру можно представить в виде платежной матрицы, в которой строки — стратегии первого игрока, столбцы — стратегии второго игрока, а элементы матрицы — выигрыши первого игрока. • Задача каждого из игроков — найти наилучшую стратегию игры, при этом предполагается, что противники делают все, чтобы получить наибольший доход. • Наилучшая стратегия первого игрока: минимальное число в каждой строке αi (i =1, 2, …,m), • Зная αi, т.е. минимальные выигрыши при различных стратегиях А i, первый игрок выберет ту стратегию, для которой αi максимально. Обозначим это максимальное значение через α, тогда • Величина α — гарантированный выигрыш, который может обеспечить себе первый игрок, — называется нижней ценой игры (максимином). • Для определения наилучшей стратегии второго игрока нужно найти максимальные значения выигрыша по столбцам и выбрать из них минимальное значение: где β — верхняя цена игры (минимакс). Если второй игрок будет придерживаться своей минимаксной стратегии, то он гарантирован, что в любом случае проиграет не больше β. • Для матричной игры справедливо неравенство • Если α = β, то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий (А iопт, Bjопт) — седловой точкой матрицы. • Элемент αij = v называется ценой игры, является одновременно минимальным в i-й строке и j-м столбце. • Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях. • Стратегия называется смешанной, если платежная матрица не имеет седловой точки, т.е. α<β, и поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. • В игре, матрица которой имеет размерность т х n, стратегии первого игрока задаются наборами вероятностей = (x 1, x 2,... ,x т), с которыми игрок применяет свои чистые стратегии. • Наборы вероятностей можно рассматривать как m-мерные векторы, для координат которых • Для второго игрока наборы вероятностей определяют n-мерные векторы y= (y 1, y 2, … , y п), для координат которых • Выигрыш второго игрока при использовании смешанных стратегий определяют как математическое ожидание выигрыша, т.е. он равен • Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры: a ≤ v ≤ b. • Применение первым игроком оптимальной стратегии x iопт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры: • Второму игроку оптимальная стратегия y jопт должна обеспечить при любых стратегиях первого игрока проигрыш, не превышающий цену игры. Игра «с природой» • Игры называются играми «с природой», если имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупатель­ский спрос и т.д.). • Условия игры задаются матрицей • Критерии, которые используют при выборе оптимальной стратегии: • Критерий Вальде. Применяется максиминная стратегия: • Критерий максимума • Критерий максимума является оптимистическим, считается, что природа будет наиболее благоприятна для человека. • Критерий Гурвица • где α — степень оптимизма — изменяется в диапазоне [0, 1]. • Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего для человека поведения природы. • При α = 1 критерий превращается в критерий Вальде, при α = 0 — в критерий максимума. • На α оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем хуже последствия ошибочных решений, больше желания застраховаться, тем а ближе к единице. • Критерий Сэвиджа. Суть критерия состоит в выборе та­кой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет человек (фирма), если для каждого состояния природы он не выберет наилучшей стратегии. • Элемент матрицы рисков (rij) находится: формуле где max аij — максимальный элемент в столбце исходной мат­рицы. • Оптимальная стратегия находится из выражения