Лекция: Игры со смешанными стратегиями

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

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

Х = (х1…хi…хm) – смешанная стратегия первого игрока.

У = (у1…уj…уn) – смешанная стратегия второго игрока.

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

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

. (1.5)

Если Х* = (х1*….хi*…хm*) – оптимальная стратегия, выбранная первым игроком; Y* = (у1*…уj*…уn*) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.

(1.6)

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

(1.7)

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

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

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

А = (1.8)

y1 y2y3

Решение:

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

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

(1.9)

у1 + у2 + у3 = 1 (1.10)

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

(1.11)

. (1.12)

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

(1.13)

х1 + х2 + х3 = 1. (1.14)

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

(1.15)

, (1.16)

где .

Если нам необходимо определить стратегию поведения первого игрока, т.е. относительную частоту использования его стратегий (х1….х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.

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