Переход к задаче линейного программирования для поиска смешанной стратегии первого игрока и цены игры, выявления активных стратегий второго игрока

Шаг № 1. Для каждой стратегии Плательщика Bj (в платежной матрице ей соответствует столбец с номером j) запишем требование: при применении смешанной стратегии Получателя средняя величина платежа должна оказаться не меньше, чем цена игры n (количество таких неравенств совпадает с количеством столбцов в платежной матрице)

a _{1 j}x ₁ + a _{2 j}x ₂ +... + a_mjx_m ³ n.

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

Шаг № 2. Разделим все полученные неравенства на цену игры n, вводя новые искомые величины через соотношение X_i = x_i /n

a _{1 j} X ₁ + a _{2 j} X ₂ +... + a_mjX_m ³ 1, где j=1...n.

Эти неравенства образуют систему ограничений в ЛП-задаче.

Замечание: матрица ЛП-задачи является транспонированной по отношению к исходной платежной матрице, все свободные члены равны единице, знак неравенств ограничивает искомые величины «снизу».

Шаг № 3. Используем соотношение x ₁ + x ₂ + …+ x_m = 1, деля его на цену игры n и вводя новые искомые

X ₁ + X ₂ +...+ X_m = 1/n.

Так как цена игры n соответствует максимальному гарантированному среднему платежу, то обратная ей величина 1/n, может быть получена в результате минимизации соответствующего функционального выражения. Отсюда получаем целевую функцию ЛП-задачи

G = X ₁ + X ₂ +...+ X_m → min.

Замечание: все коэффициенты целевой функции равны единице. Для Получателя ЛП-задача требует минимизации значения целевой функции при ограничениях «снизу» на значения искомых величин X_i.

Шаг № 4. Решение ЛП-задачи. В результате решения становятся известными величины X ₁, X ₂,..., X_m, G _min.

Шаг № 5. Возврат к «игровой» задаче осуществляется с помощью соотношений

n = 1/ G _min (цена игры);

x_i = X_i ×n (все вероятности, с которыми Плательщик применяет свои чистые стратегии).

Шаг № 6. Проверка результата.

Значения вероятностей – неотрицательные, их сумма x ₁ + x ₂ + …+ x_m = 1.

При рассмотрении каждой отдельно взятой стратегии Плательщика Bj должны выполняться неравенства, сформулированные при выполнении шага № 1, причем строгие неравенства указывают на невыгодные для Плательщика стратегии (неактивные), равенства – на активные стратегии, составляющие его смешанную стратегию

a _{1 j}x ₁ + a _{2 j}x ₂ +...+ a_mjx_m ³ n.

Значения цены игры n, полученные для Получателя и Плательщика, должны совпадать.

Пример 6а. Требуется найти смешанную стратегию Получателя, цену игры n, определить состав смешанной стратегии Плательщика и упростить данную платежную матрицу (она взята из примера 4а).

	В 1	В 2	В 3
А 1
А 2

Решение

1. Для каждой стратегии Плательщика запишем требование: средняя величина платежа должна оказаться не меньше, чем цена игры n.

2. Разделим все полученные неравенства на цену игры n, вводя новые искомые величины через соотношение X_i = x_i /n.

Эти неравенства образуют систему ограничений в ЛП-задаче.

3. Запишем целевую функцию ЛП-задачи

G = X ₁ + X ₂ → min.

4. Пользуясь малым количеством искомых величин, решение ЛП-задачи проводим графическим методом. Граничным линиям соответствуют строгие равенства (линейные зависимости), по которым найдем точки пересечения с координатными осями графика

Выполним построение отрезков

По результатам построения делаем вывод: наименьшее значение целевая функция принимает в точке М, которая является точкой пересечения отрезков, соответствующих стратегиям В 2 и В 3.

Проведем аналитический расчет координат точки М и значения целевой функции

5. Возврат к «игровой» задаче осуществляется с помощью соотношений

n = 1/ G _min=16/3» 5,33 (цена игры);

x ₁= X ₁×n = 1/3» 0,33 (вероятность применения Получателем стратегии А 1);

x ₂ = X ₂×n = 2/3» 0,67 (вероятность применения Получателем стратегии А 2).

6. Проверка результата.

Значения вероятностей – неотрицательные, их сумма x ₁ + x ₂ =1/3 + 2/3=1.

При использовании Плательщиком его чистых стратегий получаем среднюю величину платежа

Неравенство, полученное для стратегии В 1, указывает на выгодную для Получателя, но невыгодную для Плательщика стратегию. Эту стратегию можно исключить из платежной матрицы как неактивную.

Ответ (совпадает с ответом в примере 4а):

– вероятности применения стратегий Получателя x ₁» 0,33 и x ₂» 0,67;

– цена игры n» 5,33;

– смешанная стратегия Плательщика состоит в применении его чистых стратегий В 2 и В 3,

– столбец, соответствующий стратегии Плательщика В 1, можно исключить из платежной матрицы (он выделен в таблице).

	В 1	В 2	В 3			В 2	В 3
А 1				~	А 1
А 2					А 2

Дата добавления: 2014-12-27