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

Пример №1 . Решить игру, заданную платежной матрицей , графоаналитическим способом. Решение. Нижняя цена игры α = 1,5, верхняя цена игры β = 2. Так как α≠β, седловой точки нет. Так как a1 = 1,5, a21 = 2 строим точки B1(0;1,5) и B2(1;2), соединяем их отрезком. Так как a21 = 3, a22 = 1 строим точки B2(0;3) и B2’(1;1), соединяем их отрезком.

Видеоинструкция. Решение онлайн

Пример №2 . Решить матричную игру, в которой один из игроков имеет две чистые стратегии, или игру, которая сводится к таковой после отбрасывания доминируемых строк и столбцов. Для нахождения цены игры и оптимальной стратегии игрока, имеющего две чистые стратегии, применяется графический метод. Для другого игрока оптимальная стратегия ищется исходя из свойств оптимальных стратегий и цены игры. Список рекомендуемых для контрольной работы задач прилагается.

Решение игры 2×2

Пример №3 . Найдем решение матричной игры

V* = -1, V* = 1, V* ≠V* - решения в чистых стратегиях не существует. Припишем строкам платёжной матрицы неизвестные вероятности p1 и p2 (вероятности выбора стратегий A1 и A2) соответственно: . Поскольку p1 + p2 =1 → p2 = 1 - p1. Обозначим p1 = p, тогда p2 =1 - p. В результате получим:

Умножим столбец поэлементно на 1-й столбец и, сложив произведения, получим - математическое ожидание (среднее значение) выигрыша первого игрока A, при условии, что второй игрок B следует первой стратегии. M1(p) = 1∙p + (-1)(1-p) = 2p-1 Умножим столбец поэлементно на 2-й столбец и, сложив произведения, получим линейную зависимость - математическое ожидание (средний выигрыш) игрока A при применении игроком B второй стратегии M2(p) = (-1)∙p + 1(1-p) = -2p+1 Поскольку мы разыскиваем оптимальное решение первого игрока A, которое не должно зависеть от выбора стратегий вторым игроком B, приравняем полученные зависимости средних выигрышей: 2p-1 = -2p+1 Отсюда, p= ½, 1-p = ½, то есть оптимальная смешанная стратегия игрока A - это P = (½, ½ ) (каждую из стратегий надо применять с относительной частотой ½). Подставив p=½ в любую из зависимостей Mi(p), i=1,2 найдем цену игры: V=Mi(½) = 0. Теперь припишем столбцам вероятности q1 и q2 соответственно, а поскольку: q1 + q2 =1 →q2 = 1 - q1. Обозначим q1 = q, тогда q2 =1 - q. В результате получим: . Умножив строку (q, 1-q) на 1-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание: W1(q) = 1· q + (-1) ·(1-q) = 2q - 1 Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 1-й стратегии. Умножив строку (q, 1-q) на 2-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание: W2 = (-1) · q + 1· (1-q) = -2q + 1 Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 2-й стратегии. Приравняем полученные зависимости: 2q -1 = -2q + 1 Отсюда, q = ½, 1 - q = ½, то есть оптимальная смешанная стратегия игрока B - это Q = (½, ½) (каждую из стратегий надо применять с относительной частотой ½). Решение о конкретном выборе одной из своих стратегий каждый из игроков может принимать с помощью подбрасывания монеты или бинарного датчика случайных чисел. Как показывает приведённый пример, оптимальные смешанные стратегии сравнительно легко находятся для игр, имеющих небольшую размерность платёжной матрицы (небольшие m и n), т.е. для игр, в которых каждый из игроков имеет небольшое число стратегий. В то же время для игр, имеющих большую размерность, поиск решения становится достаточно сложным. Поэтому до построения оптимального решения в смешанных стратегиях проводят предварительный анализ платёжной матрицы на предмет её упрощения, исключения из неё дублирующих и доминируемых стратегий, что позволяет существенно упростить поиск решения игровой задачи в смешанных стратегиях.

Решение игр вида 2хn и mх2

У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2 , которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом. Рассмотрим решение матричной игры на примере.

Пример №4 . Решение. αi 1471 6 3 2 2 βj 6 4 7 2 4 α=2, β=4, α≠β, поэтому игра не имеет седловой точки, и решение должно быть в смешанных стратегиях. 1. Строим графическое изображение игры.

Правила решения игры mx2

1. строится графическое изображение игры;
2. выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры γ;
3. определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них;
4. решается полученная игра 2x2.

Примечание: Игроку А не выгодно отклоняться от спектра своих активных стратегий.