Дублирование и доминирование стратегий

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

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

Аналогично, если i-й столбец поэлементно не меньше j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок не использует i-ю стратегию. Так как его проигрыш (равный выигрышу игрока ) при j-й стратегии не больше ( ), чем при i-й стратегии, вне зависимости от того, как играет игрок . Это – доминирование стратегий.

Задача: Найти решение матричной игры Ответ: v=4/11,

Пример 1.7. Рассмотрим игру с платежной матрицей

Требуется найти оптимальные смешанные стратегии игроков.

Решение. Проверим, имеет ли данная игра седловую точку в чистых стратегиях.

Нижняя цена игры

Верхняя цена игры

т. е. , значит, седловой точки в чистых стратегиях в игре нет.

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

В рассматриваемом примере

,

,

,

.

Графики этих функций построены на рис.1.3.

Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: . Эта функция отмечена на рис. 1.3 жирной линией.

При , где определяется из условия второй игрок будет выбирать свою вторую стратегию, и первый игрок будет выигрывать

При , второй игрок будет выбирать первую стратегию, и первый игрок будет выигрывать .

Наилучший для первого игрока выбор при этом соответствует .

Рис. 1.3. Гарантированный выигрыш первого игрока в примере 1.4 при различном выборе смешанной стратегии

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

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

Тогда проигрыш второго игрока равен:

, если первый игрок выбирает свою первую стратегию,

, если первый игрок выбирает свою вторую стратегию.

Значение определяется из условия , оно равно .

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

Решение игры

Приписав первому столбцу вероятность , а второму столбцу – вероятность , получим линейных зависимостей. Изобразим их графики.

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

Пусть это точка пересечения i-й и j-й прямых. Тогда припишем i-й строке вероятность , а j-й строка вероятность . Всем остальным строкам припишем нулевые вероятности. Находим и .

Пример 1.8. Найти решение матричной игры

.

Припишем столбцам вероятности и соответственно:

Получим линейные зависимости (1), (2), (3).

Изобразим их графики. .

Возьмем верхнюю огибающую. Это ломаная ABCD. Точка В – это точка с наименьшей второй координатой на этой огибающей. Точка В – это точка пересечения прямых (1) и (2). Поэтому припишем первой строке вероятность p, а второй строке – вероятность 1 – p. Всем остальным строкам припишем нулевые вероятности. Найдем координаты точки В.

4 – 3q = 5q – 2, q = (вероятность применения игроком В своей первой стратегии), 1 – q = (вероятность применения игроком В своей второй стратегии). Все цифры игрок В делит на полноценные «четверки». Первые три цифры относятся к первой стратегии, а последняя – ко второй стратегии: первая стратегия (1, 2, 3, 5, 6, 7) и вторая стратегия (4, 8). Перед своим очередным ходом игрок А смотрит в таблицу случайных чисел. Если «выпадает» 4, 8, то он играет вторую стратегию. Цена игры v = w = . Цифры 0 и 9 игнорируются.

Найдем решение для игрока А: .

, то есть p = , 1 ‑ p = . Для игрока А p^* = ( для игрока В q^* = ( .

Задача: Найти решение матричной игры Ответ: ,

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

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

Теорема.В любой матричной игре у игроков есть оптимальные смешанные стратегии.

Доказательство. Пусть рассматривается игра с платежной матрицей A (1.1), все элементы которой строго положительны; и — смешанные стратегии первого и второго игрока.

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

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

(1.2)

При этом ; ;

Введем новые обозначения

,

и разделим все неравенства системы (1.2) на положительное число r, получим следующую систему:

(1.3)

При этом ; ; .

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

Цель первого игрока – максимизировать свой гарантированный выигрыш r или, соответственно, минимизировать величину .

Следовательно, приходим к задаче линейного программирования для первого игрока:

,

, (1.4)

;

Аналогичные рассуждения с позиции второго игрока приводят к задаче линейного программирования, двойственной к задаче для первого игрока:

,

, (1.5)

;

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

Например, ,

Следовательно, задача (1.4) имеет допустимое решение.

Допустимым решением задачи (1.5) является, очевидно, нулевой вектор.

Лекция 3. Матричные игры (продолжение)

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

.

Покажем, что цена игры , а оптимальные смешанные стратегии игроков равны соответственно:

Действительно, пусть и – произвольные смешанные стратегии игроков, тогда

(1.6)

= (1.7)

(1.8)

Из (1.6) следует, что , из (1.7) следует, что , а из (1.8) следует, что одновременно

(так как )

и

(так как ),

Значит .

Итак, , , , поэтому

.

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

Если же в платежной матрице есть отрицательные элементы или нули, то можно добавить ко всем элементам матрицы одно и то же достаточно большое положительное число b, так чтобы все элементы матрицы были положительными.

Обозначим математическое ожидание выигрыша первого игрока в игре с платежной матрицей , а – математическое ожидание выигрыша первого игрока в игре с платежной матрицей .

При этом

,

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

или

,

откуда

,

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

.

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

Решение. От платежной матрицы

путем добавления положительного числа перейдем к матрице,

все элементы которой положительны.

Сведем данную матричную игру к паре двойственных задач линейного программирования (согласно теореме 1.2):

,

, , , .

Решаем уравнения из первой системы уравнений первое и второе, так как третье и четвертое дает отрицательные значения х, получаем:

.

Так как выбрали в системе x первые два уравнения, то в системе y зануляются и .

.

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

(

и

,

а цена игры

.