Теория игр

Вариант 5.

Задание 2.

Дана матрица игры [pic 1].

1. Проверить наличие седловой точки;
2. Упростить матрицу игры с помощью геометрических построений;
3. Найти решение игры.

Решение:

1) Проверим наличие седловой точки, определив и сравнив верхнюю и нижнюю цены игры.

Нижняя цена игры определяется по формуле:

[pic 2]

Находим минимумы в каждой строке:

[pic 3], [pic 4]

Получаем нижнюю цену игры: [pic 5].

Аналогично находим верхнюю цены игры по формуле:

[pic 6]

Находим максимумы в каждой строке:

[pic 7], [pic 8], [pic 9], [pic 10].

Получаем верхнюю цену игры: [pic 11].

Так как [pic 12], седловая точка отсутствует, цена игры v находится в интервале [3; 4].

2) Упростим матрицу игры с помощью геометрических построений.

Смешанная стратегия первого игрока представляет собой совокупность двух чисел p1 и p2, в сумме дающих единицу. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

[pic 13]

Рис. 1. График зависимости выигрыша первого игрока от смешанной стратегии

Далее находим нижнюю границу множества прямых (выделена жирным на рис. 1). Точка отрезка, при которой нижняя граница достигает максимума (точка M), соответствует искомой смешанной стратегии p, высота максимума дает при этом значение верхней цены игры α.

По графику видно, что минимум достигается при пересечении стратегий B1 и B2, поэтому исключаем из матрицы третий и четвертый столбцы, при этом q3 = 0 и q4 = 0. Получаем сокращенную матрицу:

[pic 14]

3) Запишем систему уравнений для первого игрока, обозначим цену игры через v:

[pic 15]

Решая систему, получаем [pic 16], [pic 17], [pic 18].

Составляем систему уравнений для второго игрока, учитывая, что цена игры равна [pic 19]:

[pic 20]

Решая систему, получаем [pic 21] и [pic 22].

Таким образом, оптимальными смешанными стратегиями являются [pic 23] и [pic 24], при этом цена игры будет равна [pic 25].

Задание 3.

Дана матрица игры [pic 26].

1. Проверить наличие седловой точки;
2. Найти решение игры методом Лагранжа.

Решение:

1) Проверим наличие седловой точки, определив и сравнив верхнюю и нижнюю цены игры.

Нижняя цена игры определяется по формуле:

[pic 27]

Находим минимумы в каждой строке:

[pic 28], [pic 29], [pic 30]

Получаем нижнюю цену игры: [pic 31].

Аналогично находим верхнюю цены игры по формуле:

[pic 32]

Находим максимумы в каждой строке:

[pic 33], [pic 34], [pic 35].

Получаем верхнюю цену игры: [pic 36]

Так как [pic 37], седловая точка отсутствует, цена игры v находится в интервале [1; 3].

2) Функция цены игры имеет вид:

[pic 38]

Данную функцию необходимо максимизировать при ограничениях: [pic 39] и [pic 40].

Получаем функцию Лагранжа:

[pic 41]

Находим частные производные:

[pic 42], [pic 43], [pic 44]

[pic 45], [pic 46], [pic 47]

[pic 48], [pic 49]

Приравнивая к нулю, получаем систему:

[pic 50]

Из первого уравнения выразим q1:

[pic 51]

и подставим его во второе и в третье:

[pic 52]

[pic 53]

В полученных уравнения из первого выражаем q2:

[pic 54]

и подставляем по второе:

[pic 55]

Подставляем полученные выражения в последнее уравнение и после упрощения получаем: [pic 56], откуда [pic 57].