Решение матричных игр в чистых стратегиях

Целью участников любой матричной игры является выбор наиболее выгодных стратегий, доставляющих игроку А максимальный выигрыш, а игрок В минимальный проигрыш. Стратегию игрока А называют оптимальной, если при ее применении выигрыш игрока А не уменьшается, какими бы стратегиями не пользовался игрок В. Оптимальный для игрока В называют стратегию, при использовании которой проигрыш игрока В не увеличивается, какие бы стратегии не применял игрок А.

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

Поэтому игроки должны быть предельно внимательны при выборе каждой своей чистой стратегии.

Предположим, что игроку А надлежит сделать свой выбор. Анализируя платежную матрицу (таблица 1, стр. 8), он для каждой чистой стратегии А_i (i= ) сначала найдет минимальное значение ожидаемого выигрыша: (i= ), , а затем из всех выделит наибольше и выберет соответствующую ему чистую стратегию А_i⁰. Это и будет наиболее предпочтительная (гарантирующая, «перестраховочная») в данных условиях стратегия игрока А. Ее называют максиминной, поскольку она отвечает величине

Число называется нижней чистой ценой игры (максимином). Оно показывает, какой минимальной выигрыш может получить игрок А, правильно применяя свои чистые стратегии при любых действиях игрока В. В свою очередь, игрок В, стремясь минимизировать проигрыш, при выборе наиболее предпочтительной стратегии, использует принцип осторожности по-своему: сначала он для каждой чистой стратегии B_j , найдет максимально возможный проигрыш , затем среди β_j выберет минимальное значение , которому и будет соответствовать искомая чистая стратегия В_j⁰. Ее называют минимаксной, так как она соответствует величине .

Число β называют верхний чистой ценой игры (минимаксом). Оно показывает, какой максимальный проигрыш может быть у игрока В при правильном выборе им чистых стратегий независимо от действий игрока А.

Таким образом, правильно используя чистые стратегии, игрок А обеспечивает себе выигрыш не меньше α, а игрок В в результате правильного применения своих чистых стратегий не позволит игроку А выиграть больше, чем β.

В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. α ≤ β. Это можно легко доказать.

По определению ; .

Объединив эти соотношения, получим:

≤ ≤ .

Отсюда

Это неравенство справедливо для любых комбинаций i и j. Будет оно справедливо и для тех i и j, для которых max α_i = α; min β_j = β и при любых i и j получаем α≤β.

Если в матричной игре нижняя и верхняя чистая цена - совпадают, т.е. α = β то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры v = α = β

Обозначим через i и j номера чистых стратегий, при которых имеет место равенство α = β Пару чистых стратегий (A_i;B_j) игроков А и В, при которых достигается это равенство, называют седловой точкой матричной игры, а элемент матрицы, стоящей на пересечении i-ой строки и j-го столбца называют седловым элементом платежной матрицы.

В развернутой форме признак матричной игры с седловой точкой запишется в виде: = =

В игре с матрицей

Ai	Bj	αi
B1	B2	В3	B4
A1
A2			-1	-3	-3
А3		-2	-5		-5
j

=2,

Т.е. V = α = β = 2, значит представленная игра с седловой точкой. В данном случае имеют две седловые точки (А₁; В₂) и (А₁; В₄).

Для игрока А максиминной является стратегия A₁⁰, для игрока В минимаксными будут стратегии B₂⁰ и B₄⁰. В платежной матрице содержится два седловых элемента а₁₂=2 и а₁₄= 2.

Из примера следует, что в матричной игре может быть несколько седловых точек (соответственно седловым элементам). Можно отметить

одно важное замечание: седловой элемент a_ij наименьшим в i-ой строке и наибольшей в j-том столбце.

Поэтому, если игрок В отклонится от своей минимаксной стратегии, его проигрыш может только увеличиться. Аналогично, отклонение игрока А от своей максимминной стратегии ведет к уменьшению его выигрыша. Таким образом, наиболее предпочтительные стратегии в игре с седловой точкой обладает свойством устойчивости, создают ситуацию равновесия.

Итак, если матричная игра имеет седловую точку, то она решается в чистых стратегиях; чистые стратегии, образующие седловую точку, и будут оптимальными, а решением игры является тройка {A_i;B_j; a_ij}. В нашем примере игра имеет два решения:

{А*₁;В*₂;2}и{А*₁;В*₄;2}.

Задача 3 имеет седловую точку:

= max (-64;-62;-60) = -60

= min (-45;-52,5;-60) = -60,

т.е. α = β = a₃₃=-60.

Следовательно игра обладает cедловой точкой (A₃⁰;П₃⁰), и чистой ценой v = -60. Задачи 1, 2, 4 - не имеют седловой точки.

Поскольку данная игра является статистической (игрой с природой), то давать рекомендации игроку П (природа) по оптимальному поведению не имеет смысла, а вот сознательному игроку А (домовладельцу) рекомендовать следует чистую стратегию А₃, т.е. запасти летом 8 т. угля.