Решение матричных игр 2х2 в смешанных стратегиях

Игра 2х2 – наиболее простой случай конечных игр. Рассмотрим игру, не имеющую седловой точки,  с платежной матрицей

Пусть и –смешанные стратегии игроков. Найдем оптимальные смешанные стратегии игроков. Если игрок В придерживается стратегии В₁, то средний выигрыш А составит . Если игрок В придерживается стратегии В₂, то средний выигрыш А составит . По свойству оптимальных смешанных стратегий эти средние выигрыши должны совпадать и быть равными цене игры. Получаем систему:

Решаем систему

Аналогично, составляем систему для игрока В:

Решая систему, находим:

Цена игры 

Решение игры 2х2 можно найти так же геометрически. Для этого на оси абсцисс отложим отрезок А₁А₂ длиной 1. Левый конец отрезка (p=0) соответствует стратегии А₁, правый – стратегии А₂. Промежуточные точки отрезка соответствуют смешанным стратегиям  первого игрока. Причем расстояние от промежуточной точки отрезка до правого края – это вероятность p₂ стратегии А₂, а расстояние до левого края – вероятность p₁ стратегии А₁. Через концы отрезка А₁А₂ проведем прямые, перпендикулярные оси абсцисс, на них будем откладывать выигрыши при стратегиях А₁ и А₂ соответственно. Если игрок В применяет стратегию В₁, то выигрыши первого игрока при стратегии А₁ составляет a₁₁, а при стратегии А₂ составляет a₂₁. Отложим эти выигрыши на перпендикулярах и соединим полученные точки прямой В₁В₁. Если игрок А применяет смешанную стратегию, то его выигрышу соответствует некоторая точка на отрезке В₁В₁. Аналогично строим отрезок В₂В₂, соответствующий применению вторым игроком стратегии В₂. В соответствии с принципом минимакса ломаная В₁NВ₂ – нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения.

Аналогично можно рассмотреть задачу минимизации верхней границы выигрыша для игрока В.

Используя геометрическую интерпретацию можно найти решение игр, заданных матрицей 2хn. Каждой из nстратегий игрока В будет соответствовать прямая. Точка N, лежащая на нижней границе и дающая наибольшую величину выигрыша, определяет цену игры и ее решение. При этом определяются активные стратегии игрока В (соответствующие им прямые пересекаются в точке N). Для активных стратегий вероятности не равны 0, остальные стратегии игроком В не используются (их вероятности равны 0).

Аналогично можно решить игру с матрицей mxn. В этом случае строят верхнюю границу выигрыша и на ней определяют минимум.

Пример 4

Игра задана платежной матрицей .

1) Решить игру аналитически.

2) Провести моделирование результатов игры с помощью таблицы равномерно распределенных случайных чисел, разыграв 30 партий; определить относительные частоты использования чистых стратегий каждым игроком и средний выигрыш, сравнив результаты с полученными теоретически в п.1.

Решение:

1.Найдем нижнюю и верхнюю цену игры.

a¹b, следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях.

Найдем аналитически оптимальную стратегию игрока А и соответствующую цену игрыn.

Так как – оптимальная, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В:

для стратегии В₁: ;

для стратегии В₂: .

С учетом того, что сумма вероятностей смешанной стратегии равна 1, получаем систему уравнений:

Вычтем из первого уравнения второе:  или .Значит:

Итак: , n = 9.

Аналогично получаем систему для нахождения смешанной стратегии игрока В.

Вычтем из первого уравнения второе: Откуда,  подставим в первое уравнение (Вместо n подставим найденное значение для игрока А
n = 9):

Итак: .

Ответ: , .

2. Проведем моделирование результатов решения с помощью таблицы равномерно распределенных случайных чисел. Для 30 партий хватит 60 чисел, на основе которых будут выбираться стратегии игроками. Используемые случайные числа сгенерированы в MSExcel функцией =СЛЧИС(). В приложении достаточно много чисел, но использовать для моделирования можно любые 60, выбранные произвольно с любого места таблицы. Выберем 60 чисел:

Будем выбирать стратегии игроков, используя геометрическое определение вероятности. Так как все случайные числа из отрезка [0; 1], то чтобы стратегия А₁ появлялась примерно в половине случаев, будем ее выбирать если случайное число меньше 0,5; в остальных случаях выбирается стратегия А₂. Аналогично для игрока В. Стратегию В₁ будем выбирать, если соответствующее случайное число меньше 2/3»0,67, в противном случае выбираем стратегию В₂.

Заполним расчетную таблицу (Средний выигрыш игрока А считаем, как отношение накопленного выигрыша к количеству сыгранных партий):

Таким образом, в результате моделирования в 30 партиях цена игры (средний выигрыш) равен 9,2. Этот результат согласуется с теоретической ценой игры 9.

Из 30 партий игрок А 18 раз применял стратегию А₁, 12 раз – стратегию А₂. Игрок В 21 раз применял стратегию В₁, 9 раз – стратегию В₂.Частоты использования игроками своих чистых стратегий соответственно равны: `p=(18/30;12/30)=(0,6;0,4),`q=(21/30;9/30)=(0,7;0,3). Сравнивая с теоретическими оптимальными стратегиями =(0,5; 0,5) и =(0,67; 0,33) можно сделать вывод, что результаты моделирования достаточно близко соответствуют теоретическим вероятностям даже для небольшого количества партий.

Пример 5

Решить графически игру,  заданную платежной матрицей .

Решение

Матрица игры имеет размер 2х3, поэтому решение игры будем искать для игрока А. Отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока – (p₁, p₂). В частности, точке А₁соответствуетстратегия А₁, точке А₂ – стратегия А₂.

В точках А₁ и А₂ восстановим перпендикуляр и на полученных прямых будем откладывать выигрыши игрока А при соответствующих стратегиях и строить прямые, соответствующие стратегиям игрока В.

В соответствии с принципом минимакса ломаная В₁NMВ₃ – нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения прямых В₂В₂ и В₃В₃.

Уравнение прямой, проходящей через 2 точки (x₁,y₁)  и (x₂,y₂) имеет вид .Прямая В₂В₂ проходит через точки (0,3) и (1,5), следовательно, ее уравнение или -2x+y=3.Прямая В₃В₃ проходит через точки (0,11) и (1,2), следовательно, ее уравнение или 9x+y=11. Для нахождения точки пересечения прямых В₂В₂ и В₃В₃ решим систему:

Вычтем из первого уравнения второе, получаем -11x=-8 Þx=8/11, y=3+2x=49/11. Точка N(8/11,49/11), следовательно, p₂=8/11, p₁=1-8/11=3/11, n=49/11.

Таким образом, , при цене игры .

Из рисунка видно, что стратегия В₁ не входит в оптимальную смешанную стратегию,поэтому q₃=0,и мы можем найти оптимальную смешанную стратегию, удалив из платежной матрицыпервый столбец. Получаем матрицу , при этом столбцы ее соответствуют активным стратегиям В₂, В₃.

Так как – оптимальная, то она должна гарантировать средний выигрыш игроку В, равный цене игры, при любом поведении игрока А:

для стратегии А₁:

для стратегии А₂: .

С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена игры получаем систему уравнений:

Вычтем из первого уравнения второе:

Решая систему, находим

Оптимальная смешанная стратегия для игрока В .

Ответ: ,

Пример 6

Решить графически игру,  заданную платежной матрицей .

Решение

Матрица игры имеет размер 4х2, поэтому решение игры будем искать для игрока В. Аналогично примеру 5отложим отрезок единичной длины В₁В₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию второго игрока – (q₁, q₂). В частности, точке В₁соответствует стратегия В₁, точке В₂ – стратегия В₂.

В точках В₁ и В₂ восстановим перпендикуляр и на полученных прямых будем откладывать выигрыши игрока А при соответствующих стратегиях и строить прямые, соответствующие стратегиям игрока А.

В соответствии с принципом минимакса ломаная А₁NА₄ – верхняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрышминимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока В достаточно составить уравнения прямых и найти точку пересечения прямых А₁А₁ и А₄А₄.

Уравнение прямой, проходящей через 2 точки (x₁,y₁)  и (x₂,y₂) имеет вид .Прямая А₁А₁ проходит через точки (0,6) и (1,5), следовательно, ее уравнение или x+y=6.Прямая А₄А₄ проходит через точки (0,1) и (1,8), следовательно, ее уравнение или -7x+y=1. Для нахождения точки пересечения прямых А₁А₁ и А₄А₄решим систему:

Вычтем из первого уравнения второе, получаем 8x=5Þx=5/8, y=6-x=43/8. Точка N(5/8,43/8), следовательно, q₂=5/8, q₁=1-5/8=3/8, n=43/8.

Таким образом, , при цене игры .

Из рисунка видно, что стратегииА₂ и А₃не входят в оптимальную смешанную стратегию,поэтому p₂=0 и p₃=0, имы можем найти оптимальную смешанную стратегию, удалив из платежной матрицывторую и третью строку. Получаем матрицу , при этом строки ее соответствуют активным стратегиям А₁, А₄.

Так как – оптимальная, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В:

для стратегии В₁:

для стратегии В₂: .

С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена игры получаем систему уравнений:

Вычтем из первого уравнения второе:

Решая систему, находим

Оптимальная смешанная стратегия для игрока А .

Ответ: , ,

Таким образом, имеем следующийалгоритм графического решения простейших матричных игр 2хn ( или mx2):

1. Строимn (m) прямых, соответствующих стратегиям второго (первого) игрока.

2. Строим нижнюю (верхнюю) границу выигрыша.

3. Выбираем на границе выигрыша точку с максимальной (минимальной) ординатой.

4. Определяем по чертежу пару активных стратегий из числа построенных для второго (первого) игрока.

5. Находим координаты точки максимума (минимума) и  решение игры.