Смешанные стратегии

В общем случае V_* ≠ V^* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи, аналогичный рассмотренному выше. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:

P = (p₁, p₂,…, p_m),

где p_i≥ 0, p₁ + p₂ +…+ p_m= 1. Величина p_i называется вероятностью (относительной частотой) применения стратегии A_i.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:

Q = (q₁, q₂,…, q_n),

где q_j≥ 0, q₁ + q₂ +…+ q_n = 1. Величина q_j называется вероятностью (относительной частотой) применения стратегии B_j. Совокупность (комбинация) чистых стратегий A₁, A₂, …A_m и B_1, B_2, …B_n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P^* и Q^*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.

Средний выигрыш игрока A определяется математическим ожиданием:

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

Стратегии P^*, Q^* называются оптимальными смешанными стратегиями, если

M_A(P, Q^*) ≤ M_A(P^*, Q^*) ≤ M_A(P^*, Q) (1)

В этом случае M_A(P^*, Q^*) называется ценой игры и обозначается через V (V_* ≤ V ≤ V^*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

Дата добавления: 2014-01-15