Принятие решений в условиях риска (в условиях неопределенности Теория игр

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

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

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

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

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

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

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

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

Пусть X и Y пространства всевозможных стратегий x и y, которыми могут пользоваться участники игры: 1-й и 2-й игрок соответственно. Обозначим 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-го (указывают чистые стратегии игроков).

Если первый игрок применяет стратегию 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_i1,j≥a_i0,j a_ij – элементы матрицы игры или существует μ_i≥0, i≠i₀ /

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

Теорема:

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

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