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

Решим задачу из примера 2. Напомним ее формулировку: игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В.

Матрица игры:

B_j A_i	B₁	B₂	B₃	минимум в строках α_i
A₁		–3		–3	максимин
A₂	–3		–5	–5
A₃		–5		–5
максимум в столбцах β_j
	минимакс

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

Чтобы использовать рассмотренный выше метод решения, необходимо, чтобы цена игры была положительной. Для этого достаточно добавить к каждому элементу матрицы такое число, чтобы нижняя цена игры α (максимин) стала положительной. Смысл этого действия – не допустить возможность получения решения ν = 0, поскольку в дальнейшем необходимо использовать величину 1/ν. Поскольку ν не меньше нижней цены игры (ν ≥ α), то при α > 0 цена игры ν также будет больше нуля.

Добавим к каждому элементу матрицы значение 4. При этом цена игры увеличится на 4, но оптимальные стратегии от этого не изменятся. Получим матрицу M:

Найдем смешанную стратегию игрока A: Как показано выше, для этого необходимо решить оптимизационную задачу:

при ограничениях

Данная задача решается с помощью методов линейного программирования. Для решения можно воспользоваться системами компьютерной математики. Например, используя функцию linprog системы MATLAB, получаем решение:

x₁ = 0.0625,

x₂ = 0.1250,

x₃ = 0.0625.

Учитывая, что , получаем: , откуда ν = 4. Подставляя ν в выражения

получаем

p₁ = 1/4,

p₂ = 1/2,

p₃ = 1/4.

Поскольку при определении оптимальной стратегии мы добавили к каждому элементу матрицы игры значение 4, вычтем его из полученного значения ν и получим истинную цену игры (средний выигрыш):

ν = 0.

Итак, если игрок A при многократном повторении игры будет придерживаться оптимальной смешанной стратегии

заключающейся в том, что A будет случайным образом выбирать в половине партий стратегию A₂, в четверти партий – A₁ и еще в четверти партий – A₃, а противник B также будет придерживаться своей оптимальной стратегии, то игрок A в среднем ничего не выиграет и ничего не проиграет ("справедливая игра"). Если же противник B отклонится от своей оптимальной стратегии, то A может в среднем даже выиграть.

Определим теперь для игрока B оптимальную смешанную стратегию
и убедимся, что цена игры будет той же самой. Для этого необходимо решить оптимизационную задачу:

при ограничениях

Решение этой задачи:

y₁ = 0.0625,

y₂ = 0.1250,

y₃ = 0.0625,

(Решение для игрока B совпало с решением для игрока A в силу того, что матрица игры симметричная. В общем случае при несимметричной матрице игры решения не обязаны совпадать.)

Вероятности для игрока B:

q₁ = 1/4,

q₂ = 1/2,

q₃ = 1/4.

Цена игры (после вычитания добавленного значения 4):

ν = 0.

Итак, оптимальные смешанные стратегии для игроков:

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

Графическое решение игр вида 2×n

Наиболее простыми случаями конечных игр является игры 2×2, 2×n, m×2. Решение таких игр может быть найдено графически. Рассмотрим их на примере решения игры вида 2×n (игра 2×2 является ее частным случаем, а игра m×2 может быть преобразована к 2×m, если мы построим матрицу игры с точки зрения противника).

Пусть сторона A (самолеты) выполняет воздушный налет на объект, а сторона B (зенитные орудия) обороняет его. У стороны A есть 2 самолета, несущих поражающие средства, у стороны B есть 4 зенитных орудия. Чтобы объект оказался разрушенным, достаточно, чтобы к нему прорвался хотя бы один самолет. Для прохода к объекту самолеты могут использовать один из четырех воздушных коридоров.

III

Сторона A может послать оба самолета в один и тот же коридор или направить по одному самолету в разные коридоры. Сторона B может разместить свои зенитные орудия в пределах рассматриваемых коридоров – по одному в каждом или в какие-то коридоры поставить несколько орудий, а какие-то оставить без орудий. Каждое зенитное орудие может произвести только выстрел в направлении своего коридора. Попадание выстрела в самолет поражает его с полной достоверностью. Сторона A не знает, где размещены орудия, сторона B не знает, по каким коридорам полетят самолеты. Задача стороны A – поразить объект, стороны B – не допустить его поражения. Необходимо найти решение игры.

Если в качестве стратегий рассматривать все возможные способы выбора самолетами коридоров и расстановки орудий, то получим игру 16×256, поскольку:

· у каждого самолета на выбор 4 коридора, всего самолетов 2, следовательно, у стороны A есть 4²=16 вариантов;

· каждое орудие можно разместить в любом из 4 коридоров, всего орудий 4, следовательно, у стороны B есть 4⁴=256 вариантов.

Но можно ограничиться гораздо меньшим числом стратегий, если заранее их "смешать" и рассматривать для A только две стратегии:

A₁ – послать два самолета в два разных (любых) коридора;

A₂ – послать оба самолета в один и тот же коридор (любой).

Для стороны B всего получается 5 стратегий:

B₁ – поставить по одному орудию на каждый коридор (1+1+1+1);

B₂ – поставить два орудия на один коридор, по одному на два других и один коридор оставить незащищенным (2+1+1+0);

B₃ – поставить по два орудия на два коридор, а два оставшихся оставить незащищенным (2+2+0+0);

B₄ – поставить три орудия на один коридор, одно – на другой, а два оставшихся оставить незащищенным (3+1+0+0);

B₅ – поставить все четыре орудия на один коридор (4+0+0+0).

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

В результате у нас получается игра 2×3:

B_j A_i	B₁	B₂	B₃
A₁	a₁₁	a₁₂	a₁₃
A₂	a₂₁	a₂₂	a₂₃

Найдем выигрыш стороны A (вероятность поражения объекта) при всех комбинациях стратегий.

A₁, B₁ – самолеты летят по разным коридорам, в каждом коридоре по одному орудию (1+1+1+1). В этом случае ни один самолет не прорвется к объекту, выигрыш a₁₁ = 0.

A₂, B₁ – оба самолета летят по одному коридору, в каждом коридоре по одному орудию (1+1+1+1). В этом случае один самолет будет сбит, а второй, для которого уже не будет орудия, прорвется к объекту и уничтожит его. Вероятность поражения объекта a₂₁ = 1.

A₁, B₂ – самолеты летят по разным коридорам, орудия стоят по схеме (2+1+1+0). Объект будет уничтожен, если один (любой) из самолетов не будет сбит. Вероятность этого события равна 1 минус вероятности события "оба самолета сбиты". Вероятность, что первый самолет выберет защищенный коридор, равна 3/4 (так как три коридора из четырех имеют зенитные орудия). После этого для второго самолета остается два защищенных и один незащищенный коридор (всего три), и вероятность выбора защищенного коридора равна 2/3. Тогда оба самолета выберут защищенные коридоры и будут сбиты с вероятностью 3/4·2/3 = 1/2, а что один самолет выберет незащищенный коридор, равна 1–1/2, то есть a₁₂ = 1/2.

A₂, B₂ – оба самолета летят одному коридору, орудия стоят по схеме (2+1+1+0). Объект будет уничтожен, если хотя бы один самолет не будет сбит. Вероятность этого события равна 1 минус вероятность того, что оба самолета будут сбиты. Это произойдет только если самолеты полетят по тому коридору, в котором стоит два орудия. Вероятность выбрать именно этот коридор и четырех возможных равна 1/4. Следовательно, вероятность того, что хотя бы один самолет не будет сбит, равна 1–1/4, то есть a₂₂ = 3/4.

A₁, B₃ – самолеты летят по разным коридорам, орудия стоят по схеме (2+2+0+0). Объект будет уничтожен, если хотя бы один из самолетов не будет сбит. Вероятность этого события равна 1 минус вероятности события "оба самолета сбиты". Вероятность того, что первый самолет выберет коридор с орудиями, равна 2/4 (2 коридора с орудиями из 4 возможных). После этого для второго самолета остается 1 коридор с орудием и 2 без орудия (всего 3), и вероятность выбрать коридор с орудиями будет равна 1/3. Тогда оба самолета выберут защищенные коридоры с вероятностью 2/4·1/3 = 1/6. А вероятность того, что хотя бы один самолет не будет сбит, равна 1–1/6, то есть a₁₃ = 5/6.

A₂, B₃ – оба самолета летят одному коридору, орудия стоят по схеме (2+2+0+0). Объект будет уничтожен, если самолеты выберут незащищенный коридор. Незащищенных коридоров два, всего коридоров четыре, следовательно, a₂₃ = 2/4 = 1/2.

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

B_j A_i	B₁	B₂	B₃	минимум в строках α_i
A₁		1/2	5/6
A₂		3/4	1/2	1/2	максимин
максимум в столбцах β_j		3/4	5/6
		минимакс

Седловая точка отсутствует (нижняя цена игры равна 1/2, верхняя 3/4), поэтому решение ищем в смешанных стратегиях.

Для игрока A необходимо решить оптимизационную задачу

при ограничениях

Здесь только две независимых переменных x₁ и x₂, поэтому решение имеет наглядную геометрическую интерпретацию на плоскости.

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

(Рисунок приведен на следующей странице).

Поскольку во всех неравенствах стоят знаки ≥, допустимая область решения располагается выше этих трех прямых.

Нам необходимо минимизировать целевую функцию , то есть найти в допустимой области решения точку с минимальной суммой координат. Графически это означает, что нужно на плоскости провести прямую

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

В данной задаче искомая прямая проходит через точку, расположенную на пересечении прямой с прямой . Координата этой точки уже известна из первого уравнения. Подставляя это значение во второе уравнение, находим координату .

Таким образом, получаем решение оптимизационной задачи:

, .

Из выражения получаем цену игры:

ν = 5/8.

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

, .

Таким образом, если в серии налетов сторона A будет придерживаться оптимальной смешанной стратегией , заключающейся в том, что с вероятностью 3/8 будет посылать два самолета в разные коридоры (стратегия A₁) и с вероятностью 5/8 – оба самолета в один коридор (стратегия A₂), а сторона B будет придерживаться своей оптимальной смешанной стратегии, то вероятность поражения объекта будет равна 5/8. Если сторона B будет отклоняться от своей оптимальной смешанной стратегии, то вероятность поражения объекта может быть выше.

Найдем теперь оптимальную смешанную стратегию стороны B: . Если сторона A будет придерживаться своей оптимальной смешанной стратегии, а сторона B – своей, то средний проигрыш B (выигрыш A) будет равен цене игры ν = 5/8. Поэтому, исходя из матрицы игры, можно записать:

Учитывая, что , можно записать: . Подставив это выражение во второе уравнение, получим:

Решением этой системы будет: , . А из выражения получаем .

Таким образом, оптимальная смешанная стратегия стороны B: заключается в том, чтобы в серии налетов с вероятностью 1/8 ставить по одному орудию в каждый коридор и с вероятностью 5/8 ставить по два орудия в два коридора и оставлять два коридора без орудий.