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

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

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

.                                  (4)

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

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

.                                               (5)

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

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

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

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

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

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

.                                     (6)

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

.                                  (7)

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

.                                  (8)

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

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

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

.                     (9)

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

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

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

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

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

,                                      (10)

, .                                     (11)

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

 

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: