автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ информационных обменов в системах управления

На правах рукописи

005006665

Грибов Андрей Геннадьевич

АНАЛИЗ ИНФОРМАЦИОННЫХ ОБМЕНОВ В СИСТЕМАХ УПРАВЛЕНИЯ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-матемаггических наук

- 8 ДЕН 2011

Москва-2011

005006665

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН в Отделе прикладных проблем оптимизации.

Научный руководитель:

доктор физико-математических наук профессор В.В. Дикусар

Официальные оппоненты:

доктор физико-математических наук профессор А.Ф. Кононенко

кандидат физико-математических наук, доцент В.В.Морозов

Ведущая организация:

Учреждение Российской академии наук Институт системного анализа РАН

Защита состоится «29 декабря » 2011г. в

на заседании совета

по защите докторских и кандидатских диссертаций Д 002.017.03 при Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра им. А.А. Дородницына РАН.

Автореферат разослан « » 2011г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 002.017.03 кандидат физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

Системный анализ функционирования объединений промышленных предприятий, совместно реализующих некоторую программу или цель и действующих на основе определенных процедур и правил, представляет собой актуальную задачу. Достаточно обратиться к примерам формирования крупных Государственных корпораций и частно -государственных предприятий. В них объединяются десятки холдингов с разнородными связями и различными интересами при принципиально иерархической структуре объединения. Возникает проблема координации их производственных, финансовых потоков и трудовых отношений. И эти процедуры формирования механизма управления осуществимы только с привлечением моделей и методов системного анализа и вычислительной техники. Можно выделить следующие основополагающие характеристики систем управления для данного процесса: динамичность (постоянное развитие), иерархичность управления (многоуровневые системы), многокритериальность (собственные интересы) и информированность (собственная и общая информация, обмен и передача информация, информационные потоки).

Логика развития научных исследований и прикладные запросы привели в настоящее время к тому, что математическое моделирование служит основным инструментом анализа и синтеза механизмов управления. Активное развитие системных подходов к исследованию иерархической структуры управляющих систем было осуществлено в серии работ западных учёных (Месарович М, Мако Д.,Такахара И.) и в информационной теории иерархических систем, развитой в трудах Моисеева H.H. и Гермейера Ю.Б.. Формальные соотношения в данных подходах, описывающие объект управления и систему управления, образуют математические модели, в которых учитываются требования участников и наличие неопределенности при принятии решений. Такие модели в теории принятия решений носят название теоретико-игровых моделей, или игр. Для иерархических систем существенно, что есть Центр управления и отдельные активные подсистемы, преследующие собственные цели. Выбор решений всех участников осуществляется путем формирования стратегий их поведения, как функций многообразных информационных обменов.

Разработка методов информационных обменов представляют собой одну из наиболее существенных задач процесса принятия решений. Их описание появилось уже в первых работах Цермело Э. и Фон Нейман Дж. по теории игр. В этих работах рассматривались игры в позиционной форме. Участники (игроки) делали конечное число ходов, причём каждый ход для данного участника соответствует выбору одной из конечного множества альтернатив. Участники принимали решения, находясь в соответствующих информационных множествах и располагая информацией о предшествующих выборах других участников. Соответственно, множества управлений участников были сугубо конечными, и объемы передаваемой информации тоже были конечны.

На основе позиционных игр путём введения стратегий выбора решений, как функций от наличной информации, были построены игры в нормальной форме, и для них были определены смешанные расширения в работах Фон Неймана Дж. и Бореля Е.. Множества смешанных стратегий уже континуальны, но обмена информацией об этих стратегиях не предполагалось.

В дальнейшем задача была обобщена, и началось исследование игр в нормальной форме с произвольно большими множествами стратегий, преимущественно континуальными, как, например, в выпуклых играх. Но довольно долго информационные обмены в таких моделях не учитывались. Работа Г.Штакельберга по анализу игр «лидер-ведомый» не привлекла должного внимания.

И лишь существенно позднее были сформулированы содержательные постановки в рамках информационной теории иерархических систем (Гермейер Ю.Б., Моисеев H.H.) и были предприняты попытки описать обмены информацией с помощью игр в нормальной форме в работах Ховарда Н., Гермейера Ю.Б., Кукушкина Н.С. После этого исследования моделей подобного рода приняли массовый характер (см., например, Ватель И.А., Ерешко Ф.И., Горелик В.А., Кононенко А.Ф., Горелов М.А., Мохонько Е.З., Алиев B.C., Морозов В.В., Федоров В.В., Бурков В.Н., Новиков Д.А. и др.). Но во всех этих работах неявно предполагалось, что от игрока к игроку может быть передан любой объем информации, в том числе и бесконечный. Понятно, что в таком случае приходится иметь дело с математической идеализацией, правомерность которой должна быть обоснована. Обычно бесконечность появляется как удобная замена большого конечного числа. И чтобы указанная идеализация была оправданной, нужно, чтобы решения, найденные на моделях с большим конечным объемом информации и на моделях с бесконечным объемом информации были близкими в определенном смысле.

Практика управления реальными системами показывает, что в соответствующих процессах передаются весьма значительные объемы информации, и при современном развитии промышленности они имеют тенденцию к росту. Проблемы соотнесения теоретических результатов принятия решений в условиях различных интересов на иерархических уровнях систем управления и конкретных реализаций имеют место и в теории активных систем (Бурков В.Н., Новиков Д.А.).

Первые модели такого рода по оценке объемов передаваемой информации были исследованы в работах Горелова М.А. В этих работах в качестве принципа оптимальности рассматривался принцип максимального гарантированного результата. В данной работе в качестве оптимальных решений рассматриваются равновесия по Нэшу.

Цель работы состоит в построении модели принятия решений при ограниченном объеме передаваемой информации, в нахождении структуры оптимальных решений информационных расширений исходной игры, т.е. конструктивных условий равновесия по Нэшу, в разработке эффективных методов поиска равновесий в терминах исходной игры и исследовании асимптотических свойств полученных решений при ограничениях на объём передаваемой информации.

Методы исследования.

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

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

Научная новизна.

В диссертации получены следующие результаты, характеризующиеся научной новизной:

1. Предложена новая постановка задачи о формировании информационно-коммуникационной среды в механизмах управления производственными системами в виде теоретико-игровой модели.

2. Предложена новая оригинальная задача принятия решений при передаче ограниченного объёма информации в виде нового математического объекта: модели Гu„={Uji„,Vt„,genMn), являющейся бинарным расширения исходной игры за счёт введения системы обмена информацией между участниками в форме вопросов и ответов.

3. Определено понятие предела для проективной системы игр

где стрелка в записи Г#л<— Г#л+[ отражает

квазиинформационное расширение игр, что позволяет формально определить близость решений игр с континуальными и с конечными объёмами передаваемой информации.

4. Найдено конструктивное описание множества ситуаций равновесия в игре двух участников Г#„ построена асимптотика для множеств ситуаций равновесия введённых игр.

5. Результаты для игр двух участников обобщены на некоторые классы игр многих участников.

6. Построен пример рассмотренных игр, имеющий практическое приложение.

Теоретическая и практическая ценность работы.

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

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

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

Результаты диссертации включены в учебный процесс на факультете ФИВТ МФТИ (ГУ) в курсе «Математическое моделирование конфликтных ситуаций».

Личный вклад автора в проведенное исследование. В диссертацию включены только те новые результаты, которые получены лично автором. В совместно опубликованных работах автору принадлежат 50% результатов.

Апробация работы.

Результаты диссертации докладывались на VI Московской международной конференции по исследованию операций, МГУ им. Ломоносова, ВЦ РАН, Москва, 19-23 октября 2010; Пятой международной конференции "Управление развитием крупномасштабных систем". ИПУ РАН, Москва, 3-5 октября 2011; Международной научно-практической конференции "Теория активных систем - 2011". ИПУ РАН, Москва, 16-18 ноября 2011, а также на научных семинарах ИПУ РАН, ЦЭМИ РАН, ИСА РАН, ВЦ РАН, МФТИ.

Публикации.

По теме диссертации опубликовано 6 печатных работ, объемом 4,1 п.л., из них 3 - в журналах, рекомендованных ВАК, объемом 1,8 п.л.

Структура и объём работы.

Диссертация состоит из введения, четырёх глав, заключения и списка литературы. Основной текст работы изложен на 95 стр. Список литературы включает 30 наименований.

Краткое содержание работы

Во Введении к работе даётся обзор работ по моделированию конфликтных ситуаций, теории игр и исследования операций, обосновывается актуальность темы диссертации, формулируются цели диссертации и научная новизна полученных результатов, а также приводится краткое описание содержания проведенных исследований.

Глава 1 посвящена обзору исследований по моделированию процессов организации объединений производственных объектов, использованию теоретико-игровых моделей в проблемах проектирования механизмов управления, постановке

основной проблемы по обмену информации в иерархических системах и определению места оригинальных исследований диссертации в общей системе работ по теории управления.

В параграфе 1.1 приводится материалы для иллюстрации возможностей теоретико-игрового подхода и эффективности его применения в задачах организации объединения общего типа, и в частности промышленных объединений, и вводятся основные определения. Объектом исследований являются структуры организации, предметом исследований - механизмы управления, а основным методом исследования -математическое моделирование. Применительно к данным системам механизм функционирования - это совокупность правил, законов и процедур, регламентирующих взаимодействие участников объединений; механизм управления - совокупность процедур принятия управленческих решений. Математические модели имеют теоретико-игровой характер. Приводится классификация механизмов управления с точки зрения системного анализа. Согласно данной классификации объектом исследования с формальной точки зрения являются различные расширения исходной игры, заданной в нормальной форме. Аналогично этому подходу в теории системного описания развивающейся экономики описание объектов моделирования (Петров А.А, Поспелов И.Г., Шананин A.A.) также представимо в виде стратегической игры. Государственная политика описывается как воздействия на параметры механизмов самоорганизации экономики. Активности экономических агентов описываются как их индивидуальные и коалиционные поведения и взаимодействия. Указанные соотношения образуют теоретико-игровые модели, и выбор решений осуществляется путем формирования стратегий поведения агентов. Описание поведения агентов выводится из принципов рациональности, агенты решают задачи оптимального управления, и передача информации играет существенную роль.

В параграфе 1.2 содержится обзор подходов информационной теории иерархических систем (Моисеев H.H., Гермейер Ю.Б.), к которой методически принадлежат исследования диссертации. В данной теории рассматриваются различные механизмы управления Центра (выделенного игрока), который имеет возможности осуществления первого хода и выбора некоторой стратегии в зависимости от предполагаемых действий игроков следующего уровня: планирование, стимулирование, координация (Ватель И.А., Ерешко Ф.И., Кононенко А.Ф.). По сути, это были первые примеры квазиинформационных расширений исходной игры в нормальной форме. В рамках этой теории было формализовано понятие проектирования хозяйственного механизма (Горелов М.А., Кононенко А.Ф.), как объекта управления, содержащего следующие элементы: проектирование организационной структуры, планирование, стимулирование, согласование, организация труда, правовые нормы. Исследование элементов механизма проводится на основе теоретико-игровых конструкций. Большое значение придаётся выбору стратегий управления в условиях принципиальной неполноты информации.

В параграфе 13 исследуются примеры формирования крупных корпораций и создание вертикально-интегрированных производственных организационных структур (Кононенко А.Ф., Шевченко В.В.) . Приводятся постановки задач управления производственными корпорациями и примеры методических рекомендаций, основанных на использовании методов математического моделирования. В процессе создания вертикально-интегрированных структур и при управлении их функционированием в рыночных условиях возникает целый ряд формализуемых современными средствами математического моделирования конкретных задач. Среди них: выбор состава создаваемой структуры, построение иерархической системы управления, разработка системы информационного обмена, построение процедур принятия решений, определение механизмов учета (согласования) интересов, разработка гибкой системы компьютерной поддержки информационного обмена и процедур принятия оперативных и стратегических решений и технологии ее постоянной адаптации к изменяющейся обстановке. Фактически

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

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

Ставится проблема описания и сравнения процессов передачи конечных и континуальных («бесконечных») объёмов информации при различных средствах передачи и визуализации информации.

Глава 2 посвящена описанию игр с конечными объёмами передаваемой информации.

В параграфе 2.1 приводится постановка основной задачи.

Игрой двух участников в нормальной форме называют набор Г = (С/,К,£,Л), где и и V - некоторые множества, а § и Л - функции из декартова произведения I! х V в множество действительных чисел.

Элементы множества V называют стратегиями или управлениями первого игрока. Аналогично элементы множества V - это стратегии или управления второго игрока. Интересы первого игрока описываются стремлением к максимизации значений функций Аналогично предполагается, что второй игрок стремится максимизировать значение функции И .

Пару (м,у)еШ К называют ситуацией в игре Г или исходом в игре Г.

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

Введем следующее обозначение. Если X и У - два множества, то Ф{Х,У) будет обозначать множество всех функции <р

Простейший пример описанной выше конструкции выглядит следующим образом. Предположим, что первый игрок рассчитывает, и действительно будет иметь в момент выбора своего управления ие11 полную информацию об управлении уеК, выбранном противником, а второй игрок не имеет никакой информации о выборе противника до того, как сам совершит окончательный выбор. Тогда множество стратегий первого игрока следует отождествить с функциональным пространством Ф{У,Ц), а множество стратегий второго игрока будет совпадать с множеством его управлений V. Если участники выберут

стратегии и.еФ(К,(У) и veF соответственно, то реализуется исход (u4y),v) и участники получат выигрыши g(«>(v),v) и h(u>(v),v) соответственно.

Таким образом, получается новая игра в нормальной форме r.=(i/.,F.,g.,/i.), в которой и>=Ф(У,и), V'=V, а функции g. и /?. определяются равенствами g<(w>,v>)=g(M>(v<),v>) и /;•(««,v>)=/;(«>(v.),v>). Такую игру называют метарасширением Ховарда ранга 1 (см. Howard N., Гермейер Ю.Б., Кукушкин Н.С., Морозов В.В.). Далее запись Г» будет означать, что игра Г< является метарасширением Ховарда ранга 1 игры Г.

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

Если множество Г бесконечно, то рассмотрение игры Г. предполагает, что первый игрок получает и обрабатывает бесконечный объем информации. Разумеется, это является абстракцией. Рассмотрим более естественную конструкцию, что приводит к построению конечной формы передаваемой информации.

Рассмотрим следующую схему взаимодействия участников. Первый игрок вправе задать партнеру и вопросов относительно выбранного им управления veV и получить на них правдивые ответы. Каждый из этих вопросов должен допускать ответ «да» или «нет». Будем кодировать ответ «да» единицей, а ответ «нет» - нулем. Окончательный выбор своего управления ueU первый игрок осуществляет после получения ответов на свои вопросы. Однако он заранее выбирает список вопросов и план своих действий при всех возможных вариантах ответов. Второй игрок выбирает свое управление, не рассчитывая на получение какой-либо информации о выборе партнера.

Нас будут интересовать ситуации равновесия по Нэшу в такой игре.

Приведем определения. Каждой системе из п вопросов рассматриваемого типа соответствует набор из 2 п подмножеств

(ад),(«)'•■•'(«)

пространства V, разбитый на пары. В множество X) входят те и только те управления v е V второго игрока, при выборе которых на вопрос с номером t следует ответить «да». В множество X" входят те управления, которые соответствуют ответу «нет» на вопрос с номером I. Разумеется, должны выполняться условия согласования Х° П X,' = 0, Х° U X) = V, t = 1,..., п.

Задаваемый первым игроком вопрос с номером t может выглядеть следующим образом:

«Верно ли, что выбранное вами управление v удовлетворяет условию v е X) ?».

Разумеется, возможны и другие, эквивалентные вопросы. Ниже мы увидим, что при «оптимальном» выборе стратегий соответствующие вопросы могут быть заданы в достаточно конструктивной форме.

Каждому булеву вектору г = (/¡,г,,...,г„) из множества /V = (0,1}" можно поставить

в соответствие множество X'=f]X?. Получив ответы (г,,г2).,.,г„) на свои вопросы,

(=i

первый игрок может и должен выбрать управление ur eU. Таким образом, стратегия первого игрока определяется заданием 2п множеств вида, удовлетворяющих условиям согласования, и т = 2" управлений u' е С/, г е N. В дальнейшем иногда будет удобно отождествить вектор (г,,г,,...,/-„) е N с натуральным числом г, -2""' +г2 •2"~2 +... + гп -2" из множества {0,1,...,ш-1}, для которого последовательность r,r2..r„является записью в двоичной системе счисления.

Если первый игрок зафиксировал свою стратегию такого вида, а второй игрок выберет управление veF, то участники получат выигрыши g(ur,v) и h(u',v) соответственно, где ответ г однозначно определяется условием v е X" .

Определим функцию P-.V-+N условием P(v) = г, если v е X' и такую функцию

Ü:N-*U, что м(г) = и . Тогда стратегию и,„ первого игрока можно отождествить с

парой функций а стратегии второго игрока, как и в случае метарасширения

Ховарда, будут совпадать с выборами в исходном множестве V. Выигрыши участников будут определяться функционалами

ft.(«,..v,„) = g("Wv)),v) и h,„(ut.,v,„) = Ki{P(y)),v).

Таким образом, получаем новую игру Гs„={Uii„,Vm,g(„,ht„), в которой множество стратегий первого игрока Ui>„=Q>(N,U)x<b(V,N), множество стратегий его партнера V*„=V, а функционалы g,„ и h,„ определяются приведенными условиями.

Игру Г#„ будем называть бинарным расширением порядка п игры Г.

Интерпретируются введенные конструкции следующим образом. Число вопросов п задает измеряемый в битах объем информации, которую получает и обрабатывает первый игрок. Это - чисто синтаксическая характеристика. Семантика получаемой информации задается отображением Р. Эту семантику определяет первый игрок. Функция u:N-*U описывает, какое управление будет выбрано первым игроком в зависимости от полученной им информации.

Для того, чтобы построить замкнутую модель процесса принятия решений в условиях конфликта, недостаточно описать возможности и интересы участников конфликта (что делается заданием игры Г). Нужно еще описать отношение участников к имеющейся у них неопределенности, то есть задать некий принцип оптимальности. Ниже будет использован принцип, предложенный Дж. Нэшем. В настоящее время этот принцип оптимальности является наиболее широко распространенным в аналитических исследованиях.

Ситуация (и°,у°) в игре Г называется ситуацией равновесия по Нэшу (или просто ситуацией равновесия), если для любых стратегий ueUnveVвыполняются неравенства

g(",v°)<g(wV) и h{u,v°)<h{u ,vü).

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

Множество всех ситуаций равновесия в игре Г будем обозначать символом NE(Г).

Ситуации равновесия в игре r = (U,V,g,h) составляют множество решений системы уравнений

fg(u,v) = maxg(u',v),

u-zU

I h(u,v) = maxg(i/,v).

Относительно игры r = (U,V,g,h) будем предполагать, что U и V - замкнутые и ограниченные подмножества конечномерных евклидовых пространств (своего для каждого игрока). Функции g и h будем считать непрерывными.

С этой игрой Г связаны ее метарасширение Г. и счетное число бинарных расширений Г«„. Структура множества ЩГ.) описана в работах Кукушкина Н.С. и Морозова В.В.

В дальнейшем нас будет интересовать аналогичная струюура множеств ИЕ{П„) и соотношения между множествами ЫЕ{Г»„) при разных п и множества ИЕ(Г.).

Параграф 2.2 посвящен исследованию свойств бинарных расширений и их аксиоматизации.

Определение. Говорят, что игра Г,=<(/', 1'1^1,/!1> является квазиинформационным расширением игры Г=<и,У^,И>, если задан набор <ж,с,д> функций ж.и'хУ'-^С/хУ, с:[/->и' ис/.У-^У1, удовлетворяющий следующим двум аксиомам: а) яУУ^яСм'У)),

б) ^(с'МУ))^. яУДу)))=у для всех ие£/, уеУ, и'е(У1, у'еУ1 (здесь я* и я2 обозначают композиции отображения ж с проекциями декартова произведения и*. V на сомножитель V и V соответственно).

Определение. Квазиинформационное расширение, в котором стратегии каждого игрока проинтерпретированы, как способы реагировать на определенную информацию о поведении партнеров, называется информационным расширением.

Набор/=<гг,с,с!> будем называть морфизмом игры Г1 в игру Г.

Бинарные расширения являются информационными расширениями. Соответствующий морфизм <л,сЛ> может быть задан следующим образом. Отображение м-.и*„хУ,„-^ихУ задается равенством Ммчп№*У=(ц{Р(у,щ)),ч,,), если м#„=(м,/>).

Отображение с:£/->(У. ставит в соответствие управлению иеЦ пару (и,/3) такую, что

Ду)=(1,1,...,1) для любого V, а и(г) = и для любого г. Отображение ¿/ив данном случае -тождественное.

Построенные морфизмы будем называть каноническими.

Таким образом, в общем случае может существовать и больше одного морфизма Г1 в игру Г (разумеется, таких морфизмов может не существовать вовсе). Множество всех морфизмов Г1 в игру Г будем обозначать Нош(Г',Г)-

Введенные выше конструкции представляют для нас интерес постольку, поскольку они определенным образом согласованы с концепцией равновесия по Нэшу. А именно, имеет место

Лемма 2. Пусть игра Т^=<и\У{&\1гх> является квазиинформационным расширением игры Г=<и,У&,И> и /=<я,сД>еНот(Г',Г). Тогда если (г/,у)еЛг£(Г), то (ф)Ду))бЩ Г1).

Содержательно доказанная лемма означает, что при увеличении информированности участников множество ситуаций равновесия не уменьшается.

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

Игра Г»гМУгпуУпп&п^) - это такая же игра в нормальной форме, как и игра Т=<и,У^,И>. Поэтому к ней может быть применена конструкция бинарного расширения, скажем, с к вопросами. В результате получим новую игру (Г>. Справедлива

Теорема. Игра (Г«„)5/[ изоморфна игре Г«„ч- в том смысле, что каждая из них является квазиинформационным расширением другой.

Следствие. Отображение схс! взаимнооднозначно отображает множество МЩГ#„)и) в Лг£(Г//„+1), причем если /¡¡ц - канонический морфизм (Гц^щ в Г, а /» -канонический морфизм Гв Г, то композиция /„°(схс1) = /„, и, соответственно, выигрыши в ситуациях равновесия ((«*„)«,(у»,,)«) и (с((и#„)з^)Д(у#„)#4.)) совпадают.

Дадим содержательную интерпретацию утверждений теоремы и следствия из нее. Допустим, первый игрок может получить и своевременно обработать п+к бит информации. Он может поступить двояко:

• сразу задать п+к вопросов и, получив ответы на них, выбрать свое управление;

• сначала задать к вопросов, получив на них ответы, сформировать дополнительный список из п вопросов, и только получив ответы на эти п вопросов выбрать свое управление.

Теорема утверждает, что получающиеся в этих двух случаях игры отличаются несущественными деталями. Следствие показывает, что и ситуации равновесия в этих двух играх совпадают.

Поэтому в дальнейшем мы будем рассматривать только первую из этих двух задач.

Параграф 2.3 посвящён исследованию системы игр с конечным объёмом передаваемой информации. Показано, что при любом и=0,1,2,... игра Г#„+1 является квазиинформационным расширением игры Г#„. Для проективной системы игр

Г=Гт<-Гв1<-Г#2<-. ■ .*-Г«„<-Г*„+1<-- • ■

где стрелка в записи Г«„<-Г#„+1 означает построенный выше морфизм /„+1=<я-„+,,с„+|,4г+1>, вводится понятие предела этой системы.

Рассмотрим игру Г"„=<£/=, г*,/ь) определенную следующим образом. Множество Уа=У. Множество 1]ц состоит из всех функций щ'У-^и, каждая из которых имеет лишь конечное множество значений. Функции g, и Л» определяются равенствами

Построенная игра Г# является квазиинформационным расширением игры Г. Более того, справедлива

Лемма 1. Для любого л=0,1,2,... игра Г# является квазиинформационным

расширением игры Г#„.

Непосредственно проверяется также следующий факт.

Лемма 2. Если морфизмы /л+ь/™ и/,„+1 определены так, как описано выше, то

/к* = /л+1 "/«>.+1 '

Справедлива

Лемма 3. Пусть для любого п=0,1,... игра Г(§=<£%,является квазиинформационным расширением игры Г#„, причем соответствующие морфизмы игры Г@ в Г«„ удовлетворяют условию =/„+, °4„+|. Тогда

существует единственный морфизм /„^<^„.с„.с1:1> игры Г®, в Г# для которого

Важным частным случаем приведенных конструкций является метарасширение Г., поскольку справедлива

Лемма 4. Для любого л=0,1,... игра Г. является квазиинформационным

расширением игры Г«„.

Как следствие получаем, что игра Г. является квазиинформационным расширением игры Г#. Соответствующий морфизмнетрудно выписать явно. Поскольку по определению и Уц=У>, в качестве отображений с-а и ¿ч естественно выбрать

канонические вложения. Тогда, если функция и.еФ(7,£/) принимает лишь конечное число значений, то проекция лдолжна быть равна (м>,у.). Для всех остальных функций и. проекция где и» - функция из Ф(У,Ц), тождественно равная и.(у).

Таким образом, как утверждает лемма 3, из всех игр, которые можно рассматривать как информационные расширения одновременно всех игр Г#„ «самой простой» является игра Г#.

Игра Г» является новым объектом исследования, и представляет весьма значительный интерес. В самом деле, рассматривая её, мы заранее не задаем ограничения

на объем информации, получаемой и обрабатываемой первым игроком. Но если первый игрок выберет любую стратегию в такой игре, то для ее реализации необходимо получить и обработать конечный объем информации (свой для каждой стратегии). Это характерно для прикладных задач, в то время как в метарасширении «почти каждая» стратегия предполагает использование бесконечного объема информации.

Глава 3 посвящена описанию структуры ситуаций равновесия во введенных квазиинформационных расширениях игр.

В параграфе 3.1 рассматриваются ситуации равновесия в игре Г#„. Исход (u,v)eUxV, назовем равновесным, если существует такая стратегия (и,РJ первого игрока в игре Г«„, что вместе со стратегией v она образует ситуацию равновесия, и выполняется условие u(P(v)) = и. Множество равновесных исходов допускает конструктивное описание. А именно, справедлива

Теорема. Для того чтобы исход (w°,v°) был равновесным, необходимо и достаточно, чтобы выполнялись условия

шах g(u, v°) = g(«°,v°), min max min A(u',v)<A(u°,v°).

(MV.....^c" 1 V€l- OSlS/H-l

Данная теорема позволяет для каждого равновесного исхода (w°,v°) построить, по крайней мере, одну ситуацию равновесия, которой этот исход порождается. Кроме того, анализ доказательства теоремы позволяет описать и все множество ситуаций равновесия.

Остановимся на содержательной интерпретации найденного решения. Как и в классическом случае, структура равновесной стратегии первого игрока предполагает выбор заранее согласованного управления и", если партнер выбрал равновесное управление v°, и использование "наказания" в противном случае. Это "наказание" может быть не предельно жестоким. Важно только, чтобы оно было достаточно эффективным. В частности, для "наказания" может использоваться и равновесное управление и0.

Рассмотрим, как могут выглядеть те вопросы, которые первый игрок задает второму. Пусть ((u,P),v°J - ситуация равновесия и и°,и\.,.,ит"'-значения функции и.

Если первый игрок задаст партнеру вопросы

«Верно ли, что при выбранном Вами управлении v выполняется неравенство h(ur,v)<h(u\v°)b>, /=0,1,...,«!,

то ответ хотя бы на один из вопросов непременно будет положительным. Если г наименьший номер такого вопроса, то выбор управления иг сделает отклонение второго от согласованного плана невыгодным для него. Но в данном случае имеется т=Т вопросов, что значительно больше п. Показано, что число вопросов можно уменьшить до п.

В параграфе 3.2 описано множество равновесных исходов в игре Г». Одной из целей данной работы является сравнение множеств ситуаций равновесия в играх Г» и Г«. Делать это удобно в терминах множеств равновесных исходов. В соответствии с результатами Кукушкина Н С. и Морозова В.В., исход (u,v)eUxV, назовем равновесным в игре Г», если существует такая ситуация равновесия (u«,v) в игре Г>, что w(v»)=u и v>=v.

Лемма 1. Для того чтобы исход (u",v) был равновесным, необходимо и достаточно, чтобы выполнялись условия

maxg(«,v°) = g(u0,v°)

net/

и

max min h(u, v) < h(u", v°).

Аналогично предыдущему введем понятие равновесного исхода в игре Г«. Исход (и,\)еШУ, назовем равновесным в игре Г«, если существует такая ситуация равновесия

в игре Г«, что и у»=у.

Обозначим через Е„ множество равновесных исходов в игре Г,„ с п вопросами, а буквой Е- множество равновесных исходов в игре ГУ Справедлива

Лемма 4. При любом п выполнено включение Е„аЕ.

Обозначим £° множество тех исходов для которых выполняется шах ттк(и,\) < А(и°,у°).

Лемма 5. Множество £° содержится в объединении .

П = 1

Для краткости назовем условием регулярности следующее утверждение: «Замыкание множества £° совпадает с множеством £». Игры, для которых выполняется это условие, будем называть регулярными.

Из доказанных лемм непосредственно вытекает

Теорема. Если выполнено условие регулярности, то замыкание объединения

совпадает с множеством Е.

Справедлива также

Теорема. Пусть выполнено условие регулярности. Тогда для любого £>0 существует такое п, что для любого исхода (и°,у°)еЕ найдется такой исход (и,у)еЕ„, что выполняются неравенства! и-иI <еи | <е.

Данные теоремы по-разному свидетельствуют о том, что условие регулярности является достаточным для корректности перехода от игр с большим числом вопросов к игре с бесконечным числом вопросов. Вероятно, условие регулярности не является необходимым для обоснования корректности перехода от игр Г# к классической игре Г.. Однако совсем отказаться от этого условия нельзя, что демонстрирует построенный в параграфе пример. Таким образом, пользоваться идеализацией, допускающей обмен бесконечными объемами информации нужно с определенной осторожностью.

Обозначим Ме(Гц„), №(Г#) и множества равновесных исходов в играх Г#„, Г« и Г» соответственно. Эти множества удобнее множеств ситуаций равновесия, поскольку все они принадлежат одному пространству {/х V. Следовательно, их можно сравнивать.

Имеют место для любого п=0,1,... включения

№(Г«„)сЛ'г(Г#)еДгг(Г.).

И отсюда

£°сЛВД,)с£.

Это соотношение дает простое описание равновесных исходов в игре Г#.

Нетрудно описать и структуру ситуаций равновесия в этой игре. Структура ситуаций равновесия в играх Г#„ описана в предыдущем параграфе. По ситуации (и6„уц„) ситуация (с,„(щ„),^„(щ„)) строится вполне конструктивно, поэтому и ситуации равновесия в игре Г# могут быть достаточно просто описаны. Они также предполагают выбор некоторого согласованного исхода и использование первым игроком наказания противника в случае отклонения того от выбранной стратегии.

В параграфе 3.3 рассматриваются игры с вопросами конечной сложности в отношении второго игрока.

Как и выше, возможны два близких, но все же различных подхода:

• можно рассматривать игры, в которых объем информации, получаемой вторым игроком, заранее ограничен некоторым числом;

• можно изучать игры, в которых этот объем заранее не ограничен, но каждая фиксированная стратегия предполагает передачу информации конечного объема.

Оба вопроса исследуются аналогично. Мы рассмотрим второй из них.

Зафиксируем базисы в евклидовых пространствах, содержащих множества управлений U и V (наличие таких пространств мы заранее предполагали). В дальнейшем управления и и v будем отождествлять с их координатами в этих базисах.

Обозначим ¡U (соответственно ¡V) множество тех векторов «et/ (соответственно veF), все координаты которых могут быть записаны в виде конечных двоичных дробей. Рассмотрим игру f=(jU,fV,jg,jh), где ¡g и /А - сужения функций g и И на декартово произведение jUxjV.

Определим следующее квазиинформационное расширение fs=ijUs,fVs,igs,ßJs) игры f={jU,fV,/g,jh) и соответствующий морфизм fs=<^s,cs,ds>. Положим ßJ^LTxV, и jV$=V (здесь'и далее If обозначает m-кратное декартово произведение множества U на себя). Если jus=(u°,и™-1,«') и /v$=v, то значение проекции jt${/us,jvs) определим следующим образом. Если 'h(u°,v)<h(u°,w), то положим ffs(/ws,/vs)=(»V). В противном случае выберем наименьшее г, для которого

h(u',v)= min h(ub,v)

и положим 7rs(/!is,/vs)=(",v)- Вложение es определим, положив cs(u)=(u,u,...,u,w ) (здесь w° - произвольный фиксированный элемент множества V; от его выбора ничего не зависит - расширения получаются изоморфные). Отображение ds будем считать тождественным отображением множества/Vна себя.

Справедливость аксиомы б) квазиинформационного расширения проверяется непосредственно. Функции выигрыша^ и ßi$ определим так, чтобы выполнялась аксиома

Справедливо утверждение: Игра fs„ игры уГ является квазиинформационным расширением игры

Поскольку в нетривиальных случаях множества стратегий в построенных играх /Г HyTj не являются компактными, то естественным аналогом равновесий по Нэшу для таких игр является понятие £-равновесия.

Ситуация (u°,v°) в игре Г называется ситуацией е-равновесия, если для любых стратегий Met/и ve Vвыполняются неравенства

g(ii,v°)<g(M0,v0)+f и h(u,v)<h(u,v°)+s.

Множество всех ситуаций ¿-равновесия в игре Г будем обозначать NE ff).

Примем, что исход (u,v)ejUx/V является г-равновесным в расширении fs, если найдется такая ситуация г-равновесия , что 7ts(jus,jvs)=(u,v). Тогда справедлива

Теорема. Для того чтобы исход (m°,v°) был е-равновесным, необходимо, чтобы выполнялись условия

supg(«,v0)<g(»0,v°) + ff,

UEfU

inf sup min h(u',v)<h(u',v°) + s, („' ,U-.....»■*■' Н/Ь—' v6/r Osiäm-1

и достаточно, чтобы выполнялись строгие неравенства sup g(uy)<g(u°y) + e,

inf sup min h(u',v)<h(u°,v") + £ («V.......у^г05«™-'

Полученный результат записывается в терминах множеств ¡U и jV, а не исходных множеств U и V. Это принципиально, что демонстрирует построенный пример.

Можно найти условия, при которых замена /U и ¡V на U и V соответственно в теореме возможна.

Лемма. Пусть множества U и V совпадают со своими замыканиями. Тогда sup g(«,v°) = maxg(u,v°)

и

inf sup min h(u',v)= min max min /?(«',v).

(«V.....i/^'^f"4 v€/[-0Sj<m-l ......1 w€l' OSvim-l

Теорема. Пусть множества U и V совпадают со своими замыканиями. Тогда для любого ¿>0 множество NE(Г) содержится в замыкании множества NEJtjCs) (замыкание понимается как замыкание в объемлющем евклидовом пространстве).

Таким образом, при некотором дополнительном геометрическом условии переход к задаче, допускающей использование вопросов «бесконечной сложности» является корректным.

Глава 4 посвящена некоторым обобщениям полученных результатов на случай игр со многими участниками и примеру, допускающему экономическую интерпретацию.

В параграфе 4.1 рассматриваются игры многих участников с информационным посредником.

Определение. Игрой р участников в нормальной форме называется набор r=<-{\2.,...j)},Ul,...,lfgl,...jf>, где {1,2,...,р} - множество, содержащее р элементов, - произвольные множества, g- функции, каждая из которых отображает произведение С/'х...х(/ в множество действительных чисел. Числа /е{1,2,...^?} интерпретируются как номера участников, множество Ü представляет собой множество управлений (стратегий) участника /', а функция g - его критерий (функция выигрыша). Будем считать, что цель участника состоит в максимизации его критерия.

Нормальная форма подразумевает, что, выбирая свое управление, каждый участник не имеет никакой информации о выборах своих партнеров.

Набор и=(и',...,г/) управлений всех участников будем называть ситуацией в рассматриваемой игре или исходом той игры. Множество всех ситуаций U'x...x[f будем обозначать буквой U без индекса.

Введем удобное обозначение. Пусть u=(u',...,if) - ситуация, a v'eif - управление го игрока. Символом («II v') будем обозначать такую ситуацию ic=(iv',.. ,,i/), что

\и', при if' = \

[v', при j = г.

Понятие равновесия по Нэшу обобщается на случай игр многих участников следующим образом.

Определение. Ситуация и называется ситуацией равновесия по Нэшу в игре Г=<{ 1,2,.. t/',... ,i/„g',... „g^,

если для любого ;'е{ 1,2,...,р] и любого v'e С/

выполняется неравенство

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

образом, его стратегиями являются функции и', е [/',[/'j а выигрыши участников в

соответствующей игре вычисляются по формулам

g'.(ul, и1.,. ..,«.') = g'("!(".2,-."O, и.2,...Х),'-1,2,-.-,р.

Эти конструкции, разумеется, не предполагают наличия каких-то ограничений на объем информации, получаемой и перерабатываемой первым игроком. Если такое ограничение есть, то довольно естественно выглядит появление и некоторых дополнительных ограничений на структуру получаемой первым игроком информации. В данном параграфе мы будем предполагать, что таких дополнительных ограничений нет.

А именно, будем считать, что в игре имеется некий посредник, который имеет полную информацию об управлениях, выбранных участниками 2,3,...,/? и может ответить первому игроку на любые вопросы, касающиеся этих управлений.

Более конкретно, рассмотрим следующую схему взаимодействия участников. Первый игрок вправе задать посреднику п вопросов относительно выбранных остальными участниками управлений (и2,«3,...У)е(/2х(73х...х{/' и получить на них правдивые ответы. Каждый из этих вопросов должен допускать ответ «да» или «нет». Как и прежде, будем кодировать ответ «да» единицей, а ответ «нет» - нулем. Окончательный выбор своего управления и е и первый игрок осуществляет после получения ответов на свои вопросы. Однако он заранее выбирает список вопросов и план своих действий при всех возможных вариантах ответов. Остальные участники выбирают свои управления, не рассчитывая на получение какой-либо информации о выборе партнера. Нас будут интересовать ситуации равновесия по Нэшу в такой игре.

Обозначим буквой Рдекартово произведение £/2хС/3х...х(/. Каждой системе из п вопросов рассматриваемого типа соответствует набор из 2п подмножеств

(ад),(ад),..,(ад)

пространства V, разбитый на пары. В множество Л",1 входят те и только те управления V е К второго игрока, при выборе которых на вопрос с номером I следует ответить «да». В множество Х° входят те управления, которые соответствуют ответу «нет» на вопрос с номером /. Разумеется, должны выполняться условия X,"ПХ,' = 0, X,"их,' = V, I = 1,...,л.

Задаваемый первым игроком вопрос с номером I может выглядеть следующим образом:

«Верно ли, что выбранное моими партнерами управления (и ,и ,...,\1>) удовлетворяют условию (и2,и,,...,ир)е Л",'?».

Разумеется, возможны и другие, эквивалентные вопросы. Ниже мы увидим, что при «оптимальном» выборе стратегий соответствующие вопросы могут быть заданы в достаточно конструктивной форме.

Каждому булеву вектору г = (г,,г2,...,/•„) из множества N = {0,1}" можно поставить

в соответствие множество ХГ=[]Х?. Получив ответы (г,,/-2,..,г„) на свои вопросы,

ы

первый игрок может и должен выбрать управление и1'" е и'. Таким образом, стратегия первого игрока определяется заданием 2п множеств вида (1), удовлетворяющих условиям (2), и т = 2" управлений ии е£/\ г е N. В дальнейшем иногда будет удобно отождествить вектор (/•|,г2,...,г„)е N с натуральным числом гх+г2 ■2"~2 +...+г„-2° из множества {0,1,...,т-1}, для которого последовательность г,г2...гП является записью в двоичной системе счисления. Такое отождествление не должно вызвать недоразумений и потому будет делаться без особых оговорок.

Если первый игрок зафиксировал свою стратегию такого вида, а остальные игроки выберут управления (и2,м3,...,1/)еГ, то игрок с номером 1 получит выигрыш g,(ыи,и2,...,ир), где ответ г однозначно определяется условием (и2,и,,...,ир)£ X'.

Определим функцию P\V N условием P(v) = г, если vel' и такую функцию

u:N —>U, что и(г) = и1,г. Тогда стратегию первого игрока можно отождествить с

парой функций (и,Р), а стратегии остальных участников, как и в случае метарасширения

Ховарда, будут совпадать с управлениями. Выигрыши участников будут определяться функционалами

Таким образом, получаем новую игру

г,„=({u ,..,p},uL,ul,-,u[„,sLgL-,gL),

в которой множество стратегий первого игрока ие„=Ф(М,и')хФ(У,М), множества стратегий его партнеров U't„ = U', < = 2,3,—,р, а функции определяются условиями аксиомы квазиинформационного расширения.

Игру Г»„ будем называть бинарным расширением порядка п игры Г. Нас будет интересовать структура множества NE(Г#„) ситуаций равновесия в игре Г#„.

Исход (u^,...,up)eU<x...xUp будем называть равновесным, если существует ситуация равновесия в игре Г#„ такая, что

»'="№2.....,<,)), и2 = и,=

где и\п =(и,Р).

Далее будем предполагать, что £/', [/,...,{/ - замкнутые ограниченные подмножества евклидовых пространств, а функции g' непрерывны на U[x...xlf.

Справедлива

Теорема. Для того, чтобы исход и=

(и1,...У) был равновесным необходимо и

достаточно, чтобы выполнялись условия

g'(u',u2,...,ur) = maxg'(v' ,и2,...,ир),

v'eL/1

min max minmaxig'((w v')!«1')-е'(и)1<0,

(»'■'У-...................v'Jel- rs.V 2S/S, " II 'II ' & V "

где и'

Таким образом, описана структура множества равновесных исходов в игре Т#„. Исследование асимптотики поведения этих множеств при неограниченном увеличении п аналогично проведенному в параграфе 2.2. и результат подобен построенному

В параграфе 4.2 рассматриваются игры с ограниченной информированностью участников.

Постановка задачи из предыдущего параграфа предполагала, что имеется агент, который информирован о всех управлениях (и2,и ,...,it), выбранных участниками с номерами ¡=2,3,.../) и может ответить первому игроку на любой вопрос, относящийся ко всей совокупности этих управлений. На практике может случиться, что такого агента нет: каждый из участников знает выбранное им самим управление, а полной информацией никто не обладает. Соответственно, первый игрок может задать каждому из своих партнеров по нескольку вопросов и на основании полученных ответов принимать свое решение.

В этой ситуации опять возможны различные варианты постановки задачи. Можно предполагать, что число вопросов, задаваемых каждому из участников, является параметром задачи. А можно предполагать, что первый игрок сам вправе решать, какое количество вопросов задать каждому из своих партнеров, а ограничено лишь суммарное число вопросов. Мы начнем с рассмотрения первого варианта, как более простого.

А именно, будем считать, что первый игрок вправе задать /-му игроку п' вопросов (;-2,3,...,р). Обозначим вектор (пг,пъ ,...rf) символом п. Положим т' = 2" и N' ={0,1}" , N=N2xN3X...XN1'.

Формальная постановка задачи.

Пусть задана игра многих участников r=<{\,2,...,p},U',...,lf,g Далее

будем предполагать, что и\ U2,...,Lf - замкнутые ограниченные подмножества евклидовых пространств, а функции g' непрерывны на U'x.-.xlf.

Рассмотрим новую игру Г,-={{l,2,...,p},f/;-,fy,2-,...,i/;-,gi-,g^,...,g,''-), заданную

следующим образом. Пусть u:N->Ul h/^-WV (i=2,3,...p). Стратегией первого игрока

в игре Г,- будем считать набор и\- =(й,Р2,Р\..,Р"). Таким образом, р

U\- = Ф(ЛР,(7)х]^[Ф(С/',ЛГ'). Для i=2,3,...p положим U't- = U'. Функции выигрыша gt- в

(=2

игре Г,- определим условиями

¿¡(«¡Х....,«;-)=¿(й(р\и],),р\и1,).....•

Нас будут интересовать ситуации равновесия по Нэшу в игре Г#-. Как обычно, будем описывать их в терминах равновесных исходов. Исход (ui,...,up)eUlx...xllp будем называть равновесным, если существует ситуация равновесия (и\-,и]-,...,и'-) в игре Гв-такая, что

«' =(ü(P\u2J,P\u],\...,P'(u:-)), и' =„;-,

если и\- = {й,Р\Р^.,Р'). Справедлива

Теорема. Для того, чтобы исход u=(ux,...,if) был равновесным необходимо и достаточно, чтобы выполнялись условия

g\u\и\..., и") = maxgVy,...,«'),

min maxming'((«|v')||i/1'')^g,(«). '=2,3,...,/>

<„»,„'■'.....„"'-1 )€((,''r' v'el'' re.V » »

где при каждом i предполагается, что ul,0=u\

Теперь обратимся к случаю, когда первый игрок вправе сам решать, сколько вопросов он задаст каждому из своих партнеров, но суммарное число вопросов равно п. Эта модель может быть формализована следующим образом. Обозначим

соответствующую игру Г,,„ =({1,2,...,р},(/¿,„,(/,2,„,...,£/,',„,g»„,-.gu„)-

В ней положим U\,n= |J i/#-,, U'm„ =£/', i = 2,3,-, P, а функции Ig;,„

определяются следующим образом. Если и},„ е U\- и и\- = (и,Р2,Р!...,Рр), то положим

g',,„«,. <4, ) = *' X r3(»L )>■■■> pp("L)). <...... «ü.) •

Этими условиями значения функций g'm„ определены для всех

р

r=t

Непосредственно проверяется справедливость следующего утверждения. Теорема. Справедливо равенство

„W+...+«'.»

Интересно сравнить множество равновесных исходов Ne(T#«„) в игре r##w с множеством равновесных исходов Ле(Г#„) в игре Г#„, рассмотренной в предыдущем параграфе. Каждая стратегия и'„„ е Ulm„ естественным образом отождествляется с некоторой стратегией i/^et/,, так, что для любых н е U2,...У elf выполняется равенство

Поэтому справедливо включение Лге(Г#«„)с №(Ги„).

Это включение может быть строгим, как показывает пример, приведенный в параграфе.

В параграфе 4.3 рассматривается практический пример.

Рассмотрим ситуацию, когда р предприятий продают на рынке однородный продукт. Затраты ;-ого предприятия на производство или закупку единицы продукции не зависят от масштаба производства и равны с'. Управлением предприятия является объем выпуска и' (по своему смыслу эти величины неотрицательны). Целью деятельности предприятия является максимизация прибыли ¿{u)=q{u)u'-c'u. Будем считать, что

рыночная цена продукции линейно убывает с ростом суммарного

р

предложения: q(u) = а~ А^ и', где а и Ъ - некоторые положительные константы. Для <=1

простоты будем предполагать, что возможности предприятий не ограничены, то есть множество управлений /-го участника представляет собой отрезок [/=[0,итах], где нтах -некоторое число, большее, чем отношение alb.

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

Рассматриваются различные постановки расширений игры, приводятся аналитические решения относительно ситуаций равновесия по Нэшу, анализируются свойства полученных решений. Отмечается, что при любом номере п расширений любое предприятие может гарантировать себе, по крайней мере, нулевой выигрыш, выбрав нулевое управление. Анализ найденных решений позволяет сделать следующие выводы.

Во-первых, одному и тому же участнику не имеет смысла задавать более одного вопроса: никакой дополнительной полезной информации при этом получено не будет, и множество равновесных исходов не изменится. Во-вторых, множество равновесных исходов существенно зависит от того, кому из своих конкурентов имеет возможность задавать вопросы первый участник. В-третьих, при п<р включение Ne(Y##„)с №(Г##„-ц), вообще говоря, строгое.

Эти и другие качественные особенности решений задач, рассмотренных в данном параграфе, в значительной степени определяются простой структурой функций выигрыша участников, а именно, наличием универсальной стратегии "наказания", то есть такой стратегии ы' первого игрока, что равенство

g'(u',u2,...,uF) = rning'(v',H2,...,u'')

выполняется при всех i=2,...,p и всех управлениях к2,«3,...,г/.

В Заключении сформулированы основные результаты, полученные в диссертации.

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

2. Введен в рассмотрение новый математический объект: игра двух участников Г«„, как и-мерная аппроксимация исходной игры в нормальной форме, путём включения в стратегии выделенного участника набора из п вопросов ко второму участнику. Показано, что последовательность игр Г#„ имеет естественный предел и описана его структура.

3. Найдены конструктивные описания множеств ситуаций равновесия в оригинально введённых играх двух участников. Установлены условия корректности постановки задач с континуальными стратегиями.

4. Построено обобщение введённого класса игр на случай многих участников при наличии и отсутствии информационного посредника. Приведены конструктивные описания множеств ситуаций равновесия в этих играх.

5. Получены аналитические решения в явном виде для конкретной модели взаимодействия нескольких предприятий, как иллюстрации реализуемости общего подхода.

Публикации по теме диссертации.

1. Грибов А.Г. О постановках задач в играх с конечным объёмом передаваемой информации. // Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(2). С. 19-24.

2. Горелов М.А., Грибов А.Г. Равновесие в играх с конечным объёмом передаваемой информации. //Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(1).С. 66-77.

3. Грибов А.Г. Аксиоматика бинарных расширений игр в нормальной форме //Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(3).С. 31-36.

4. Горелов М.А., Грибов А.Г. О принятии решений при ограниченном объёме передаваемой информации. // Материалы Пятой международной конференции "Управление развитием крупномасштабных систем". МЬ8Э'2011. ИПУ РАН, 3-5 октября 2011г. Т. 2, С.216-218.

5. Грибов А.Г. Об играх многих лиц с информационным посредником. // Труды Международной научно-практической конференции "Теория активных систем - 2011". ИПУ РАН, 14-16 ноября 2011. Т. 2. С. 97-100.

6. Грибов А.Г. Дикусар В.В. Передача конечного объёма информации в играх многих лиц. В серии "Сообщения по прикладной математике", М., ВЦ РАН, 2011.с. 32

Подписано в печать:

23.11.2011

Заказ № 6338 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Глава 1 ТЕОРЕТИКО-ИГРОВЫЕ МОДЕЛИ МЕХАНИЗМОВ УПРАВЛЕНИЯ ПРОМЫШЛЕННЫМИ ОБЪЕДИНЕНИЯМИ И ПРОЦЕДУРЫ ОБМЕНА

ИНФОРМАЦИЕЙ В ИЕРАРХИЧЕСКИХ СИСТЕМАХ

§1.1 Системный анализ механизмов управления

§ 1.2 Методические основания информационной теории иерархических систем

§1.3 Вертикально - интегрированные промышленные структуры

§ 1.4 Проблема синтеза информационного управления в объединении

Выводы по Главе

Глава 2. ИГРЫ С КОНЕЧНЫМ ОБЪЁМОМ ПЕРЕДАВАЕМОЙ ИНФОРМАЦИИ

§ 2.1 Постановка задачи

§ 2.2 Бинарные расширения

§ 2.3 Проективная система игр

Выводы по Главе

Глава 3. СТРУКТУРА СИТУАЦИЙ РАВНОВЕСИЯ

§ 3.1 Игры с ограниченным объёмом передаваемой информации

§ 3.2 Множество равновесных исходов в игре Г#.

§ 3.3 Игры с вопросами конечной сложности

Выводы по Главе

Глава 4. НЕКОТОРЫЕ ОБОБЩЕНИЯ И ПРИМЕР

§ 4.1 Игры многих лиц с информационным посредником

§ 4.2 Игры с ограниченной информированностью игроков

§ 4.3 Пример

Выводы по Главе

Системный анализ функционирования объединений промышленных предприятий, совместно реализующих некоторую программу или цель и действующих на основе определенных процедур и правил, представляет собой актуальную задачу. Достаточно обратиться к примерам формирования крупных Государственных корпораций и частно -государственных предприятий. В них объединяются десятки холдингов с разнородными связями и различными интересами при принципиально иерархической структуре объединения. Возникает проблема координации их производственных, финансовых потоков и трудовых отношений. И эти процедуры формирования механизма управления осуществимы только с привлечением моделей и методов системного анализа и вычислительной техники. Можно выделить следующие основополагающие характеристики систем управления для данного процесса (Емельянов C.B. [1]): динамичность (постоянное развитие), иерархичность управления (многоуровневые системы), многокритериальность (собственные интересы) и информированность (собственная и общая информация, обмен и передача информация, информационные потоки).

Логика развития научных исследований и прикладные запросы привели в настоящее время к тому, что математическое моделирование служит основным инструментом анализа и синтеза механизмов управления. Активное развитие системных подходов к исследованию иерархической структуры управляющих систем было осуществлено в серии работ западных учёных (Месарович М, Мако Д.,Такахара И. [2]) и в информационной теории иерархических систем, развитой в трудах Моисеева H.H. и Гермейера Ю.Б. [3,4]. Формальные соотношения в данных подходах, описывающие объект управления и систему управления, образуют математические модели, в которых учитываются интересы участников и наличие неопределенности при принятии решений. Такие модели в теории принятия решений носят название теоретико-игровых моделей, или игр. Для иерархических систем существенно, что есть Центр управления и отдельные активные подсистемы, преследующие собственные цели. Выбор решений всех участников осуществляется путем формирования стратегий их поведения, как функций многообразных информационных обменов.

Разработка методов информационных обменов представляют собой одну из наиболее существенных задач процесса принятия решений. Их описание появилось уже в первых работах Цермело Э. [5] и Фон Нейман Дж. [6] по теории игр. В этих работах рассматривались игры в позиционной форме. Участники (игроки) делали конечное число ходов, причём каждый ход для данного участника соответствует выбору одной из конечного множества альтернатив. Участники принимали решения, находясь в соответствующих информационных множествах и располагая информацией о предшествующих выборах других участников. Соответственно, множества управлений участников были сугубо конечными, и объемы передаваемой информации тоже были конечны.

На основе позиционных игр путём введения стратегий выбора решений, как функций от наличной информации, были построены игры в нормальной форме, и для них были определены смешанные расширения в работах Фон Неймана Дж. [6] и Бореля Е. [7]. Множества смешанных стратегий уже континуальны, но обмена информацией об этих стратегиях не предполагалось.

В дальнейшем задача была обобщена, и началось исследование игр в нормальной форме с произвольно большими множествами стратегий, преимущественно континуальными, как, например, в выпуклых играх. Но довольно долго информационные обмены в таких моделях не учитывались. Работа Г.Штакельберга (см. Википедия) по анализу игр «лидер-ведомый» не привлекла должного внимания.

И лишь существенно позднее были сформулированы содержательные постановки в рамках информационной теории иерархических систем (Гермейер Ю.Б., Моисеев H.H.) и были предприняты попытки описать обмены информацией с помощью игр в нормальной форме в работах Ховарда Н., Гермейера Ю.Б., Кукушкина Н.С. [8-11]. После этого исследования моделей подобного рода приняли массовый характер (см., например, Ватель И.А., Ерешко Ф.И., Горелик В.А., Кононенко А.Ф., Горелов М.А., Мохонько Е.З., Алиев B.C., Морозов В.В., Федоров В.В., Бурков В.Н., Новиков Д.А. и др. [12-18]). Но во всех этих работах неявно предполагалось, что от игрока к игроку может быть передан любой объем информации, в том числе и бесконечный. Понятно, что в таком случае приходится иметь дело с математической идеализацией, правомерность которой должна быть обоснована. Обычно бесконечность появляется как удобная замена большого конечного числа. И чтобы указанная идеализация была оправданной, нужно, чтобы решения, найденные на моделях с большим конечным объемом информации и на моделях с бесконечным объемом информации были близкими в определенном смысле.

Практика управления реальными системами показывает, что в соответствующих процессах передаются весьма значительные объемы информации, и при современном развитии промышленности они имеют тенденцию к росту. Проблемы соотнесения теоретических результатов принятия решений в условиях различных интересов на иерархических уровнях систем управления и конкретных реализаций имеют место и в теории активных систем (Бурков В.Н., Новиков Д.А. [17,18]).

Первые модели такого рода по оценке объемов передаваемой информации были исследованы в работах Горелова М.А. [19-21] В этих работах в качестве принципа оптимальности рассматривался принцип максимального гарантированного результата. В данной работе [см. 22 и список трудов автора] в качестве оптимальных решений рассматриваются равновесия по Нэшу [23,24].

Цель работы состоит в построении модели принятия решений при ограниченном объеме передаваемой информации, в нахождении структуры оптимальных решений информационных расширений исходной игры, т.е. конструктивных условий равновесия по Нэшу, в разработке эффективных методов поиска равновесий в терминах исходной игры и исследовании асимптотических свойств полученных решений при ограничениях на объём передаваемой информации.

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

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

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

Диссертация состоит из Введения, 4-х глав, заключения и списка литературы.

выполняется при всех 1=2,.,р и всех управлениях м2,г?,.,г/. ЗАКЛЮЧЕНИЕ

В заключение сформулируем основные результаты, полученные в диссертации.

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

2. Введен в рассмотрение новый математический объект: игра двух участников Г#„, как «-мерная аппроксимация исходной игры в нормальной форме, путём включения в стратегии выделенного участника набора из п вопросов ко второму участнику. Показано, что последовательность игр Г#„ имеет естественный предел и описана его структура.

3. Найдены конструктивные описания множеств ситуаций равновесия в оригинально введённых играх двух участников. Установлены условия корректности постановки задач с континуальными стратегиями.

4. Построено обобщение введённого класса игр на случай многих участников при наличии и отсутствии информационного посредника. Приведены конструктивные описания множеств ситуаций равновесия в этих играх.

5. Получены аналитические решения в явном виде для конкретной модели взаимодействия нескольких предприятий, как иллюстрации реализуемости общего подхода.

1. Емельянов C.B. Введение в проблематику научного управления. М.: ЛЕЛАНД, 2011.-64 с.

2. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем, М., Мир, 1973, 344 с.

3. Гермейер Ю.Б., Моисеев Н.Н. О некоторых задачах теории иерархических систем. В кн.: Проблемы прикладной математики и механики, М., Наука, 1971, с. 30-43.

4. Моисеев Н.Н. Иерархические структуры и теория игр, Изв. АН СССР, Техн. кибернетика, 1973, №6, с. 1-11.

5. Цермело Э. О применении теории множеств к теории шахматной игры // Матричные игры. М.: Наука, 1961. С. 167 -172.

6. Фон Нейман Дж. К теории стратегических игр // Матричные игры. М.: Наука, 1961. С. 173-204.

7. Borel Е. La theorie du jeux et les equations integrales a noyau symmetrique // Comptes Rendus de l'Academie des Science. 1921. Vol. 173. P. 1304-1308.

8. Howard N. The theory of meta-games // General systems. 1966. Vol. 11. P. 187-200.

9. Гермейер Ю.Б. Об играх двух лиц с фиксированной последовательность ходов // ДАН. 1971. Т. 198. № 5. С. 1001-1004.

10. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976.

11. Кукушкин Н.С. Точки равновесия в метаиграх // Журн. вычисл. матем. и матем. физ. 1974. Т. 14. № 2. С. 312-320.

12. Ватель И.А., Ерешко Ф.И. Математика конфликта и сотрудничества. М.: Знание. 1973,-64 с.

13. Ерешко Ф.И. Математические модели и методы принятия согласованных решений в активных иерархических системах Диссертация на соискание учёной степени доктора технических наук, ИПУ РАН, 1998, 292 с.

14. Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ конфликтных ситуаций в системах управления. М.: Радио и связь, 1991.

15. Горелов М.А., Кононенко А.Ф. Информационные аспекты принятия решений в условиях конфликта. М.: ВЦ РАН, 1994. 42 с.

16. Кукушкин Н.С. Морозов В.В. Теория неантагонистических игр. М.: МГУ, 1984.

17. Бурков В.Н. Основы теории активных систем. М.: Наука, 1977.

18. Новиков Д.А. Теория управления организационными системами. М.: МПСИ, 2005.-583 с.

19. Горелов М.А. Синтез рациональных процедур обмена информацией в иерархической игре двух лиц // Журн. вычисл. матем. и матем. физ., 2002. Т. 42. №11. С. 1657-1665.

20. Горелов М.А. Теоретико-множественная постановка задачи синтеза рациональных процедур обмена информацией в иерархической игре двух лиц // Журн. вычисл. матем. и матем. физ. 2003. Т. 43. № 3. С.376- 387.

21. Горелов М.А. Максимальный гарантированный результат при ограниченном объеме передаваемой информации // Автоматика и телемеханика. 2011. №3. С.12 -18.

22. Грибов А.Г. Аксиоматика бинарных расширений игр в нормальной форме //Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(3).С. 31-36.

23. Nash J. Non-cooperative games // Annals of Mathematics. 1951. Vol. 54. № 2. P. 286295. (русский перевод: Нэш Дж. Бескоалиционные игры // Матричные игры. М.: Наука, 1961. С.205-221.

24. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984. -496 с.

25. Петров A.A., Поспелов И.Г., Шананин A.A. Опыт математического моделирования экономики. М.: Энергоатомиздат, 1996, 586 с

26. Кононенко А.Ф., Шевченко В.В. Задачи управления производственными корпорациями и операционные игры. М.: ВЦ РАН, 2004. 42 с.

27. Маклейн С. Категории для работающего математика, М.: Физматлит, 2004. 352 с.

28. Голдблатт Р. Топосы. Категорный анализ логики. М.: Мир, 1983. 488 с.

29. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир, 1972. -259 с

30. Эдварде Г. Последняя теорема Ферма. Генетическое введение в алгебраическую теорию чисел. М.: Мир, 1980. 484 с.

31. Публикации автора по теме диссертации

32. Грибов А.Г. О постановках задач в играх с конечным объёмом передаваемой информации. // Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(2). С. 19-24.

33. Горелов М.А., Грибов А.Г. Равновесие в играх с конечным объёмом передаваемой информации. //Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(1).С. 66-77.

34. Грибов А.Г. Аксиоматика бинарных расширений игр в нормальной форме //Труды Института системного анализа РАН, «Динамика неоднородных систем». М.: ИСА РАН, 2010. Т. 53(3).С. 31-36.

35. Горелов М.А., Грибов А.Г. О принятии решений при ограниченном объёме передаваемой информации. // Материалы Пятой международной конференции "Управление развитием крупномасштабных систем". MLSD'2011. ИПУ РАН, 3-5 октября 2011г. Т. 2, С.216-218.

36. Грибов А.Г. Об играх многих лиц с информационным посредником. // Труды Международной научно-практической конференции "Теория активных систем 2011". ИПУ РАН, 14-16 ноября 2011. Т. 2. С. 97-100.

37. Грибов А.Г. Дикусар В.В. Передача конечного объёма информации в играх многих лиц. В серии "Сообщения по прикладной математике", М., ВЦ РАН, 201 I.e. 32