Решение игр с помощью линейного программирования. Оптимальные стратегии игроков. Графическое решение

Задача: Матричная игра задана следующей платежной матрицей :

Найти решение матричной игры, а именно:  - найти верхнюю цену игры;  - нижнюю цену игры;  - чистую цену игры;  - указать оптимальные стратегии игроков;  - привести графическое решение (геометрическую интерпретацию), при необходимости.

Шаг:1

Определим нижнюю цену игры - α

Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой"). Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец ( Выделен желтым цветом см. Табл.1). Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.

Таблица 1

В нашем случае нижняя цена игры равна: α = -7, и для того чтобы гарантировать себе выигрыш не хуже чем -7 мы должны придерживаться стратегии A₁ Шаг:2

Определим верхнюю цену игры - β

Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию. Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу ( Выделена желтым цветом см. Табл.2 ). Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.

Таблица 2

В нашем случае верхняя цена игры равна: β = 1, и для того чтобы гарантировать себе проигрыш не хуже чем 1 противник ( игрок "B") должен придерживаться стратегии B₁ Шаг:3 Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β, платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях. Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать

где A₁, A₂ - стратегии игрока "A", а p₁, p₂ - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p₁ + p₂ = 1. Аналогично смешанную стратегию игрока "В" будем обозначать

где B₁, B₂, B₃, B₄, B₅ - стратегии игрока "B", а q₁, q₂, q₃, q₄, q₅ - соответственно вероятности, с которыми эти стратегии применяются, причем q₁ + q₂ + q₃ + q₄ + q₅ = 1. Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S_A^* и S_B^* соответственно. Пара оптимальных стратегий образует решение игры. В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями. Шаг:4 Из теории игр известно, что если игрок "А" в своей оптимальной смешанной стратегии использует не более чем N активных стратегий, то и оптимальная стратегия игрока "B" состоит не более чем из N активных стратегий. А в нашем случае у "А" активных стратегий две и поэтому оптимальная стратегия игрока "В" представляет собой случайную смесь двух из 5-х стратегий B₁, B₂, B₃, B₄, B₅. Но каких именно? Ответить на этот вопрос нам поможет геометрическая