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

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

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

.                                  (4)

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

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

.                                               (5)

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

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

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

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

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

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

.                                     (6)

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

.                                  (7)

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

.                                  (8)

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

 

Исходя из рассмотренных определений, можно сделать следующие выводы:

1. Игра приобретает случайный характер.

2. Случайной становится величина выигрыша (проигрыша).

3. Средняя величина выигрыша (математическое ожидание выигрыша) является функцией от смешанных стратегий , и называется платежной функцией игры.

Стратегии  называются оптимальными, если для произвольных стратегий ,  выполняется условие .

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

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

Оптимальным решением игры называется совокупность оптимальных стратегий и цены игры.

Резюмируя все вышесказанное получаем:

 

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

.                     (9)

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

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

Теорема фон Неймана (основная теорема теории матричных игр): Любая матричная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях – две оптимальные стратегии и соответствующую им цену: .

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

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

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

,                                      (10)

, .                                     (11)

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

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

 

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

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

Упрощение игр

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

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

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

Аналогично рассмотрим две стратегии второго игрока - j - ю и l – ю, и при этом для элементов соответствующих столбцов матрицы выполняются условия: . Для второго игрока, как известно, более выгодной является стратегия, дающая меньший проигрыш, поэтому говорят, что j - я стратегия доминирует над l - й. Если попарные неравенства являются строгими, то говорят, что одна стратегия строго доминирует над другой. При этом, естественно, .

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

Пример 3. Упростить игру, заданную матрицей: .

Решение. Начнём упрощение с игрока А. Стратегия А₃ «дублирует» А₁ (А₃ = А₁). Следовательно, любую из них можно вычеркнуть (например, А₃). Далее сравнивая А₁ и А₂, видим, что элементы А₂ меньше или равны А₁ (А₂ ≤ А₁). Т.е. стратегия А₂ для игрока А желающего выиграть как можно больше, невыгодна. Т.о. Получаем матрицу .

Для игрока В, который стремится как можно меньше проиграть, В₃ невыгодна по сравнению с В₄ (В₃ > В₄). Вычёркиваем В_3. Т.о. игра 4×4 свелась к игре 2×3: .

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

Теорема. Оптимальные смешанные стратегии  соответственно 1 – го и 2 – го игроков в матричной игре  с ценой v будут оптимальными и в матричной игре  с ценой , где .

 

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

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

 

Упрощение игр

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

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

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

Аналогично рассмотрим две стратегии второго игрока - j - ю и l – ю, и при этом для элементов соответствующих столбцов матрицы выполняются условия: . Для второго игрока, как известно, более выгодной является стратегия, дающая меньший проигрыш, поэтому говорят, что j - я стратегия доминирует над l - й. Если попарные неравенства являются строгими, то говорят, что одна стратегия строго доминирует над другой. При этом, естественно, .

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

Пример 4. Упростить игру, заданную матрицей: .

Решение. Начнём упрощение с игрока А. Стратегия А₃ «дублирует» А₁ (А₃ = А₁). Следовательно, любую из них можно вычеркнуть (например, А₃). Далее сравнивая А₁ и А₂, видим, что элементы А₂ меньше или равны А₁ (А₂ ≤ А₁). Т.е. стратегия А₂ для игрока А желающего выиграть как можно больше, невыгодна. Т.о. Получаем матрицу .

Для игрока В, который стремится как можно меньше проиграть, В₃ невыгодна по сравнению с В₄ (В₃ > В₄). Вычёркиваем В_3. Т.о. игра 4×4 свелась к игре 2×3: .

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

Теорема. Оптимальные смешанные стратегии  соответственно 1 – го и 2 – го игроков в матричной игре  с ценой v будут оптимальными и в матричной игре  с ценой , где .

Пример 5. В матричной игре с платежной матрицей  примем b=10, C=-6 . Применим преобразование bA+ c, тогда получим игру с теми же оптимальными стратегиями, но с другой эквивалентной матрицей: .

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

Поделиться: