Доминирование стратегий

Если платежная матрица такова, что каждый элемент некоторой строки i не меньше соответствующего элемента строки k и по меньшей мере один ее элемент строго больше соответствующего элемента строки k, то говорят, что стратегия a_i, игрока 1 доминирует его стратегию a_k. Доминируемая стратегия a_k. не может быть оптимальной чистой стратегией игрока 1, или войти в его оптимальную смешанную стратегию с ненулевой вероятностью, поэтому ее можно исключить из рассмотрения, вычеркнув из матрицы строку k. Аналогично, если каждый элемент некоторого столбца j не больше соответствующего элемента столбца r и по меньшей мере один его элемент строго меньше соответствующего элемента столбца r, то говорят, что стратегия b_j игрока 2 доминирует его стратегию b_r. Поэтому столбец r матрицы можно вычеркнуть.

Игры в смешанных стратегиях

Однако существуют матрицы игры двух лиц с нулевой суммой (и таких игр большинство), для которых  ≤ , т.е. определенная выше седловая точка отсутствует.

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

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

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

для матричной игры т п обозначим через смешанную стратегию игрока 1, где

через ..., — смешанную стратегию игрока 2, где

Здесь — вероятности использования игроком 1 в смешанной стратегии своих чистых стратегий ,

- вероятности использования игроком 2 в смешанной стратегии своих чистых стратегий . Математическое ожидание выигрыша игрока 1:

.

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

Пусть Р* — смешанная стратегия игрока 1, Q* — смешанная стратегия игрока 2. Ситуацию (Р*, Q*). при которой M(Р, Q*) ≤ М(Р*, Q*) ≤ M(Р*, Q) называют седловой точкой смешанного расширения игры, а математическое ожидание выигрыша v = M(P*, Q*) — ценой игры, причем всегда  ≤  ≤.

Сведение игры двух лиц с нулевой суммой к задаче линейного программирования

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

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

Величина  неизвестна, но всегда можно предположить, что ‚ > 0. Это условие выполняется, поскольку всегда можно путем соответствующего преобразования матрицы сделать все ее элементы положительными.

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

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

Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 — чиcтую стратегию bj, то средний выигрыш игрока 1 (математическое ожидание выигрыша) составит

Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры, “, и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования:

(игрок 1 стремится максимизировать свой выигрыш)

или, обозначив , учитывая, что равнозначно

задачу можно переписать в виде:

причем

Поведению игрока 2 соответствует двойственная задача:

где

Целевая функция второго игрока т.е. игрок 2 стремится минимизировать свой средний проигрыш, и т.к. , имеем задачу с максимизацией критерия. Задача (1) всегда имеет решение. Получив ее оптимальное решение можно найти цену игры ‘оптимальные значения , и, следовательно, оптимальную стратегию игрока 1.

Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры значение v нужно уменьшить на d.