 |
Решение игр графическим методом
|
|
|
|
Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.
Первый случай. Рассмотрим игру (2 ´ 2) с матрицей
без седловой точки. Решением игры являются смешанные стратегии игроков 
(x 1, x 2) и 
(y 1, y 2), где x 1 - вероятность применения первым игроком первой стратегии, x 2 - вероятность применения первым игроком второй стратегии, y 1 - вероятность применения вторым игроком первой стратегии, y 2 - вероятность применения вторым игроком второй стратегии. Очевидно, что
x 1 + x 2 = 1, y 1 + y 2 = 1.
Найдем решение игры графическим методом. На оси О X отложим отрезок, длина которого равна единице. Левый конец (x = 0) соответствует стратегии первого игрока А 1, правый (x = 1) - стратегии А 2. Внутренние точки отрезка будут соответствовать смешанным стратегиям 
(x 1, x 2) первого игрока, где x 1 =1 - x 2. Через концы отрезка проведем прямые, перпендикулярные оси О X, на которых будем откладывать выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В 1, то выигрыш при использовании первым игроком стратегий А 1 и А 2 составит соответственно а 11 и а 21. Отложим эти точки на прямых и соединим их отрезком В 1 В 1. Если игрок А применяет смешанную стратегию, то выигрышу соответствует некоторая точка М, лежащая на этом отрезке. (см. рис.1)
 |
В1 а21
М
В1
а11
х2 х11 Х
Рис.1. Подписать рисунок
Аналогично строится отрезок В 2 В 2, соответствующий стратегии В 2 игрока В.
Определение 1. Ломаная линия, составленная из частей отрезков, интерпретирующих стратегии игрока В, расположенная ниже всех отрезков, называется нижней границей выигрыша, получаемого игроком А.
|
|
|
Определение 2. Стратегии, части которых образуют нижнюю границу выигрыша, называются активными стратегиями.
В игре (2 ´ 2) обе стратегии являются активными.
В1 а21
В2
а12 К
В2 а22
В1
а11 v
О х2 N х1 1 Х
Рис.2.
Ломаная В 1 КВ 2 является нижней границей выигрыша, получаемого игроком А. (см. рис.2) Точка К, в которой он максимален, определяет цену игры и ее решение. Найдем оптимальную стратегию первого игрока. Запишем систему уравнений
Приравнивая выражения для v из уравнений системы и учитывая, что
x 1 + x 2 = 1, получим 
, 
, (1)
. (2)
Составляя аналогичную систему
и учитывая условие
y 1 + y 2 = 1,
можно найти оптимальную стратегию игрока В:
. (3)
Пример 1. Найти решение игры, заданной матрицей
.
 |
a = max ( 1,1) = 1, b = min ( 3,2) = 2, a ¹ b,
. Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям второго игрока. (см. рис.3)
Рис.3.
По формулам (1) - (3) находим оптимальные стратегии и цену игры:
x 1 = 1/3, x 2 = 2/3; y 1 = 2/3, y 2 = 1/3; v =5/3.
Ответ. Оптимальные смешанные стратегии игроков 
(1/3, 2/3) и 
(2/3, 1/3), цена игры составляет v =5/3.
Данный ответ означает следующее:
если первый игрок с вероятностью 1/3 будет применять первую стратегию и с вероятностью 2/3 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 5/3;
|
|
|
если второй игрок с вероятностью 2/3 будет применять первую стратегию и с вероятностью 1/3 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 5/3.
Второй случай. Рассмотрим игру (2 ´ n) с матрицей
.
Для каждой из n стратегий игрока В строится соответствующий ей отрезок на плоскости. Находится нижняя граница выигрыша, получаемого игроком А, и определяется точка на нижней границе, соответствующая наибольшему выигрышу. Выделяются две активные стратегии игрока В, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока В. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).
Пример 2. Найти решение игры, заданной матрицей
.
a = max ( 1,1) = 1, b = min ( 4, 3, 3,4) = 3, a ¹ b, 
.
Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям второго игрока. (см. рис.4)
 |
Рис.4.
Нижней границей выигрыша для игрока А является ломаная В 3 КВ 4. Стратегии В 3 и В 4 являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В 1 и В 2, поэтому вероятность их применения равна нулю, т.е. у 1 = у 2= 0. Решение игры сводится к решению игры с матрицей (2 ´ 2)
.
a = max ( 1,1) = 1, b = min ( 3,4) = 3, a ¹ b, 
.
По формулам (1) - (3) находим оптимальные стратегии и цену игры:
x 1 = 2/5, x 2 = 3/5; y 3 = 3/5, y 2 = 2/5; v =11/5.
Ответ. Оптимальные смешанные стратегии игроков 
(2/5, 3/5) и 
(0, 0, 3/5, 2/5), цена игры составляет v =11/5.
Данный ответ означает следующее:
если первый игрок с вероятностью 2/5 будет применять первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;
если второй игрок с вероятностью 3/5 будет применять третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 11/5.
Третий случай. Рассмотрим игру (m ´ 2) с матрицей
|
|
|
.
Решение игры может быть получено аналогично случаю два. Для каждой из m стратегий игрока А строится соответствующий ей отрезок на плоскости.
Находится верхняя граница проигрыша, получаемого игроком В, и определяется точка на нижней границе, соответствующая наименьшему проигрышу. Выделяются две активные стратегии игрока А, отрезки которых проходят через данную точку.
Далее рассматриваются только эти две стратегии игрока А. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).
Пример 3. Найти решение игры, заданной матрицей
.
a = max ( 3, 2, 0, - 1) = 3, b = min ( 4,6) = 4, a ¹ b, 
. Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям первого игрока. (см. рис.5).
 |
Рис.5.
Верхней границей проигрыша для игрока В является ломаная А 1 КА 4. Стратегии А 1 и А 4 являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А 2 и А 3, поэтому вероятность их применения равна нулю, т.е. x 2 = x 3= 0. Решение игры сводится к решению игры с матрицей (2 ´ 2)
.
a = max ( 3, - 1) = 3, b = min ( 4,6) = 4, a ¹ b, 
.
По формулам (1) - (3) находим оптимальные стратегии и цену игры:
x 1 = 7/8, x 4 = 1/8; y 1 = 3/8, y 2 = 5/8; v =27/8.
Ответ. Оптимальные смешанные стратегии игроков 
(7/8, 0, 0, 1/8) и 
(3/8, 5/8), цена игры составляет v =27/8.
Данный ответ означает следующее:
если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;
если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.
|
|
|
