Игра с иерархической структурой

- модель конфликтной ситуации при фиксированной последовательности ходов и обмена информацией участников. Основным объектом исследования в теории И. с и. с. является задача об отыскании наибольшего гарантированного результата и оптимальной стратегии выделенного игрока. Пусть игроки I, II стремятся к увеличению, соответственно, функций выигрыша f1(x1, х 2)и f2(x1, х 2), непрерывных на произведении компактов Х 1, Х 2; [img: http://localhost:8080/file/021002-1.jpg]. В зависимости от характера информации и порядка ходов могут быть сформулированы следующие различные игры. Игра Г 1. Игрок I выбирает [img: http://localhost:8080/file/021002-2.jpg] и сообщает свой выбор игроку II. Пусть [img: http://localhost:8080/file/021002-3.jpg] - множество оптимальных выборов игрока II. Тогда наибольший гарантированный результат игрока I равен [img: http://localhost:8080/file/021002-4.jpg] Игра Г 2. Игрок I рассчитывает иметь и действительно будет иметь информацию о выборах игрока II; сообщает свою стратегию - функцию [img: http://localhost:8080/file/021002-5.jpg] где [img: http://localhost:8080/file/021002-6.jpg] - множество всех отображений из Х 2 в X1 игроку II. Наибольший гарантированный результат игрока I равен [img: http://localhost:8080/file/021002-7.jpg] где множество оптимальных выборов игрока II есть [img: http://localhost:8080/file/021002-8.jpg] [img: http://localhost:8080/file/021002-9.jpg] при этом [img: http://localhost:8080/file/021002-10.jpg] тогда и только тогда, когда достигается max f2(x1(y), у). Игра Г 3. Игрок I рассчитывает иметь и действительно будет иметь информацию о выборах игрока II вида [img: http://localhost:8080/file/021002-11.jpg] где [img: http://localhost:8080/file/021002-12.jpg] - множество всех отображений из X1 в Х 2;сообщает игроку II свою стратегию [img: http://localhost:8080/file/021002-13.jpg] где [img: http://localhost:8080/file/021002-14.jpg] - множество всех отображений из [img: http://localhost:8080/file/021002-15.jpg] в Х 1. Наибольший гарантированный результат игрока I равен [img: http://localhost:8080/file/021002-16.jpg] где [img: http://localhost:8080/file/021002-17.jpg] [img: http://localhost:8080/file/021002-18.jpg] при этом [img: http://localhost:8080/file/021002-19.jpg] тогда и только тогда, когда достигается [img: http://localhost:8080/file/021002-20.jpg] Соотношение между результатами в этих играх определяет для игрока I значимость информации о действиях игрока II: [img: http://localhost:8080/file/021002-21.jpg] Пользуясь указанной схемой в построении стратегий игроков, можно формулировать игры с произвольной глубиной рекурсии. Имеет место утверждение: в играх Г 2m, m>1, наибольший гарантированный результат игрока I равен G2; в играх Г 2m+1, m>1, наибольший гарантированный результат равен G3. Задача отыскания G1 относится к классу задач на максимин со связанными ограничениями. Развиты методы решения игры Г 1; использующие штрафные функции, необходимые условия оптимальности, приближение исходной игры игрой с однозначными ответами игрока II. Полностью решены частные классы игр: с близкими интересами, биматричные, билинейные и др. Задача отыскания G1 некорректна относительно изменения функции f2(x1, х 2)в равномерной метрике и множеств Х 1, Х 2 в метрике Хаусдорфа. Предложен общий метод регуляризации решения игры Г 1; регуляризация задачи по функции выигрыша игрока II осуществляется за счет введения искусственной неточности определения. Отыскание величины G2 сводится к решению [img: http://localhost:8080/file/021002-22.jpg] ряда задач математического программирования. Пусть для любого е>0 определены функции, множества и величины: [img: http://localhost:8080/file/021002-23.jpg] В указанных условиях G2=max[K, M]и стратегия [img: http://localhost:8080/file/021002-24.jpg] гарантирует игроку I при достаточно малых е получение тaх[ К, M]-e. Как видно из определения, оптимальная стратегия состоит из нескольких ветвей, последняя играет роль стратегии наказания. Если L2<f2(x1, x2)и у функции f2(x1, х 2)нет локальных максимумов со значением L2 на Х 1 [img: http://localhost:8080/file/021002-25.jpg] Х 2, то [img: http://localhost:8080/file/021002-26.jpg] и оптимальная стратегия имеет простой вид: [img: http://localhost:8080/file/021002-27.jpg] Аналогичным образом может быть найдено решение игры Г 3, оно также сводится к решению ряда задач математич. программирования. При введении в И. с и. с. побочных платежей со стороны игрока I, как функций от выборов игрока II, выражение для наибольшего гарантированного результата игрока I значительно упрощается. В игре Г 2, где [img: http://localhost:8080/file/021002-28.jpg] [img: http://localhost:8080/file/021002-29.jpg] и игрок I выбирает стратегии х 1(х 2), z(x2), отыскание G2 сводится к решению задачи математич. программирования [img: http://localhost:8080/file/021002-30.jpg] Вообще применение сколь угодно малых побочных платежей z(x2)в И. с и. с. позволяет игроку I реализовать наибольший гарантированный результат, рассчитанный на благожелательность партнера. Сформулированные игры допускают обобщение на случай постепенного получения и использования информации в динамике. В случае, когда состояние игроков описывается дифференциальными или разностными уравнениями, возникает обширный класс задач, связанный с разнообразием форм информированности игроков о состоянии и течении как физич. процесса, так и процесса принятия решения. Рассмотрены обобщения игр Т 1 и Г 2 на случай запрещенных ситуаций, т. е. при наличии совместных ограничений на выборы игроков. Приведенные формулировки относятся к случаю полной информированности игрока I о функции выигрыша и множестве его выборов. Если игроку I известно, что непрерывная функция выигрыша игрока II удовлетворяет неравенствам [img: http://localhost:8080/file/021002-31.jpg] при известных непрерывных функциях f-2(х 1, х 2), f+2(x1, х 2), то его наибольший гарантированный результат в игре Г 2 определяется из условия максимизации функции от одной переменной. Более общий вариант неполной информированности игрока I об интересах игрока II состоит в следующем: игроку I известна функция f2(x1, x2, а), [img: http://localhost:8080/file/021002-32.jpg]. и известно, что при нек-ром (неизвестном) значении a=a0 истинная функция f2(x1, x2)=f2(x1, х 2,a0). При такой информированности решение игры Г 2 для конечных множеств Асводится к максимизации функции нескольких переменных; при бесконечных множествах Азадача еще более сложна. Наличие неопределенных факторов в постановке игры Г 1 не приводит к принципиальному усложнению задачи, поскольку этот случай сводится к игре без неопределенностей. Для игры Г 2 при неопределенности рассмотрен ряд задач, когда понятие стратегии игроков расширено за счет предложения игрока I игроку II сообщить свой критерий эффективности, т. е. нек-рое [img: http://localhost:8080/file/021002-33.jpg] так чтобы окончательный выбор х 1 мог быть сделан по получении информации о х 2 и критерия эффективности игрока II. Если в этом случае игрок II осторожен, т. е. придерживается принципа наибольшего гарантированного результата, а игрок I сообщает ему параметризованную стратегию [img: http://localhost:8080/file/021002-34.jpg] то можно показать, что наибольший гарантированный результат игрока I равен [img: http://localhost:8080/file/021002-35.jpg] где G2a - наибольший гарантированный результат игрока I в игре Г 2 при данном [img: http://localhost:8080/file/021002-36.jpg] Аналогичный результат без предположения об осторожности игрока II имеет место, когда игроку I известно параметрич. семейство множеств Х 2(a), [img: http://localhost:8080/file/021002-37.jpg] одно из к-рых совпадает с истинным. Близка к рассмотренным задача об отыскании наибольшего гарантированного результата игрока I в игре Г 2 при наличии в функциях выигрышей игроков параметра а, характеризующего природную неопределенность, когда игрок II при своем выборе информирован о конкретной величине а, а игрок I не информирован. В случае, когда игра Г 2 при неопределенности повторяется, информированность игрока I об интересах и возможностях игрока II может быть повышена за счет информации, содержащейся в откликах игрока II на действия игрока I. Построены соответствующие процедуры, позволяющие игроку I, начиная с нек-рой партии, получать результат, сколь угодно близкий к результату, гарантированному ему при полной информированности. Такие же результаты получены и в игре Г 1 с неопределенностями. Если моменты получения игроком I информации о неопределенном факторе а не фиксированы, то игрок I может получить в остальных повторениях результат, сколь угодно близкий к гарантированному ему в условиях полной информированности, при более слабых предположениях относительно функций выигрышей участников. Кроме того, в игре Г 1 аналогичный результат игрок I может получить, наблюдая только за значениями собственной функции выигрыша. Формулировки рассматриваемых игр естественно переносятся на случай многих лиц, взаимодействия к-рых в смысле приоритета действий и передачи информации имеют иерархическую структуру. При анализе этих игр необходимо оговаривать также правила взаимодействий игроков одного уровня. Так, при рассмотрении игры трех лиц, где функции выигрышей игроков имеют вид [img: http://localhost:8080/file/021002-38.jpg] х 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, [img: http://localhost:8080/file/021002-39.jpg] х- {х 1,..., х n}- совокупный выбор игроков на нижнем уровне иерархии, причем они действуют независимо, и каждый игрок номера iраспоряжается выбором х i О Х i. Все множества полагаются компактными, а функции непрерывными. Игрок П 0 рассчитывает на информацию (и будет ее иметь) о выборах [img: http://localhost:8080/file/021002-40.jpg] и сообщает каждому игроку i соответствующую стратегию функцию [img: http://localhost:8080/file/021002-41.jpg] определенную на Xi со значениями из Х i0. Для И. с и. с. плиц получены выражения наибольшего гарантированного результата выделенного игрока при различных расширениях его класса стратегий за счет передачи игрокам нижнего уровня информации о действиях партнеров, а также введения элементов блефа. Как и в играх двух лиц, возможность побочного платежа со стороны выделенного игрока значительно упрощает отыскание его гарантированного результата. При помощи И. с и. с. получают естественную интерпретацию различные механизмы централизованного управления активными экономич. подсистемами. Игра Г 1 описывает процесс централизованного управления при помощи цен; игра Г 2 моделирует политику штрафов и поощрений при стимулировании производства; игрой Г 3 моделируется процесс распределения ресурсов как функций от производственных способов использования данных ресурсов.