Математическая энциклопедия

ИГРА С ИЕРАРХИЧЕСКОЙ СТРУКТУРОЙ

- модель конфликтной ситуации при фиксированной последовательности ходов и обмена информацией участников. Основным объектом исследования в теории И. с и. с. является задача об отыскании наибольшего гарантированного результата и оптимальной стратегии выделенного игрока. Пусть игроки 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. Как видно из определения, оптимальная стратегия состоит из нескольких ветвей, последняя играет роль стратегии наказания. ЕслиL22(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определяется из условия максимизации функции от одной переменной.

Более общий вариант неполной информированности игрока I об интересах игрока II состоит в следующем: игроку I известна функцияf2(x1, x2, а),.и известно, что при нек-ром (неизвестном) значении a=a0истинная функция f2(x1, x2)=f2(x1, х2,a0). При такой информированности решение игры Г2для конечных множеств Асводится к максимизации функции нескольких переменных; при бесконечных множествах Азадача еще более сложна. Наличие неопределенных факторов в постановке игры Г1не приводит к принципиальному усложнению задачи, поскольку этот случай сводится к игре без неопределенностей. Для игры Г2при неопределенности рассмотрен ряд задач, когда понятие стратегии игроков расширено за счет предложения игрока I игроку II сообщить свой критерий эффективности, т. е. нек-рое так чтобы окончательный выборх1мог быть сделан по получении информации ох2и критерия эффективности игрока II. Если в этом случае игрок II осторожен, т. е. придерживается принципа наибольшего гарантированного результата, а игрок I сообщает ему параметризованную стратегию то можно показать, что наибольший гарантированный результат игрока I равен где G2a- наибольший гарантированный результат игрока I в игре Г2при данном Аналогичный результат без предположения об осторожности игрока II имеет место, когда игроку I известно параметрич. семейство множествХ2(a),одно из к-рых совпадает с истинным.

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

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

Формулировки рассматриваемых игр естественно переносятся на случай многих лиц, взаимодействия к-рых в смысле приоритета действий и передачи информации имеют иерархическую структуру. При анализе этих игр необходимо оговаривать также правила взаимодействий игроков одного уровня. Так, при рассмотрении игры трех лиц, где функции выигрышей игроков имеют вид

х1ОХ1, х2ОХ2, х3ОХ3,для отыскания наибольшего гарантированного результата выделенного игрока I, обладающего приоритетом в действиях, необходимо конкретизировать его информацию о поведении игроков II и III. Если игроки II и III образуют известную игроку I жесткую коалицию, т. е. формулируют коалиционный критерий и сообща определяют свои выборы, то для игрока I данный случай эквивалентен рассмотренным ранее играм двух лиц. Обозримые результаты получаются также в случае, когда игроки II и III либо находятся в известной игроку I коалиции, либо действуют индивидуально, если таким образом могут получить результат больший, чем дает коалиция; при этом каждый из игроков II и III не имеет самостоятельной информации о ходе другого и порядок их ходов задается игроком I. Подробно проанализированы игры, имеющие "веерную" структуру: выделенный игрок (управляющий центр) П0и пигроков на следующем уровне иерархии (производители продукции) стремятся к увеличению функций выигрыша f0(x0, х)иfi(xi0;хi),i=l, ...,п,соответственно, гдех0= {хi0, ..., хn0)- выбор П0,х- {х1, ..., хn}- совокупный выбор игроков на нижнем уровне иерархии, причем они действуют независимо, и каждый игрок номера iраспоряжается выборомхiОХi.Все множества полагаются компактными, а функции непрерывными. Игрок П0рассчитывает на информацию (и будет ее иметь) о выборах и сообщает каждому игроку i соответствующую стратегию функцию определенную наXiсо значениями изХi0.Для И. с и. с. плиц получены выражения наибольшего гарантированного результата выделенного игрока при различных расширениях его класса стратегий за счет передачи игрокам нижнего уровня информации о действиях партнеров, а также введения элементов блефа. Как и в играх двух лиц, возможность побочного платежа со стороны выделенного игрока значительно упрощает отыскание его гарантированного результата.

При помощи И. с и. с. получают естественную интерпретацию различные механизмы централизованного управления активными экономич. подсистемами. Игра Г1описывает процесс централизованного управления при помощи цен; игра Г2моделирует политику штрафов и поощрений при стимулировании производства; игрой Г3моделируется процесс распределения ресурсов как функций от производственных способов использования данных ресурсов.

Лит.:[1] Гермейер Ю. Б., Игры с непротивоположными интересами, М., 1972.

И. А. Вателъ, Ф. II. Ерешко.