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

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

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

Х = (х₁…х_i…х_m) – смешанная стратегия первого игрока.

У = (у₁…у_j…у_n) – смешанная стратегия второго игрока.

x_i, у_j – относительные частоты (вероятности) использования игроками своих стратегий.

Условия использования смешанных стратегий

. (1.5)

Если Х * = (х ₁^*…. х _i^*… х_m ^*) – оптимальная стратегия, выбранная первым игроком; Y * = (у ₁^*… у _j^*… у_n ^*) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.

(1.6)

Для того чтобы число V было ценой игры, а х ^* и у ^* - оптимальными стратегиями, необходимо и достаточно выполнение неравенств

(1.7)

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

Сведения задач теории игр к задачам линейного программирования.

Пример. Найти решение игры, определяемой платежной матрицей А.

А = (1.8)

y ₁ y ₂ y ₃

Решение:

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

Для первого игрока

(1.9)

у ₁ + у ₂ + у ₃ = 1 (1.10)

Освобождаясь от переменной V (цена игры), разделим левую и правую часть выражений (1.9), (1.10) на V. Приняв у_j / V за новую переменную z_i, получим новую систему ограничений (1.11) и целевую функцию (1.12)

(1.11)

. (1.12)

Аналогично получим модель игры для второго игрока:

(1.13)

х ₁ + х ₂ + х ₃ = 1. (1.14)

Приведя модель (1.13), (1.14) к форме без переменной V, получим

(1.15)

, (1.16)

где .

Если нам необходимо определить стратегию поведения первого игрока, т.е. относительную частоту использования его стратегий (х ₁…. х_i…х_m), мы будем использовать модель второго игрока, т.к. эти переменные находятся в его модели выигрыша (1.13), (1.14).

Решение полученных моделей произведем в среде MS Excel 2007 с помощью надстройки “Поиск решения”. На рисунках 1, 2, 3 и 4 приведены скриншоты этапов решения задачи линейного программирования (1.11)-(1.12).

Ячеки с адресами A2:C2 выделены для переменных . В ячейках A5:A7 введены формулы (рис. 3) левых частей системы неравенств (1.11). В ячейках с адресами B5:B7 введены правые части системы неравенств (1.11). В ячейке с адресом F6 (рис. 4) введена формула целевой функции (1.12). Найденное решение с помощью надстройки MS Excel 2007 “Поиск решения” для рассматриваемого примера: . Тогда, в соответствии с (1.12), значение цены V игры равно 1 и соответственно . Т.е., для второго игрока оптимальная стратегия поведения выглядит следующим образом .

Аналогично получаем оптимальную стратегию поведения первого игрока, решая в среде MS Excel задачу линейного программирования (1.13)-(1.14). Для рассматриваемого примера оптимальная стратегия поведения первого игрока будет .

Рисунок 1.

Рисунок 2.

Рисунок 3.

Рисунок 4.

ВАРИАНТЫ ЗАДАНИЙ