Чистые и смешанные стратегии и их свойства

Чистая стратегия A_i (i=1,m) первого игрока – это возможный ход первого игрока, выбранный им с вероятностью, равной единице. Аналогично определяется стратегия B_j (j=1,n) второго игрока. Если первый игрок имеет m стратегий, а второй n стратегий, то для всех пар стратегий первого и второго игроков чистые стратегии можно представить в виде единичных векторов, т.е. для пары стратегий A_iB_j чистую стратегию можно записать в виде p_i=(0,0,…,1(i-е место),0,…,0), q_j=(0,0,…,1(j-е место),0,…,0).

Теорема. В МИ нижняя чистая цена игры не превосходит верхней чистой цены игры: a£b. Если для чистых стратегий A_iB_j игроков А и В соответственно имеет место равенство a=b, то пару чистых стратегий (A_iB_j) называют седловой точкой МИ, элемент матрицы a_ij на пересечении i-й строки и j-го столбца, – седловым элементом платежной таблицы, а число n=a=b называется чистой ценой игры.

Если МИ не имеет седловой точки, то решение игры затрудняется, в таких играх a<b. Для решения этих задач применяют смешанные стратегии.

Смешанными стратегиями двух игроков называются векторы p и q:

p=(p₁,p₂,…,p_m), p_i³0, . q=(q₁,q₂,…,q_n), q_j³0, .

Вектор p(q) есть вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком). Средняя величина выигрыша или проигрыша – мат. ожидание, которое является ф-ей от смешанных стратегий (это и будет целевая функция линейного программирования: f (p,q) – v ® 0):

. Функция f(p,q) называется платежной функцией МИ.

Стратегии p*=(p₁*,p₂*,…,p_m*); q*=(q₁*,q₂*,…,q_n*) называются оптимальными, если для произвольных стратегий p и q выполняются условия: f(p, q*) £ f(p*, q*) £ f(p*, q).

Совокупность оптимальных стратегии и цены игры составляет решение игры. Значение платежной функции при оптимальных стратегиях определяет чистую цену игры: f(p*, q*) = n

Теорема. В смешанных стратегиях любая конечная МИ имеет седловую точку.

Теорема. Для того, чтобы смешанные стратегии p* и q* были оптимальными в игре с матрицей [a_ij]_mxn с выигрышем n необходимо и достаточно выполнение неравенств:

i=1ån a_ijp_i* ³ n; j=1åm a_ijq_j* £ n (ограничения для задачи линейного программирования)

Если игрок А принимает оптимальную смешанную стратегию р*, а игрок В любую чистую стратегию B_j, то выигрыш игрока А будет не меньше цены игры n. Аналогично, если игрок В использует оптимальную смешанную стратегию q*, то проигрыш игрока В не превысит цены игры n.

Активные стратегии игрока – это чистые стратегии игрока, которые входят в его оптимальную смешанную стратегию с вероятностями отличными от 0.

Теорема. Если один из игроков придерживается своей оптимальной стратегии, то его выигрыш остается неизменным и равным цене игры, независимо от того, какую стратегию применяет другой игрок (если только второй игрок не выходит за пределы своих активных стратегий).

Решение МИ можно упростить, если выявить доминирование одних стратегий над другими. Рассмотрим стратегии игрока А и элементы строк s и t. Если a_sj³a_tj, то выигрыш игрока А при стратегии A_s больше, чем при стратегии A_t, т.е. A_s доминирует над A_t. В этом случае строка s называется доминирующей, а строка t доминируемой. Для игрока В доминирующим будет столбец с наименьшими элементами.

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

Пусть дана матричная игра с матрицей А порядка m×n. Оптимальные смешанные стратегии

х = (х₁, ..., х_m) и y = (y₁,..., y_n) игроков 1 и 2 и цена игры v должны удовлетворять соотношениям:

Разделим все уравнения и неравенства на v (это можно сделать,т.к. по предположению v > 0).

Тогда:

, .

Поскольку первый игрок стремится найти такие значения х_i и, следовательно, p_i , чтобы цена игры была макс., то решение первой задачи сводится к нахождению таких значений p_i>0, при которых

Поскольку второй игрок стремится найти такие значения y_j и,следовательно, q_j, чтобы цена игры v была мин., то решение второй задачи сводится к нахождению таких значений q_j>0, при которых

Эти формулы выражают двойственные друг другу задачи линейного программирования.

Решив эти задачи, получим значения p_i, q_j и v.Тогда смешанные стратегии, т.е. x_i и y_j получаются:

Пример. Найти решение игры, определяемой матрицей.

При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу:

Составим теперь пару взаимно-двойственных задач :

Решим вторую из них симплексным методом. Из оптимальной симплекс-таблицы следует,

что (q₁, q₂, q₃) = (0; 1/2; 1), а из соотношений двойственности следует, что

( p₁, p₂, p₃) = (1/2; 1; 0).

Следовательно, цена игры с платёжной матрицей А₁ равна

,

а игры с платёжной матрицей А:

При этом оптимальные стратегии игроков имеют вид:

Х = (х₁, х₂, х₃) = (v₁р₁; v₁р₂; v₁р₃) = (1/3; 2/3; 0)

Y = (y₁, y₂, y₃) = (v₁q₁; v₁q₂; v₁q₃) = (0; 1/3; 2/3)