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

Возможны ситуации, когда приемы упрощения платежной матрицы (они описаны в пп. 3 и 4) исчерпывают свой потенциал, оставляя более чем две возможные стратегии для каждого игрока. В таких случаях есть возможность применения математического аппарата теории «линейного программирования» (ЛП) при постановке задачи линейного программирования с условиями, опирающимися на решаемую «игровую» задачу. Затем решение сформулированной ЛП-задачи осуществляется с помощью арсенала имеющихся для этого средств, в том числе, при необходимости симплекс-метода и теорем двойственности или программных продуктов. Использование связей между искомыми «игровой» задачи и ЛП-задачи позволяет восстановить соответствующие значения и интерпретировать полученный результат как вероятности применения игроками их чистых стратегий в рамках смешанных стратегий, определить цену игры.

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

1. Первый игрок, Получатель, имеет несколько стратегий, обозначенных A 1, A 2, … Am, т. е. стратегии Ai, где i= 1... m, а второй игрок, Плательщик, – несколько стратегий В 1, В 2, … Bn, т. е. стратегии Bj, где j =1... n. Заранее неизвестно, какие из стратегий являются активными.

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

3. Значение n не меньше, чем нижняя цена игры a[6], но не больше, чем верхняя цена игры b.

4. Вероятности всех стратегий Получателя обозначаются x ₁, x ₂, …, x_m – это неотрицательные значения, связанные между собой соотношением

x ₁ + x ₂ + …+ x_m = 1

и требованиями достижения средней величины платежа не меньше, чем цена игры n.

5. Вероятности всех стратегий Плательщика обозначаются y ₁, y ₂, …, y_n – это неотрицательные значения, связанные между собой соотношением

y ₁ + y ₂ + …+ y_n = 1

и требованиями достижения средней величины платежа не больше, чем цена игры n.

6. Искомыми являются вероятности x ₁, x ₂, …, x_m, y ₁, y ₂, …, y_n и цена игры n.

Замечания

Переход к ЛП-задаче может применяться как альтернатива изложенным выше (пп. 1–5) методам, однако какого-либо выигрыша по сравнению с ними обычно не возникает.

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

Для решения громоздких ЛП-задач бывает полезно сформулировать «игровую» задачу, чтобы воспользоваться потенциалом приемов упрощения платежной матрицы (пп. 3 и 4) и интерпретировать результаты в терминах линейного программирования.

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