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

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

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

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

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

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

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

Первая и четвертая строки равны, поэтому отбросим четвертую строку, а вероятность будет Дублирование и доминирование стратегий - student2.ru .

Получим матрицу Дублирование и доминирование стратегий - student2.ru .

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

Получим матрицу Дублирование и доминирование стратегий - student2.ru .

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

Получим матрицу Дублирование и доминирование стратегий - student2.ru .

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

Решение игры Дублирование и доминирование стратегий - student2.ru

Пример 1.4. Найдем решение матричной игры Дублирование и доминирование стратегий - student2.ru

Припишем строкам вероятности Дублирование и доминирование стратегий - student2.ru и Дублирование и доминирование стратегий - student2.ru соответственно.

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

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

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

Приравняем полученные зависимости: Дублирование и доминирование стратегий - student2.ru . Получим Дублирование и доминирование стратегий - student2.ru ,

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

Припишем столбцам вероятности Дублирование и доминирование стратегий - student2.ru и Дублирование и доминирование стратегий - student2.ru соответственно.

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

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

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

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

Приравняем полученные зависимости: Дублирование и доминирование стратегий - student2.ru . Имеем Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru , т.е. оптимальная смешанная стратегия игрока Дублирование и доминирование стратегий - student2.ru Дублирование и доминирование стратегий - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- при Дублирование и доминирование стратегий - student2.ru второй игрок будет выбирать первую стратегию, и первый игрок будет выигрывать Дублирование и доминирование стратегий - student2.ru .

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

В рассматриваемом примере Дублирование и доминирование стратегий - student2.ru , определяемая из условия Дублирование и доминирование стратегий - student2.ru или Дублирование и доминирование стратегий - student2.ru .

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

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

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

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

Дублирование и доминирование стратегий - student2.ru , если первый игрок выбирает свою первую стратегию,

Дублирование и доминирование стратегий - student2.ru , если первый игрок выбирает свою вторую стратегию.

Наилучшее с точки зрения второго игрока значение Дублирование и доминирование стратегий - student2.ru определяется из условия Дублирование и доминирование стратегий - student2.ru .

Как видно из рис. 1.1, б, в данном случае Дублирование и доминирование стратегий - student2.ru , откуда Дублирование и доминирование стратегий - student2.ru .

Поэтому оптимальная смешанная стратегия второго игрока равна Дублирование и доминирование стратегий - student2.ru .

Решение игры Дублирование и доминирование стратегий - student2.ru

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

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

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

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

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

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

Припишем строка вероятности Дублирование и доминирование стратегий - student2.ru и Дублирование и доминирование стратегий - student2.ru соответственно.

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

Получим линейные зависимости Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru .

Изобразим их графики. Дублирование и доминирование стратегий - student2.ru .

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

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

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

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru (вероятность применения игроком А своей первой стратегии),

Дублирование и доминирование стратегий - student2.ru (вероятность применения игроком А своей второй стратегии).

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

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

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

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

Дублирование и доминирование стратегий - student2.ru 0 Дублирование и доминирование стратегий - student2.ru

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

Имеем Дублирование и доминирование стратегий - student2.ru , т.е. Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru .

Для игрока А Дублирование и доминирование стратегий - student2.ru ; для игрока B Дублирование и доминирование стратегий - student2.ru .

Задача: Найти решение матричной игры Дублирование и доминирование стратегий - student2.ru Ответ: v=4/11,

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

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

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

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

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

Нижняя цена игры Дублирование и доминирование стратегий - student2.ru

Верхняя цена игры Дублирование и доминирование стратегий - student2.ru

т. е. Дублирование и доминирование стратегий - student2.ru , значит, седловой точки в чистых стратегиях в игре нет.

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

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

Дублирование и доминирование стратегий - student2.ru ,

Дублирование и доминирование стратегий - student2.ru ,

Дублирование и доминирование стратегий - student2.ru ,

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

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

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

При Дублирование и доминирование стратегий - student2.ru , где Дублирование и доминирование стратегий - student2.ru определяется из условия Дублирование и доминирование стратегий - student2.ru второй игрок будет выбирать свою вторую стратегию, и первый игрок будет выигрывать Дублирование и доминирование стратегий - student2.ru

При Дублирование и доминирование стратегий - student2.ru , второй игрок будет выбирать первую стратегию, и первый игрок будет выигрывать Дублирование и доминирование стратегий - student2.ru .

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

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

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

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

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

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

Дублирование и доминирование стратегий - student2.ru , если первый игрок выбирает свою первую стратегию,

Дублирование и доминирование стратегий - student2.ru , если первый игрок выбирает свою вторую стратегию.

Значение Дублирование и доминирование стратегий - student2.ru определяется из условия Дублирование и доминирование стратегий - student2.ru , оно равно Дублирование и доминирование стратегий - student2.ru .

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

Решение игры Дублирование и доминирование стратегий - student2.ru

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

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

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

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

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

Припишем столбцам вероятности Дублирование и доминирование стратегий - student2.ru и Дублирование и доминирование стратегий - student2.ru соответственно:

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

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

Получим линейные зависимости Дублирование и доминирование стратегий - student2.ru (1), Дублирование и доминирование стратегий - student2.ru (2), Дублирование и доминирование стратегий - student2.ru (3).

Изобразим их графики. Дублирование и доминирование стратегий - student2.ru .

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

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

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

Найдем решение для игрока А: Дублирование и доминирование стратегий - student2.ru Дублирование и доминирование стратегий - student2.ru .

Дублирование и доминирование стратегий - student2.ru , то есть p = Дублирование и доминирование стратегий - student2.ru , 1 ‑ p = Дублирование и доминирование стратегий - student2.ru . Для игрока А p* = ( Дублирование и доминирование стратегий - student2.ru для игрока В q* = ( Дублирование и доминирование стратегий - student2.ru .

Задача: Найти решение матричной игры Дублирование и доминирование стратегий - student2.ru Ответ: Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru

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

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

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

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

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

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

Дублирование и доминирование стратегий - student2.ru (1.2)

При этом Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru

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

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru

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

Дублирование и доминирование стратегий - student2.ru (1.3)

При этом Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru .

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

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

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

Дублирование и доминирование стратегий - student2.ru ,

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru (1.4)

Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru

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

Дублирование и доминирование стратегий - student2.ru ,

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru (1.5)

Дублирование и доминирование стратегий - student2.ru ; Дублирование и доминирование стратегий - student2.ru

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

Например, Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru

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

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

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

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

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

Покажем, что цена игры Дублирование и доминирование стратегий - student2.ru , а оптимальные смешанные стратегии игроков равны соответственно:

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

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

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

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

Дублирование и доминирование стратегий - student2.ru (1.6)

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

= Дублирование и доминирование стратегий - student2.ru (1.7)

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

Дублирование и доминирование стратегий - student2.ru (1.8)

Из (1.6) следует, что Дублирование и доминирование стратегий - student2.ru , из (1.7) следует, что Дублирование и доминирование стратегий - student2.ru , а из (1.8) следует, что одновременно

Дублирование и доминирование стратегий - student2.ru (так как Дублирование и доминирование стратегий - student2.ru )

и

Дублирование и доминирование стратегий - student2.ru (так как Дублирование и доминирование стратегий - student2.ru ),

Значит Дублирование и доминирование стратегий - student2.ru .

Итак, Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru , поэтому

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

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

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

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

При этом

Дублирование и доминирование стратегий - student2.ru ,

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

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

или

Дублирование и доминирование стратегий - student2.ru ,

откуда

Дублирование и доминирование стратегий - student2.ru ,

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

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

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

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

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

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

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

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

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

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

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

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru

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

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

Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru , Дублирование и доминирование стратегий - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

Дублирование и доминирование стратегий - student2.ru ( Дублирование и доминирование стратегий - student2.ru

и

Дублирование и доминирование стратегий - student2.ru ,

а цена игры

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

Наши рекомендации