Комплексное применение приемов при решении задач теории матричных игр с нулевой суммой 2 страница

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

	В1	В2	B3	B4
А1							В1	В2	B3	B4
А2					~	А1
A3						А2
A4

6. Для выявления доминируемых столбцов проведем их поэлементное сравнение:

	В1 и В2	В1 и В3	В1 и В4	В2 и В3	В2 и В4	В3 и В4
А1	7>3	7<8	7>2	—	3>2	—
А2	3<7	3<5	3<9	—	7<9	—

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

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

	В1	В2	B3	B4			В1	В2	B4
А1					~	А1
А2						А2

7. Проведем проверку оставшихся стратегий Получателя и сделаем выводы:

	В1	В2	B4
А1 и А2	7>3	3<7	2>9

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

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

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

Обозначим: – частотность использования Получателем стратегии А2. Выполним графическое построение: отрезок, соответствующий стратегии В1, соединяет величины платежа (при и (при . Отрезок, соответствующий стратегии В2, соединяет величины платежа (при ) и (при ). Отрезок, соответствующий стратегии В3, соединяет величины платежа (при ) и (при ).

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

- Точка М имеет координаты (то есть ) и , – обе стратегии Получателя являются активными, позволяя ему достигать цену игры, превосходящую значение .

- Точка М соответствует пересечению отрезков, соответствующих стратегиям Плательщика В1 и В2, – именно эти стратегии являются активными.

- Платежную матрицу можно упростить:

	В1	В2	B4			В1	В2
А1				~	А1
А2					А2

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

Ответ:

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

- Поэлементное сравнение стратегий позволяет выявить и исключить из рассмотрения заведомо невыгодные стратегии игроков А3, А4 и В3. Активные стратегии Получателя – А1 и А2.

- Графический метод позволяет выявить активные стратегии Плательщика – В1 и В2.

- Для выявленных активных стратегий Плательщица и Получателя установлено: смешанная стратегия Получателя состоит в применении стратегий А1 и А2 с равной частотностью ; смешанная стратегия Плательщика состоит в применении стратегий В1 и В2 с равной частотностью ; цена игры .

Пример 10. Для данной платежной матрицы:

- найти нижнюю и верхнюю цены игры;

- упростить данную платежную матрицу, исключив из неё доминируемые строки и столбцы, соответствующие заведомо невыгодным стратегиям игроков;

- выявить активные стратегии игроков графическим методом;

- найти решение игры: смешанные стратегии игроков и цену игры.

Решение:

1. Введем обозначения стратегий первого игрока (Получателя) и второго игрока (Плательщика):

	В1	В2	B3	B4
А1
А2
A3
A4

2. В каждой строке выявим наименьшее значение, и из этих результатов – наибольшее:

	В1	В2	B3	B4
А1
А2
A3
A4

Нижняя цена игры (реализуется при использовании Получателем стратегии А2).

3. В каждом столбце выявим наибольшее значение, и из этих результатов – наименьшее:

	В1	В2	B3	B4
А1
А2
A3
A4

Верхняя цена игры (реализуется при использовании Плательщиком стратегий В3 и B4).

4. По результатам пп. 2,3 сделаем выводы: верхняя и нижняя цены игры не совпадают, значит, игра не имеет решения в чистых стратегиях (следует искать смешанную стратегию), и цена игры лежит в диапазоне .

5. Для выявления доминируемых строк платежной матрицы проведем их поэлементное сравнение:

	В1	В2	B3	B4
A1 и А2	6>3	4<2	0<1	0<2
A1 и A3	6<7	4<9	0=0	0<1
A1 и A4	—	—	—	—
А2 и A3	3<7	2<9	1>0	2>1
А2 и A4	3>0	2<7	1<5	2<5
А3 и A4	7>0	9>7	0<5	1<5

Вывод: в выделенной строке таблицы знаки неравенств – одинаковые, строку №1 можно исключить из платежной матрицы по сравнению со строкой №3 (стратегия А3 доминирует стратегию А1). Дальнейшее сравнение доминируемой стратегии А1 не проводилось.

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

	В1	В2	B3	B4			В1	В2	B3	B4
А1						А2
А2					~	A3
A3						A4
A4

6. Для выявления доминируемых столбцов проведем их поэлементное сравнение:

	В1 и В2	В1 и В3	В1 и В4	В2 и В3	В2 и В4	В3 и В4
А2	3>2	3>1	3>2	2>1	—	1<2
А3	7<9	7>0	7>1	9>0	—	0<1
А4	0<7	0<5	0<5	7>5	—	5=5

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

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

	В1	В2	B3	B4			В1	B3
А2						А2
A3					~	A3
A4						A4

7. Проведем проверку оставшихся стратегий Получателя и сделаем выводы:

	В1	B3
А2 и A3	3<7	1>0
А2 и A4	3>0	1<5
А3 и A4	7>0	0<5

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

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

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

Обозначим: – частотность использования Плательщиком стратегии В3. Выполним графическое построение: отрезок, соответствующий стратегии А2, соединяет величины платежа (при и (при . Отрезок, соответствующий стратегии А3, соединяет величины платежа (при ) и (при ). Отрезок, соответствующий стратегии А4, соединяет величины платежа (при и (при ).

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

- Точка М имеет координаты (то есть ) и , – обе стратегии Плательщика являются активными, позволяя ему достигать цену игры, превосходящую значение .

- Точка М соответствует пересечению отрезков, соответствующих стратегиям Получателя А3 и А4, – именно эти стратегии являются активными.

- Платежную матрицу можно упростить:

	В1	B3
А2					В1	B3
A3			~	A3
A4				A4

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

Ответ:

- Нижняя цена игры , верхняя цена игры .

- Поэлементное сравнение стратегий позволяет выявить и исключить из рассмотрения заведомо невыгодные стратегии игроков А1, В2 и В4. Активные стратегии Плательщика – В1 и В3.

- Графический метод позволяет выявить активные стратегии Получателя – А3 и А4.

- Для выявленных активных стратегий Плательщица и Получателя установлено: смешанная стратегия Получателя состоит в применении стратегий А3 и А4 с частотностями и соответственно; смешанная стратегия Плательщика состоит в применении стратегий В1 и В3 с частотностями и соответственно; цена игры .

Пример 11. Для данной платежной матрицы:

- найти нижнюю и верхнюю цены игры;

- упростить данную платежную матрицу, исключив из неё доминируемые строки и столбцы, соответствующие заведомо невыгодным стратегиям игроков;

- выявить активные стратегии игроков и найти решение игры: смешанные стратегии игроков и цену игры.

Решение:

1. Введем обозначения стратегий первого игрока (Получателя) и второго игрока (Плательщика):

	В1	В2	B3	B4
А1
А2
A3
A4

2. В каждой строке выявим наименьшее значение, и из этих результатов – наибольшее:

	В1	В2	B3	B4
А1
А2
A3
A4

Нижняя цена игры (реализуется при использовании Получателем стратегии А1).

3. В каждом столбце выявим наибольшее значение, и из этих результатов – наименьшее:

	В1	В2	B3	B4
А1
А2
A3
A4

Верхняя цена игры (реализуется при использовании Плательщиком стратегии В1).

4. По результатам пп. 2,3 сделаем выводы: верхняя и нижняя цены игры не совпадают, значит, игра не имеет решения в чистых стратегиях (следует искать смешанную стратегию), и цена игры лежит в диапазоне .

5. Для выявления доминируемых строк платежной матрицы проведем их поэлементное сравнение:

	В1	В2	B3	B4
A1 и А2	3<6	7>2	7=7	6<8
A1 и A3	3<6	7>2	7>4	6<8
A1 и A4	3<4	7<9	7<9	6>0
А2 и A3	6=6	2=2	7>4	8=8
А2 и A4	6<4	2<9	7<9	8>0
А3 и A4	—	—	—	—

Вывод: в выделенной строке таблицы знаки неравенств – одинаковые, строку №3 можно исключить из платежной матрицы по сравнению со строкой №2 (стратегия А2 доминирует стратегию А3). Дальнейшее сравнение доминируемой стратегии А3 не проводилось.

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

	В1	В2	B3	B4			В1	В2	B3	B4
А1						А1
А2					~	A2
A3						A4
A4

6. Для выявления доминируемых столбцов проведем их поэлементное сравнение:

	В1 и В2	В1 и В3	В1 и В4	В2 и В3	В2 и В4	В3 и В4
А2	3<7	3<7	3<6	—	7>6	—
А3	6>2	6<7	6<8	—	2<8	—
А4	4<9	4<9	4>0	—	9>0	—

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

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

	В1	В2	B3	B4			В1	В2	B4
А1						А1
A2					~	A2
A4						A4

7. Проведем проверку оставшихся стратегий Получателя и сделаем выводы:

	В1	В2	B4
А1 и A2	3<6	7>2	6<8
А1 и A4	3<4	7<9	6>0
А2 и A4	6>4	2<9	8>0

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

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

8. Так как ни для Получателя, ни для Плательщика не выявлена пара активных стратегий, применить графический метод (на плоскости) для выявления активных стратегий другого игрока невозможно. Для нахождения решения игры следует сформулировать соответствующую задачу линейного программирования (ЛП) и, получив её решение хотя бы для одного из игроков, вернуться к рассмотрению «игровой» задачи.

Дата добавления: 2014-12-27