Математическая энциклопедия - игра с иерархической структурой

модель конфликтной ситуации при фиксированной последовательности ходов и обмена информацией участников. Основным объектом исследования в теории И. с и. с. является задача об отыскании наибольшего гарантированного результата и оптимальной стратегии выделенного игрока. Пусть игроки I, II стремятся к увеличению, соответственно, функций выигрыша f1(x1 , х 2 )и f2(x1, х 2), непрерывных на произведении компактов Х 1, Х 2;. В зависимости от характера информации и порядка ходов могут быть сформулированы следующие различные игры.

Игра Г 1. Игрок I выбирает и сообщает свой выбор игроку II. Пусть

множество оптимальных выборов игрока II. Тогда наибольший гарантированный результат игрока I равен

Игра Г 2. Игрок I рассчитывает иметь и действительно будет иметь информацию о выборах игрока II; сообщает свою стратегию функцию где

множество всех отображений из Х 2 в X1 игроку II. Наибольший гарантированный результат игрока I равен

где множество оптимальных выборов игрока II есть

при этом тогда и только тогда, когда достигается max f2(x1(y), у).

Игра Г 3. Игрок I рассчитывает иметь и действительно будет иметь информацию о выборах игрока II вида где множество всех отображений из X1 в Х 2;сообщает игроку II свою стратегию где множество всех отображений из в Х 1. Наибольший гарантированный результат игрока I равен

где

при этом тогда и только тогда, когда достигается

Соотношение между результатами в этих играх определяет для игрока I значимость информации о действиях игрока II: Пользуясь указанной схемой в построении стратегий игроков, можно формулировать игры с произвольной глубиной рекурсии. Имеет место утверждение: в играх Г 2m, m>1, наибольший гарантированный результат игрока I равен G2; в играх Г 2m+1, m>1, наибольший гарантированный результат равен G3. Задача отыскания G1 относится к классу задач на максимин со связанными ограничениями.

Развиты методы решения игры Г 1; использующие штрафные функции, необходимые условия оптимальности, приближение исходной игры игрой с однозначными ответами игрока II. Полностью решены частные классы игр: с близкими интересами, биматричные, билинейные и др. Задача отыскания G1 некорректна относительно изменения функции f2(x1, х 2 )в равномерной метрике и множеств Х 1, Х 2 в метрике Хаусдорфа. Предложен общий метод регуляризации решения игры Г 1; регуляризация задачи по функции выигрыша игрока II осуществляется за счет введения искусственной неточности определения. Отыскание величины G2 сводится к решению ряда задач математического программирования.

Пусть для любого е>0 определены функции, множества и величины:

В указанных условиях G2=max[K, M]и стратегия

гарантирует игроку I при достаточно малых е получение тaх[ К, M]-e. Как видно из определения, оптимальная стратегия состоит из нескольких ветвей, последняя играет роль стратегии наказания. Если L2<f2(x1, x2 )и у функции f2(x1, х 2 )нет локальных максимумов со значением L2 на Х 1 Х 2, то и оптимальная стратегия имеет простой вид:

Аналогичным образом может быть найдено решение игры Г 3, оно также сводится к решению ряда задач математич. программирования.

При введении в И. с и. с. побочных платежей со стороны игрока I, как функций от выборов игрока II, выражение для наибольшего гарантированного результата игрока I значительно упрощается. В игре Г 2, где

и игрок I выбирает стратегии х 1( х 2), z(x2), отыскание G2 сводится к решению задачи математич. программирования

Вообще применение сколь угодно малых побочных платежей z(x2 )в И. с и. с. позволяет игроку I реализовать наибольший гарантированный результат, рассчитанный на благожелательность партнера.

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

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

при известных непрерывных функциях f^-2( х 1, х 2), f⁺2(x1, х 2), то его наибольший гарантированный результат в игре Г 2 определяется из условия максимизации функции от одной переменной.