" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

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

Значение ИГРА С ИЕРАРХИЧЕСКОЙ СТРУКТУРОЙ в математической энциклопедии:

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

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

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

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

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

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

при этом тогда и только тогда, когда достигается max f₂(x₁(y), у).

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

где

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

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

Развиты методы решения игры Г _1; использующие штрафные функции, необходимые условия оптимальности, приближение исходной игры игрой с однозначными ответами игрока II. Полностью решены частные классы игр: с близкими интересами, биматричные, билинейные и др. Задача отыскания G₁ некорректна относительно изменения функции f₂(x₁, х ₂ )в равномерной метрике и множеств Х ₁, Х ₂ в метрике Хаусдорфа. Предложен общий метод регуляризации решения игры Г ₁; регуляризация задачи по функции выигрыша игрока II осуществляется за счет введения искусственной неточности определения. Отыскание величины G₂ сводится к решению ряда задач математического программирования.

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

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

гарантирует игроку I при достаточно малых е получение тaх[ К, M]-e. Как видно из определения, оптимальная стратегия состоит из нескольких ветвей, последняя играет роль стратегии наказания. Если L₂<f₂(x₁, x₂ )и у функции f₂(x₁, х ₂ )нет локальных максимумов со значением L₂ на Х ₁ Х ₂, то и оптимальная стратегия имеет простой вид:

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

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

и игрок I выбирает стратегии х ₁( х ₂), z(x₂), отыскание G₂ сводится к решению задачи математич. программирования

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

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

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

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

Более общий вариант неполной информированности игрока I об интересах игрока II состоит в следующем: игроку I известна функция f₂(x₁, x₂, а),. и известно, что при нек-ром (неизвестном) значении a=a₀ истинная функция f₂(x₁, x₂)=f₂(x₁, х ₂,a₀). При такой информированности решение игры Г ₂ для конечных множеств Асводится к максимизации функции нескольких переменных; при бесконечных множествах Азадача еще более сложна. Наличие неопределенных факторов в постановке игры Г ₁ не приводит к принципиальному усложнению задачи, поскольку этот случай сводится к игре без неопределенностей. Для игры Г ₂ при неопределенности рассмотрен ряд задач, когда понятие стратегии игроков расширено за счет предложения игрока I игроку II сообщить свой критерий эффективности, т. е. нек-рое так чтобы окончательный выбор х ₁ мог быть сделан по получении информации о х ₂ и критерия эффективности игрока II. Если в этом случае игрок II осторожен, т. е. придерживается принципа наибольшего гарантированного результата, а игрок I сообщает ему параметризованную стратегию то можно показать, что наибольший гарантированный результат игрока I равен где G_2a - наибольший гарантированный результат игрока I в игре Г ₂ при данном Аналогичный результат без предположения об осторожности игрока II имеет место, когда игроку I известно параметрич. семейство множеств Х ₂(a), одно из к-рых совпадает с истинным.

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

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

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

х ₁ О Х ₁, х ₂ О Х ₂, х ₃ О Х ₃, для отыскания наибольшего гарантированного результата выделенного игрока I, обладающего приоритетом в действиях, необходимо конкретизировать его информацию о поведении игроков II и III. Если игроки II и III образуют известную игроку I жесткую коалицию, т. е. формулируют коалиционный критерий и сообща определяют свои выборы, то для игрока I данный случай эквивалентен рассмотренным ранее играм двух лиц. Обозримые результаты получаются также в случае, когда игроки II и III либо находятся в известной игроку I коалиции, либо действуют индивидуально, если таким образом могут получить результат больший, чем дает коалиция; при этом каждый из игроков II и III не имеет самостоятельной информации о ходе другого и порядок их ходов задается игроком I. Подробно проанализированы игры, имеющие "веерную" структуру: выделенный игрок (управляющий центр) П ₀ и пигроков на следующем уровне иерархии (производители продукции) стремятся к увеличению функций выигрыша f₀(x₀, х)и f_i(xⁱ₀; х _i),i=l, ..., п, соответственно, где х ₀= {х ⁱ₀, ..., х ⁿ₀)- выбор П ₀, х- {х ₁, ..., х _n}- совокупный выбор игроков на нижнем уровне иерархии, причем они действуют независимо, и каждый игрок номера iраспоряжается выбором х _i О Х _i. Все множества полагаются компактными, а функции непрерывными. Игрок П ₀ рассчитывает на информацию (и будет ее иметь) о выборах и сообщает каждому игроку i соответствующую стратегию функцию определенную на X_i со значениями из Х ⁱ₀. Для И. с и. с. плиц получены выражения наибольшего гарантированного результата выделенного игрока при различных расширениях его класса стратегий за счет передачи игрокам нижнего уровня информации о действиях партнеров, а также введения элементов блефа. Как и в играх двух лиц, возможность побочного платежа со стороны выделенного игрока значительно упрощает отыскание его гарантированного результата.

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

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

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