Лекция: Игры, не содержащие седловой точки. Смешанные стратегии.

Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с седловой точкой. Более типичным является случай, когда нижняя и верхние цены не совпадают, причём, не трудно показать, что тогда .

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

. (1.4)

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

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

. (1.5)

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

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

Для ответа на этот вопрос введём вероятность (относительную частоту) применение игроком А i-й стратегии, и – вероятность применения j-й стратегии игроком В. Совокупности этих вероятностей определяют векторы, где и, где .

Эти векторы или наборы вероятностей выбора чистых стратегий называются смешанными стратегиями игроков.

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

Для получения ограничений на средний выигрыш или проигрыш рассмотрим математическое ожидание выигрыша первого игрока

. (1.6)

Если второй игрок В выбрал некоторую смешанную стратегию, то первому игроку, естественно, считать лучшей ту смешанную стратегию, при которой достигается :

. (1.7)

Аналогично, при выборе первым игроком некоторой стратегии второму игроку следует выбирать стратегию такую, что

. (1.8)

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

Основная теорема теории игр (доказана фон Нейманом в 1928 году) утверждает:

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

. (1.9)

Число называют ценой игры.

Примечание.Нулевая сумма означает, что выигрыш одного игрока равен проигрышу другого.

Из основной теоремы следует, что каждая конечная игра имеет цену и она лежит между нижней и верхней ценами игры (1.8).

И, если один из игроков придерживается своей оптимальной стратегии, то выигрыш (проигрыш) его остаётся неизменным независимо от тактики другого игрока, если, конечно, последний не выходит за пределы своих «полезных» стратегий, иначе выигрыш (проигрыш) возрастает.

Это означает выполнение неравенств

, (1.10)

,. (1.11)

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

2. Элементарные методы решения матричных игр,, .

Игра .

Наиболее простой матричной игрой является игра, в которой игроки имеют по две чистых стратегии.

Пусть матрица такой игры

. (2.1)

Если седловой точки нет, то решением игры являются смешанные стратегии (2.2)

. (2.3)

При стратегии В1 игрока В, При стратегии В2 игрока В.

Кроме того, .

Решение этих уравнений даёт:

, (2.4)

, (2.5)

. (2.6)

Аналогично, применение оптимальных стратегии обеспечивает проигрыш V игроку В при любых стратегиях А, что приводит к системе

(2.7)

Ее решение даётся формулами

(2.8)

(2.9)

Пример (п.2.1)

Во многих учебниках приводится пример игры в «орла и решку», суть которой состоит в следующем. Каждый из двух партнёров, не зная хода другого, кладёт свою монету орлом или решкой вверх и при совпадении наименований второй игрок (В) платит первому (А) единицу, а при несовпадении первый платит второму. Очевидно платёжная матрица такой игры будет:

Седловой точки нет. Тогда, согласно формул: (2.4), (2.5), (2.6), (2.8) и (2.9), оптимальными стратегиями будут

,, цена игры .

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

Пример (п.2.2)

Цех заготовитель поставляет в сборочный цех детали двух видов a и b. По договору между цехами оговорены ежедневно два срока поставки этих деталей, причём, при поставке в первый срок деталей вида «а» сборочный цех платит заготовительному премию 50 руб., при поставке же изделий «а» выплачивается премия 20 руб. При поставке же изделий вида «b» в первый срок премия составляет 30 руб., а во второй – 40 руб. Определить оптимальные стратегии поставок и получения деталей.

Решение. Принимая цех-заготовитель за игрока А, а сборочный за В, составим матрицу игры.

Таблица 2.1

Матрица игры заданная таблицей

	I срок	II срок
Детали «а» Детали «b»

Значит, ,

, следовательно, седловой точки нет. Для нахождения оптимальных стратегий применим формулы (2.4), (2.5), (2.6), (2.8) и (2.9):

; ;

(руб.).

Таким образом, цех-изготовитель поставляет детали вида а и b с вероятностями,, при этом гарантированная премия 35 рублей, а сборочный цех получает эти детали в сроки I и II с вероятностями, и выплачивает 35 рублей премии заготовительному цеху ежедневно. Полученные вероятности и определяют оптимальные стратегии

, .

Примечание. Игры допускают простое графическое толкование и решение, следующее из него. Действительно, пусть игра задана матрицей (2.1). На оси абсцисс отложим отрезок 0D, равный 1, и условимся считать, что левый конец отрезка – стратегии А2, тогда промежуточная точка N с координатой x соответствует некоторой смешанной стратегии первого игрока, причём,,, так как при имеем и, и при имеем и .

Вводя ось 0y, можно построить прямую, отвечающую стратегии второго игрока, её уравнение (при каждом x, y даёт значение выигрыша игрока А, когда В применяет стратегию В1). Отметим, что для построения В1 достаточно провести из концов отрезка 0D прямые, не перпендикулярные ему, на левой прямой отложить, на правой – и, соединив их получим прямую В1В1, отвечающую стратегии В1 рис. 2.1. Затем аналогично строим стратегию В2 (её уравнение ). Заметим, что при каждом x точки на прямых В1В1 и В2В2 отвечают выигрышем первого игрока при применении вторым игроком стратегий В2 и В1 соответственно. Откуда следует, что ломанаяВ2КВ1 рис. 2.2 отвечает нижней границе выигрыша игрока А, а значит в точке её максимума, то есть цена игры и точка N отвечает оптимальной стратегии игрока А: .

Для нахождения оптимальной стратегии игрока В, исходя из графика, можно воспользоваться формулами:

; (2.10)

. (2.11)

В справедливости формул (2.10) и (2.11) легко убедиться, подставив значения LB2 и LB1,, и значение, тогда получим формулы, совпадающие с (2.10) и (2.11).

Аналогично, меняя ролями x и y, можно построить решение для игрока А.

B1(50)

B2(40)

B1(30)