- •Учебно-методические материалы Теоретический курс Тема 1. Задачи теории игр в экономике Математические модели игр
- •Основные понятия
- •Классификация игр
- •Тема 2. Математические модели игр
- •Тема 3. Антагонистические игры Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегия
- •Тема 4. Решение антагонистической игры с седловой точкой
- •Тема 5. Смешанные стратегии
- •Тема 6. Функции выигрыша в смешанных стратегиях
- •Тема 7. Решение игры в смешанных стратегиях
- •Тема 8. Критерии и свойства оптимальных стратегий
- •Тема 9. Принцип доминирования
- •Тема 10. Игры 2хп
- •Тема 11. Игры
- •Тема 12. Игры и их решение с помощью линейного программирования
- •Тема 13. Игры в условиях риска
- •Тема 14. Принятие решение в условиях риска на основе модели игры с природой
- •Тема 15. Игры в условиях неопределенности. Критерий принятия решений
- •Тема 16. Позиционные игры Понятие позиционной игры и ее нормальной формы
- •Графическое представление позиционной игры
- •Определение позиционной игры
- •Позиционные игры с полной информацией
- •Позиционные игры с идеальной памятью
Тема 9. Принцип доминирования
Отыскать решения игр без седловой точки, особенно при достаточно больших размерах платежной матрицы, оказывается довольно сложной задачей. В некоторых случаях эту задачу можно упростить с помощью редуцирования игр, т. е. сведения данной игры со сложной матрицей к игре с более простой матрицей. В этом параграфе мы рассмотрим один из способов редуцирования игр, основанный на принципе доминирования, который позволяет в некоторых случаях игру с матрицей большего размера свести к игре с матрицей меньшего размера.
Пусть имеем игру с матрицей
А= |
Ai |
|
|
… |
|
|
|
|
… |
|
|
|
|
|
… |
|
|
… |
… |
… |
… |
… |
|
|
|
|
... |
|
Каждой смешанной (в частности, чистой) стратегии игрока А поставим в соответствие строку
(9.1)
Строку (9.1) можно представить так:
(9.2)
Обратно, каждой выпуклой комбинации (9.2) строк матрицы А с коэффициентами поставим в соответствие смешанную стратегию игрока А.
Таким образом, между смешанными (в том числе и чистыми) стратегиями игрока А и выпуклыми комбинациями
строк матрицы А устанавливается взаимно-однозначное соответствие
(9.3)
Из (9.1) или (9.3) ясно, что каждой чистой стратегии игрока А ставится во взаимно-однозначное соответствие k-я строка матрицы А.
Если для двух выпуклых комбинаций строк матрицы А
(9.4)
(9.5)
выполняются неравенства
, (9.6)
то говорят, что строка (9.5) доминирует строку (9.4), а строка (9.4) доминируется строкой (9.5). Таким образом, строка (11.5) — доминирующая строку (9.4), а строка (9.4) — доминируемая строкой (9.5).
Если каждое из неравенств (9.6) является равенством, то строки (9.4) и (9.5) называют дублирующими друг друга. Каждая из двух дублирующих строк является одновременно и доминируемой, и доминирующей другую.
Если каждое из неравенств (9.6) является строгим, то говорят, что строка (9.5) строго доминирует строку (9.4), а строка (9.4) строго доминируется строкой (9.5), или строка (9.5) является строго доминирующей строку (9.4), а строка (9.4) является строго доминируемой строкой (9.5).
Аналогичная терминология используется и для соответствующих стратегий игрока А. А именно, если строка (9.5) доминирует, соответственно дублирует, соответственно строго доминирует строку (9.4), то говорят, что стратегия доминирует, соответственно дублирует, соответственно строго доминирует стратегию .
Так как элементами строк, соответствующих по (9.3) смешанным стратегиям, являются выигрыши игрока А (см. (9.1)), то из данных определений понятно, что для игрока А дублирующие стратегии равнопредпочтительны, а доминируемая не дублирующая стратегия заведомо для него невыгодна.
Аналогично, каждой смешанной (в частности, чистой) стратегии игрока В поставим в соответствие столбец
(9.7)
Если для двух выпуклых комбинаций столбцов матрицы А
, (9.8)
(9.9)
справедливы неравенства
, ,..., , (9.10)
то говорят, что столбец (9.8) (стратегия ) доминирует столбец (9.9) (стратегию ) а столбец (9.9) (стратегия ) доминируется столбцом (9.8) (стратегией ).
В случае, когда каждое неравенство (9.10) является равенством, столбцы (9.8) и (9.9) (стратегии и ) называются дублирующими.
Если каждое неравенство (9.10) является строгим, то столбец (9.8) (стратегия ) называется строго доминирующим (строго доминирующей) столбец (9.9) (стратегию ), а столбец (11.11) (стратегия ) - строго доминируемым (строго доминируемой) столбцом (11.10) (стратегией ).
Теорема 9.1. Справедливы следующие предложения.
1 .Если -я строка, , матрицы А игры доминируется некоторой выпуклой комбинацией остальных ее строк, то существует оптимальная смешанная стратегия игрока А, в которой -я чистая стратегия выбирается им с нулевой вероятностью, т.е .
2. Если -я строка, , матрицы игры строго доминируется некоторой выпуклой комбинацией остальных ее строк, то в любой оптимальной смешанной стратегии игрока А чистая -я стратегия выбирается им с нулевой вероятностью, т.е. .
3. Если -й столбец, , матрицы А игры доминируется некоторой выпуклой комбинацией остальных ее столбцов, то существует оптимальная смешанная стратегия игрока В, в которой -я чистая стратегия выбирается им с нулевой вероятностью, т.е. .
4. Если -й столбец, , матрицы А игры строго доминируется некоторой выпуклой комбинацией остальных ее столбцов, то в любой оптимальной смешанной стратегии игрока В чистая -я стратегия выбирается им с нулевой вероятностью, т е. .
Следствие 9.1.
1. Если -я строка матрицы игры доминируется (строго доминируется) некоторой другой строкой, то существует (любая) оптимальная смешанная стратегия игрока А, в которую чистая стратегия входит с нулевой вероятностью.
2. Если -й столбец матрицы игры доминируется (строго доминируется) некоторым другим столбцом, то существует (любая) оптимальная смешанная стратегия игрока В, в которую чистая стратегия входит с нулевой вероятностью.
Следствие 9.2 (о дублирующих чистых стратегиях). Одну из двух дублирующих чистых стратегий можно удалить.
Пример 11.1. Рассмотрим игру 3x5 с матрицей
|
|
|
|
|
|
(9.11) |
|
-2 |
1 |
3 |
0 |
1 |
|
|
-1 |
-4 |
2 |
-1 |
-4 |
|
|
1 |
-5 |
6 |
3 |
-5 |
В данной матрице и - дублирующие стратегии игрока В. Поэтому в соответствии со следствием 9.2 один из этих столбцов можно удалить. Удалим, например, 5-й столбец. В оставшейся матрице 3-й Столбец строго, а 4-й столбец нестрого доминируются 1-м столбцом. Поэтому можно удалить также 3-й и 4-й столбцы. В результате получим матрицу
|
|
|
(9.12) |
|
-2 |
1 |
|
|
-1 |
-4 |
|
|
1 |
-5 |
2-я строка матрицы (9.12) строго доминируется выпуклой комбинацией 1-й и 3-й строк с коэффициентами и :
Поэтому нужно отбросить 2-ю строку. В результате получим матрицу
|
|
|
(9.13) |
|
-2 |
1 |
|
|
1 |
-5 |
Нижняя цена в чистых стратегиях игры с матрицей (11.25) , а верхняя цена . Так как , то решение надо искать в смешанных стратегиях. Предположим, что и - оптимальные стратегии игроков и V - цена игры с матрицей (9.13). Тогда по необходимым условиям оптимальности стратегий, сформулированным в теореме 9.2, имеем:
(9.14)
Умножив 1-е неравенство системы (9.14) на 2 и прибавив ко 2-му, получим
(9.15)
Умножив 3-е неравенство системы (9.4) на 2 и прибавив к 4-му, получим
(9.16)
Из неравенств (9.15) и (9.16) следует равенство . Подставим найденное значение V в систему (9.15):
(11.29)
Из первых двух уравнений системы (11.29): , а из вторых двух уравнений: .
Учитывая удаленные столбцы и строку для исходной игры с матрицей (11.11), получим следующее (частное) решение:
.
Поскольку 4-й столбец матрицы (11.23) нестрого доминировался 1-м столбцом, то могут существовать и другие оптимальные стратегии игрока В, в которых чистая стратегия будет входить с положительной вероятностью.