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

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

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

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

Если игра имеет седловую точку, то после упрощения получится игра 1 1.

Пример 1.3. Следует упростить матрицу игры:

.

Первая и четвертая строки равны, поэтому отбросим четвертую строку, а вероятность будет .

Получим матрицу .

Вторая строка доминирует на третьей строкой (). Поэтому отбросим третью строку, а вероятность будет .

Получим матрицу .

Второй столбец доминирует на третьим (. Поэтому отбросим третий столбец, а вероятность будет .

Получим матрицу .

Строки между собой несравнимы (), столбцы тоже (). Дальнейшее упрощение невозможно. Игра сведена от к игре .

Решение игры

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

Припишем строкам вероятности и соответственно.

.

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

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

Приравняем полученные зависимости: . Получим ,

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

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

.

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

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

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

Таким образом, каждую стратегию необходимо применять с частотой .

Пример 1.5. Найти решение игры из примера 1.2 в смешанных стратегиях.

Решение. Платежная матрица, построенная ранее:

Пусть первый игрок выбирает свою первую стратегию с вероятностью , а вторую – с вероятностью , т.е. первый игрок играет со смешанной стратегией .

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

а) гарантированный выигрыш первого игрока в зависимости от его смешанной стратегии

б) верхняя граница проигрыша второго игрока в зависимости от его смешанной стратегии

Рис. 1.1. – Гарантированный выигрыш первого игрока и верхняя граница проигрыша второго игрока в игре «Угадывание монеты» в зависимости от их смешанных стратегий»

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

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

- при где соответствует максимуму функции , второй игрок будет выбирать свою вторую стратегию, и первый игрок будет выигрывать

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

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

В рассматриваемом примере , определяемая из условия или .

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

Найдем оптимальную смешанную стратегию второго игрока.

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

Тогда проигрыш второго игрока, представленный на рисунке 1.1 б), равен:

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

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

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

Как видно из рис. 1.1, б, в данном случае , откуда .

Поэтому оптимальная смешанная стратегия второго игрока равна .

Решение игры

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

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

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

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

.

Первый столбец доминирует над третьим столбцом. Поэтому отбросим третий столбец. Вероятность . Получим матрицу .

Припишем строка вероятности и соответственно.

.

Получим линейные зависимости ; ; .

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

Рис. 1.2 – Графики функций линейных зависимостей , , и нижней огибающей ломаной прямой

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

, (вероятность применения игроком А своей первой стратегии),

(вероятность применения игроком А своей второй стратегии).

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

Примечание. Математическая функция СЛЧИС мастера формул пакета Excel возвращает случайное число; математические СЛЧИС ОК. У этой функции не оргументов. ОК. После этого в ячейке появится десятичная дробь из интервала (0,1). Исследователь берет нужное число знаков после запятой. После нажатия клавиши F9 десятичная дробь в ячейке изменится.

Найдем ненулевые вероятности выбора стратегий игроком B.

Используем матрицу

0

.

Имеем , т.е. , .

Для игрока А ; для игрока B .

Задача: Найти решение матричной игры Ответ: 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 – 3 q = 5 q – 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, сведя эту игру к паре взаимно двойственных задач линейного программирования.

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