Выбор оптимального решения игр в смешанных стратегиях

Таблица 4. Решение задачи

Решение.

Решение задачи приведено в таблице 4

Ai Вj	стратегии игрока В	αi	нижняя цена игры, α
В1	В2	В3
стратегии игрока А	A1	0,5	0,6	0,8	0,5	α=0,7
A2	0,9	0,7	0,8	0,7
A3	0,7	0,6	0,6	0,6
βj	0,9	0,7	0,8	чистая цена игры ν=α=β=0,7
верхняя цена игры, β	β=0,7

Анализируя строки матрицы (стратегии игрока А), заполняем столбец α _i: α ₁ =0,5, α ₂ =0,7, α ₃ =0,6 - минимальные числа в строках i= 1, 2, 3. Заполняем строку β_j – максимальные числа в столбцах j=1.2,3 соответственно: β ₁ =0,9, β ₂ =0,7, β ₃ =0,8.

Значения нижней цены игры α - наибольшее число в столбцеα_i, и верхней цены игры β - наименьшее число в строке β _j равны: α=β=0,7. Равные значения α и β достигаются на одной и той же паре стратегий (A ₂, B ₂).

Следовательно, игра имеет седловую точку (A ₂ , B ₂) и цена игры ν =0,7.

Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере1 α=-1 ≠ β=1, седловая точка отсутствует. В этом случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁,A₂,...,A_m с вероятностями p₁,p₂,...,p_i,...,p_m. Причем сумма вероятностей равна 1:

Смешанные стратегии игрока А записываются в виде матрицы:

Аналогично смешанные стратегии игрока В обозначаются:

где сумма вероятностей появления стратегий также равна 1:

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии.

Оптимальное решение (или решение) игры (на основании принципа минимакса) - это пара оптимальных стратегий S*_A, S*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей.

Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: α ≤ v ≤ β, где α и β — нижняя и верхняя цены игры.

Справедлива следующая основная теорема теории игр - теорема Неймана:

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

Пусть S*_A = (p*₁,p*₂,...,p*_i,...,p*_m) и S*_B = (q*₁,q*₂,...,q*_j,...,q*_n) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

Справедлива теорема об активных стратегиях:

если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

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

Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры.

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

Для игры, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*_A = (p*₁, p*₂) и S*_B = (q*₁, q*₂).

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S*_A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В.

Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й – B₁, и для 2-й - B₂ стратегии противника.

Пусть игра задана платежной матрицей /

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию , а игрок В - чистую стратегию B₁ (это соответствует 1-му столбцу платежной матрицы H), равен цене игры v:

h₁₁ p*₁+ h₂₁ p*₂= v.

Тот же средний выигрыш получает игрок А, если игрок B применяет стратегию B₂, т.е.

h₁₂ p*₁+ h₂₂ p*₂= v.

Учитывая, что p*₁+p*₂=1, получаем систему уравнений для определения оптимальной стратегии S'_A и цены игры v:

Решая эту систему, получим оптимальную стратегию игрока А:

и цену игры: .

Применяя теорему об активных стратегиях при отыскании S*_В- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А₁ или А₂) средний проигрыш игрока В равен цене игры v, т.е.

Тогда оптимальная стратегия игрока В определяется формулами: