Лекция 2. Принятие решений в условиях риска

1. Основные понятия теории игр.

Теория игр – это математическая дисциплина, исследующая методы принятия решений в конфликтных ситуациях, когда сталкиваются интересы конфликтующих сторон. Обычно в игре участвуют два лица, преследующие противоположные цели. К конфликтным ситуациям относятся почти все ситуации, возникающие при планировании военных операций, охране объектов, преследовании и перехвате цели, при рассмотрении экономического поведения, арбитражных споров, выборов в парламент, работы аукционов.

Игра – это упрощенная формализованная модель конфликтной ситуации.

Игроки – это конфликтующие стороны.

Допустимые действия каждого игрока направлены на достижение некоторой цели – это правило игры. Элементы игры называются ходами.

Личный ход – это выбор игроком одного варианта из заданного множества. Решение, принятое игроком при личном ходе это выбор.

Случайный ход – это выбор одного варианта из множества при помощи некоторого случайного механизма.

Стратегия игрока – это система правил, однозначно определяющих выбор поведения игрока на каждом ходе в зависимости от ситуации, сложившейся в процессе игры. При выборе стратегии S_j S игрок получает выигрыш h_ij в зависимости от сложившейся i-ой ситуации. Для формализации игры применяют матрицу игры или платежную матрицу, элементы которой a_ij – это выигрыш 1-го игрока при выборе своей i-ой стратегии и встречной j-ой стратегии 2-го игрока.

Правила игры состоят в описании каждого хода в зависимости от выборов и исходов предыдущих ходов. Если это личный ход, то указывают возможные варианты для любого игрока. Если это случайный ход, то перечисляют возможные варианты с вероятностью их выбора. Кроме того правила определяют способ окончания игры и количественную оценку результатов игры – платеж (выигрыш и проигрыш каждого игрока).

Пусть X и Y пространства всевозможных стратегий x и y, которыми могут пользоваться участники игры: 1-й и 2-й игрок соответственно. Если рассматриваются случайные ходы, то считается, что в игре принимает участие 3 игрок делающий ходы с механизмом случайного выбора, выбирая их из пространства H с вероятностью P(h), причем .

Обозначим L_x(x,y,h) и L_y(x,y,h) - проигрыш 1-го и 2-го игроков соответственно в конкретной партии игры. Тогда общая сумма проигрышей называется функцией потерь L_x +L_y=L.

Далее будем рассматривать игры с нулевой суммой, т.е. игры в которых L_x(x,y,h) = -L_y(x,y,h) (проигрыш одного игрока равен выигрышу другого) – антагонистические игры.

С учетом случайности h можно найти средние потери.

Укажем, что в общем виде игра задается следующей моделью:

На множествах X и Y нужно выбрать такие стратегии, чтобы обеспечить первому игроку наибольший выигрыш, если 2-й игрок стремится минимизировать свой проигрыш. Тогда игра задается платежной матрицей строки, которой соответствуют стратегиям 1-го игрока, а столбцы стратегиям 2-го (указывают чистые стратегии игроков).

Заметим, что в игре с ненулевой суммой выигрыши одних игроков могут получаться не только за счет проигрышей других, но и за счет каких-либо платежей поступающих извне. Эти платежи рассматриваются как проигрыш какого-то фиктивного игрока, что позволяет свести игру n лиц с ненулевой суммой к игре n+1 лиц с нулевой суммой.

На этапе предварительного анализа игру удобно представить в виде дерева, на котором положения, возникающие в процессе игры, отображаются вершинами, а ходы – ветвями, соединяющими вершины. При этом расставляются пометки I, II, 0 для хода первого, второго и случайного игрока. Конечные вершины каждой дуги имеют внутреннюю пометку, означающую проигрыш 2-го игрока. Объединив те вершины, в которых игрокам доступна одинаковая информация о предыдущих ходах, получаем классы информации. Если информация о выборе 1-го игрока отсутствует, то игра называется игрой с неполной информацией. Игры в которых любой класс информации содержит только одну вершину, т.е. можно знать о всех предыдущих ходах, проследив по дереву игры путь до данной вершины называются играми с полной информацией.

Если первый игрок применяет стратегию X_k_,то он обеспечивает для себя гарантированный выигрыш A(X_k)= min L(X_k,Y) (наименьший элемент в k-ой строке).

Число называется нижней ценой игры,

а соответствующая чистая стратегия 1-го игрока называется максиминной.

Гарантированный проигрыш 2-го игрока B(y_k) равен наибольшему элементу из L(x,y_k) max в k-ом столбце. Выбор наименьшего из этих чисел обеспечивает уменьшение проигрыша 2-го игрока, тогда число - верхняя цена игры.

Теорема:

в игре с матрицей : A(x)≤L(x.y)≤B(y) и α<β.

Теорема:

Если α=β=υ, то игра имеет седловую точку, а соответствующие стратегии игроков являются оптимальными:

Максиминная стратегия оптимальна для первого игрока

Минимаксная стратегия оптимальна для 2-го игрока.

υ – цена игры: означает выигрыш первого и проигрыш 2-го игрока.

Точка (элемент матрицы ) называется седловой, если этот элемент является максимальным в своем столбце и минимальным в своей строке. Такая точка означает цену игры.

Если матрица игры имеет седловую точку, то игра называется игрой с седловой точкой. При υ=0 игра называется справедливой, при υ<>0 несправедливой.

Если игра не имеет седловой точки, то для решения используют смешанные стратегии.

Вектор, каждая координата которого равна относительной частоте или вероятности использования игроком соответствующей чистой стратегии, называется смешанной стратегией игрока. При использовании смешанных стратегий функция потерь зависит от распределения вероятностей и применения игроками №1 и №2 своих чистых стратегий x и y примет вид:

Теорема:

Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Гарантированное значение выигрыша 1-го игрока при стратегии :

Нижняя цена игры

Стратегия, определяющая нижнюю цену игры называется максиминной стратегией первого игрока.

Гарантированное значение проигрыша 2-го игрока при стратегии :

;

Верхняя цена игры

Стратегия η₀определяющая верхнюю цену игры называется минимаксной стратегией 2-го игрока.

Чистые стратегии, входящие в состав оптимальной смешанной стратегии называются полезными стратегиями.

Стратегия i₀для первого игрока называется доминируемой, если существует стратегия i₁ первого игрока / a_i_1,_j≥a_i_0,_j a_ij – элементы матрицы игры или существует μ_i≥0, i≠i₀/

Стратегия j₀2-го игрока называется доминирующей, если существует стратегия j₁2-го игрока / a_i_,_j1≥a_i_,_j0 или существует ν_j≥0, j≠j₀/

Теорема:

Неполезными стратегиями 1-го игрока являются его доминируемые стратегии. Неполезными стратегиями 2-го игрока являются его доминирующие стратегии.

На основании теоремы целесообразно вычеркнуть из матрицы игры неполезные стратегии, т.о. уменьшить размерность матрицы игры и упростить процесс решения.

2 Методы решения задач теории игр с нулевой суммой

1-й метод: Матрица игры имеет седловую точку, тогда решение сводится к поиску седловой точки матрицы, координаты которой (i₀,j₀) определяют элемент a_i_0,_j0 – цену игры, i₀ – чистая оптимальная стратегия 1-го игрока, j₀ – чистая оптимальная стратегия 2-го игрока.

Пример: Игра имеет матрицу

α₁=2; α₂=5; α₃=4; - min элемент в строке.→ max=5=α – верхняя цена игры.

β₁=10; β₁=10; β₁=5; β₁=14; β₁=12; - max элемент столбца→ min=5=β – нижняя цена игры.

a_2,3=5=α=β=υ – цена игры, т.е. оптимальная стратегия 1-го игрока №2, 2-го игрока № 3.

2-й метод: Матрица А имеет размер 2 x n (m x 2) или сводима к этим размерам, тогда задача может быть решена графически. Рассмотрим ситуацию 2 x n, тогда 1-й игрок имеет 2 стратегии и его искомая смешанная стратегия U(x₁,x₂), где x_i – это вероятности с которыми игрок применяет свои i стратегии, тогда средний выигрыш игрока 1-го, если 2-й игрок применяет свою стратегию y_j, равен: L(x,y_j)=x₁*a₁_j+x₂*a₂_j. Это может быть интерпретировано графически как прямая. Изобразив все стратегии 2-го игрока, как ответы на ход 1-го, определим максиминную стратегию, оптимальную для 1-го игрока. Аналогично, если матрица имеет размер m x 2, изображаем стратегии 1-го как ответы на ход второго. Найдем минимаксную стратегию, оптимальную для 2-го и находят его оптимальную смешанную стратегию.

Пример:

Изображаем стратегии второго игрока

9 9

7 6

х₁1/3 х₂

Решаем задачу первого игрока (ищем максиминную стратегию), для чего решаем систему уравнений:

результате получим: х₁=2/3; х₂=1/3; U^*=(2/3; 1/3) υ=8 (цена игры)

y₁=y₂=1/2; y₃=0; υ=8;

X^*(2/3;1/2)→ 67% времени 1-й игрок применяет свою стратегию №1 и 33% времени стратегию № 2.

Пример 2:

Т.к. 2-й игрок имеет 2 стратегии, то решаем задачу для 2-го игрока, изображая стратегии 1-го как ответ на ход 2-го.

y₁₌3/8; y₂=5/8; υ=43/8

x₁=7/8; x₂=0; x₃=0; x₄=1/8 X^*(7/8;0;0;1/8)

Пример 3:

доминируемая стратегия

доминирующие стратегии

Вычеркивая неполезные стратегии (доминируемые для первого игрока и доминирующие для второго), получим, что матрица после упрощения примет вид:

, и решаем задачу графически:

7 7

x₁=x₃=1/2; x₂=0; υ=4,5

y₄=y1=0; y₂=7/12; y₃=0; y₅=5/12

X^*(1/2;0;1/2);

Y^*(0;7/12;0;0;5/12);

υ=4,5;

3 метод. Матрица А имеет размер m x n, не имеет седловой точки и не может быть решена графически. Тогда задача теории игр сводится к задаче линейного программирования, а именно к паре взаимодвойственных задач для 1-го и 2-го игрока соответственно.

Задача 1-го игрока: Задача 2-го игрока:

F=υ→max Ф=U→min