- •Учебно-методические материалы Теоретический курс Тема 1. Задачи теории игр в экономике Математические модели игр
- •Основные понятия
- •Классификация игр
- •Тема 2. Математические модели игр
- •Тема 3. Антагонистические игры Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегия
- •Тема 4. Решение антагонистической игры с седловой точкой
- •Тема 5. Смешанные стратегии
- •Тема 6. Функции выигрыша в смешанных стратегиях
- •Тема 7. Решение игры в смешанных стратегиях
- •Тема 8. Критерии и свойства оптимальных стратегий
- •Тема 9. Принцип доминирования
- •Тема 10. Игры 2хп
- •Тема 11. Игры
- •Тема 12. Игры и их решение с помощью линейного программирования
- •Тема 13. Игры в условиях риска
- •Тема 14. Принятие решение в условиях риска на основе модели игры с природой
- •Тема 15. Игры в условиях неопределенности. Критерий принятия решений
- •Тема 16. Позиционные игры Понятие позиционной игры и ее нормальной формы
- •Графическое представление позиционной игры
- •Определение позиционной игры
- •Позиционные игры с полной информацией
- •Позиционные игры с идеальной памятью
Тема 10. Игры 2хп
Рассмотрим игру с матрицей
|
|
|
|
… |
|
A= |
|
|
|
… |
|
|
|
|
|
… |
|
В этой игре игрок А обладает двумя чистыми стратегиями и , а игрок В имеет п чистых стратегий , ,…, .
Известно, что показатель эффективности стратегии
Если , то , поскольку . Тогда будет выражаться формулой
Таким образом, представляет собой нижнюю огибающую п линейных функций , от вероятности , график каждой из которых есть отрезок, возрастающий (положительного наклона), убывающий (отрицательного наклона) или горизонтальный, в зависимости от того, положителен, отрицателен или равен нулю угловой коэффициент этой линейной функции.
Стратегия , удовлетворяющая равенству
(10.1)
где, напомним, - множество всех смешанных (в том числе и чистых) стратегий игрока А, является (по основной теореме 8.1 матричных игр фон Неймана, см. [9])) оптимальной, т.е. абсцисса максимальной (наивысшей) точки нижней огибающей определяет оптимальную стратегию , придерживаясь которой игрок А выбирает свои чистые стратегии случайным образом, причем стратегию - с вероятностью , а стратегию - с вероятностью .
По теореме фон Неймана
, (10.2)
т.е. цена игры V равна ординате максимальной точки нижней огибающей.
Таким образом, мы можем сформулировать алгоритм геометрического (графического) нахождения оптимальных стратегий игрока А и цены игры.
Алгоритм "А "
1. Берем горизонтальный отрезок [0,1].
2. Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый.
3. На левом перпендикуляре, лежащем на вертикальной числовой оси, от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первой строки матрицы А.
4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все элементы второй строки матрицы А.
Замечания к пунктам 1, 3, 4. Масштабы на левом и правом перпендикулярах должны быть одинаковыми, не обязательно совпадающими с масштабом горизонтального отрезка [0,1].
5. Каждую пару точек, изображающих элементы и стоящие в -м столбце матрицы А, соединяем отрезком . Таким образом, будут построены отрезков, представляющих собой графики линейных функций
(10.3)
6. Если все отрезки , - неубывающие (имеют неотрицательный наклон): , то стратегия доминирует стратегию . Если все отрезки , , возрастающие (имеют положительный наклон): , то стратегия строго доминирует стратегию .
7. Если все отрезки , невозрастающие (имеют неположительный наклон): то стратегия доминирует стратегию . Если все отрезки , убывающие (имеют отрицательный наклон): , то стратегия строго доминирует стратегию .
8. Если отрезок лежит не ниже отрезка , ,то стратегия доминирует стратегию . Если отрезок лежит выше отрезка , , то стратегия строго доминирует стратегию .
9. Находим (выделяем) нижнюю огибающую (10.1) семейства отрезков (10.3), которая в общем случае будет представлять собой выпуклую вверх ломаную, а, в частности, может быть и отрезком.
10. На нижней огибающей находим максимальную (наивысшую) точку (или точки).
11. Абсцисса этой точки (удовлетворяющая равенству (10.1)) является вероятностью выбора игроком А чистой стратегии А2 в оптимальной смешанной стратегии
12. Ордината наивысшей точки нижней огибающей является ценой игры V (см. 10.2)).
13. Верхний из двух концов нижней огибающей (лежащих на перпендикулярах) есть нижняя цена игры в чистых стратегиях .
14. Нижний из верхних концов отрезков , , есть верхняя цена игры в чистых стратегиях .
15. Элемент матрицы А, изображающая точка которого является нижней на перпендикуляре, где она лежит, и верхним концом отрезка, на котором она лежит, будет седловой точкой игры.
В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки, является оптимальной.
Рис. 10.1
На рис. 10.1 из отрезков , , указаны три, которые принимают участие в конструировании нижней огибающей, выделенной жирной линией; N - максимальная точка этой огибающей; р° - абсцисса точки N, следовательно - оптимальная смешанная стратегия игрока А: цена игры V равна ординате точки N; нижняя цена игры в чистых стратегиях ; верхняя цена игры в чистых стратегиях ; на рисунке видно, что .
Теорема 16.1. Если через максимальную точку N нижней огибающей отрезков , порождаемых чистыми стратегиями , игрока В, проходят два каких-либо отрезка , , , то абсцисса
точки N
(10.4)
и, следовательно,
, (10.5)
а цепа игры
. (16.7)
Теорема 16.2. Пусть через максимальную точку N нижней огибающей отрезков , порождаемых чистыми стратегиями , игрока В, проходят два каких-либо отрезка , , .
Для того чтобы смешанная стратегия игрока В, где
,
,
была оптимальной, необходимо и достаточно, чтобы отрезки и имели разные наклоны.