1.2.2. Элементарные приемы решения игр 22

Пусть дана матричная (22)-игра . Может оказаться, что эта игра имеет седловую точку, если это так, то никакой проблемы нет. Предположим, что игра не имеет седловой точки. Отсюда следует, что оптимальные стратегии и должны иметь положительные компоненты. Далее, если цена игры есть , то

или

(1.10)

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

(1.11)

(1.12)

Тогда, поскольку и , левая часть в (1.10) будет строго меньше . Отсюда следует, что оба выражения, заключенные в скобки в (1.10), должны быть равны . Значит,

(1.13)

(1.14)

Аналогично можно показать, что

zx (1.15)

(1.16)

Тем самым мы установили в частном случае справедливость следующей важной теоремы.

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

Теперь присоединив к уравнениям (1.15), (1.16) соотношение

(1.17)

можем решить эту систему трех уравнений с тремя неизвестными и найти оптимальные вероятности и цену игры по формулам

(1.18)

Аналогично, составив систему из уравнений (1.13), (1.14)

(1.19)

находим оптимальную смешанную стратегию для игрока В.

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

Так точке для которой отвечает стратегия точке для которой - стратегия и так далее. По оси ординат будем откладывать выигрыши игрока А. При использовании стратегии выигрыш равен если второй игрок применяет если второй игрок применяет Следовательно, получим две точки Соответственно, при использовании стратегии выигрыши могут быть (при ) или (при ); они показаны двумя точками на перпендикуляре, восстановленном в точке Средний выигрыш при любом сочетании стратегий (с вероятностями ) и стратегии второго игрока равен и геометрически определяется ординатой, восстановленной в точке х до пересечения с отрезком Аналогично, средний выигрыш при использовании стратегии будет определяться ординатами точек, лежащих на отрезке

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

Следуя принципу максимина, получаем, что оптимальное решение игры определяет точка М, в которой этот минимальный выигрыш достигает максимума. Ей отвечает на оси абсцисс оптимальная стратегия а ее ордината равна цене игры По цене игры сразу находится оптимальная стратегия игрока В из уравнений (1.13) и (1.19).

На рисунке 1 можно показать нижнюю и верхнюю цены игры .

Если матрица игры имеет седловую точку, то получим следующие разновидности графического изображения игры.

1. Решением игры для игрока А является чистая стратегия (для игрока В – стратегия ), т.е. . Игра имеет седловую точку , равную цене игры (рис. 2).

2. Решение игры соответствует точке и задается векторами и . Игра имеет седловую точку Стратегия доминируемая и явно невыгодна для игрока В (рис. 3).

Пример 1.4

Проблема встречи у театра.

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

Виктор	Алла
		Рано	Поздно
	Рано	0	-1	-1
	Поздно	-3	0	-3
		0	0	0	-1

Легко убедиться, что и седловой точки нет, значит, эта игра требует смешанной стратегии. Используя формулы (1.18), получаем, что то есть Виктор должен приходить рано и поздно в отношении 3:1. Средний платеж равен

Для определения отношения можно из формул (1.18) вывести правило, которое легче запомнить, чем сами формулы (1.18). Именно, . Итак, чтобы найти относительные частоты смешивания чистых стратегий игрока А, достаточно вычесть второй столбец матрицы из первого и взять абсолютные величины получившихся чисел в обратном порядке. Так, применение этого правила к нашей матрице дает столбец:

Рано	1
Поздно	-3

что и дает решение . Отсюда, используя соотношение находим Цену игры теперь можно найти из соотношений (1.15), (1.16):

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

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

Алла
Рано	Поздно
3	-1

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

Упражнение 1.9

Решить и привести графическую иллюстрацию игр, заданных следующими матрицами:

1)	2)	3)
4)	5)	6)
7)	8)	9)
10)	11)	12)

Упражнение 1.10

День рождения.

После особенно напряженного трудового дня Василий спешит домой. Тут ему внезапно приходит в голову, что у Нади сегодня день рождения. А может быть нет? Все магазины уже закрыты, кроме цветочного. Если ее день рождения не сегодня и он не принесет никакого подарка, то положение будет нейтральным, т.е. платеж будет равен 0. Если у нее не день рождения и он ворвется с букетом цветов, то он рискует подвергнуться испытанию на трезвость, но он все-таки будет на высоте положения, и такой исход может быть оценен как 1. Если у Нади действительно день рождения и он вовремя вспомнил о нем, то это может быть справедливо оценено как 1,5 единицы. Если же в этом случае он не принесет ничего, то он погибший человек с оценкой –10. Что рекомендует теория игр Василию в этой ситуации?

Упражнение 1.11

Наступление и оборона.

У синих имеется два оборонительных сооружения. Они могут успешно оборонять какое-нибудь одно из них, но не оба вместе. Красные, в свою очередь, могут атаковать тоже только одно сооружение, а не оба одновременно. Сооружения имеют неодинаковую важность. Пусть значение менее важного сооружения оценивается единицей, а более важного – тремя единицами. Тогда, если уцелеют оба сооружения, то платеж будем считать равным 4, если уцелеет более важное – платеж равен 3, и, наконец, если уцелеет менее важное – платеж равен 1.

Составить матрицу игры и определить оптимальные стратегии каждой из сторон.