Равновесие угроз-контругроз и равновесие по Бержу в коалиционной дифференциальной игре при неопределенности тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Максимушкина, Елена Викторовна

• Максимушкина, Елена Викторовна
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Максимушкина, Елена Викторовна

Введение

Глава 1. О-гарантироватшое ра.вновесие угроз-контругроз.

§1.1. Постановка задачи. Определение решения.

§1.2. Свойства решения.

§1.3. Сведение исходной игры к бескоалиционной.

§1.4. Достаточные условия оптимальности.

§1.5. Устойчивость коалиционной структуры.

Глава 2. Гарантированное равновесие

Бержа-Слейтера.

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

§2.2. Определение решения

§2.3. Свойства решения.

§2.4. Сведение к бескоалиционной игре.

§2.5. Достаточные условия существования.

Глава 3. Численное решение дифференциальной игры четырех лиц.

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

§3.2. Бескоалиционная игр а,. З-гарантярованное равновесие угроз-контругроз.

§3.3. G-гаралтированное равновесие угроз-контругроз в игре двух коалиций.

§3.4. Равновесие Бержа-Слейтера в коалиционной игре.«.

§3.5. Итоги эксперимента.

Введение диссертации (часть автореферата) на тему «Равновесие угроз-контругроз и равновесие по Бержу в коалиционной дифференциальной игре при неопределенности»

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

Основы этой теории были заложены в конце 50-х годов ака- * демиком Л. С. Поитряггагым и его учениками [67]. Центральный ее результат - принцип максимума, широко используемый в настоящее время. Еще один подход к решению задач оптимального управления - метод динамического программирования - был разработан американским ученым Р. Беллмалом примерно в то же время [4]. Так, благодаря своей, востребованности, теория оптимального управления стала активно развиваться [2], [6], [7], [22], [в1].

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

Основы теории многокритериальной оптимизации были заложены итальянским экономистом В. З'Гарето.1 Но сразу существенного развития проблема не получила из-за отсутствия математического аппарата для решения подобною рода задач. На первые порах изучались статические задачи [32], [34], [35], [64]. Однако залросы практики вскоре потребовали изучения и динамических систем управления. Это связано с тем, что, как правило, реальные процессы протекают во времени, и соответствующие математические модели содержат системы дифференциальных уравнений (динамические системы). Активное исследоёание динамических многокритериальных задач началось сравнительно недавно, и в настоящее время многокритериальный подход является весьма популярным [8], [22], [37], [56], [71], [78]» Это связано с тем, что качество функционирования любой достаточно сложной системы оценивается, как правило, несколькими показателями.

Основы теории игр были заложены американскими учеными Дж. фон Нейманом и II.O. Монгенштерном, которые в 1944 году опубликовали монографию2, ставшую классической. О современном уровне развития игрового направления можно судить по работам [16], [37], [62], [63], [70], [78]—[80]. Первые этапы развития теории игр были посвящены изучению статических игр, таких, как матричные, биматричные, позиционные, конечные многошаговые, бесконечные, простейшие бескоалиционные и другие [5], [16], [21], [47], [62], [63]. В подобных ситуациях игроки в процессе развития игры, предпринимал какие-либо действия, не могут повлиять на изменение управляемой системы. Но в повседневной жизни чаще встречаются такие конфликтные ситуации, в которых действия из: участников изменяют саму ситуацию. И эти изменения необхо

1 Pareto V. Cours d'Economie Politique. Lausanne, Rouge, 1896. Vl-2. 1897. 426p.

2 Фогт Нейман Дж., Моргснштсрн И.О. Теория игр и экономическое поведение. М.: Наука, 1973. 708с. димо учитьшать при рассмотрении соответствующих математических моделей. Так, синтез теорий игр и оптимального управления привел к становлению теории дифференциальных игр, основной задачей которой стало изучение конфликтных задач управления системами, описываемыми дифференциальными уравнениями [1], [8], [17] [30], [31], [33], [37],.[41], [43], [46], [59], [63], [70].

Развитие общества сопровождается неизбежными конфликтами, которые пронизывают практически все сферы общества. Конфликт (от лат. сопШсЪиБ - столкновение) означает столкновение противоположных интересов, взглядов, серьезное разногласие, спор. При этом конфликтующие стороны действуют, как правило, в условиях воздействия неконтролируемых факторов (или в условиях неопределенности, неполной информации). Неопределенность возникает в социальной жизни (отношения людей и их различного рода объединений, отношения государств), экономике и экологии (неточность прогнозов, измерений, погрешности в начальных данных), механике управляемых систем (помехи, запаздывание в каналах передачи информации, погодные условия). Поэтому и решения принимать приходится с учетом воздействия неконтролируемых факторов. В связи с этим особое значение приобретает бурно развивающееся направление теории принятия решений, которое получило название многокритериальные задачи при неопределенности. .

Зачастую о неопределенностях известны лишь границы изменений, а реализоваться может любая из них. Как принимать решение, учитывая также изменение конфликта с течением времени? Какое оптимальное поведение нужно выбрать конкурентам в таких условиях? Ответы на эти вопросы и составляют содержание теории дифференциальных игр, включающей в себя вопросы переработки и использования информации для принятия решений в условиях неопределенности. В настоящее время решение этих вопросов представляет собой одну из важнейших проблем, и поэтому соответствующие математические задачи исследуются довольно активно [31], [32], [34], [45], [56], [78]-[80].

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

Если в неопределенностях априори известны необходимые статические характеристики, то игра в такой ситуации сводится к обычной дифференциальной игре без неопределенности. В противном случае для .учета влияния неопределенности целесообразно использование принципа, гарантированного результата (ожидание "наихудшей для игроков" ситуации) - минимумов по Слейтеру, Парето, Джоффриону, Ворвейну.

Математическая теория игр является составной частью исследования операций, - науки о принятии решений в условиях конфликта и неопределенности [15], [20], [22], [24], [37], [40]. Она находит широкое применение в различных областях человеческой деятельности, таких, как экономика и менеджмент, промышленность и сельское хозяйство, военное дело и строительство, торговля, и транспорт и т.д. Следуя определению Н.Н.Воробьева, теория игр — это теория математических моделей принятия оптимальных решений в условиях йфпределенности, когда принимающий решение субъект ("игрок") располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится, о множестве решений (стратегий), которые он может принять, и о количественной мере того "выигрыша", который он мог бы получить, выбрав в данной ситуации данную стратегию (Воробьев H.H. Философская энциклопедия. Т.5. М., 1970, с.208-210). Актуальность этой теории заключается в возможности адекватного описания ее средствами сложных управляемых систем и принятия в них оптимальных решений. В частности, моделями теории игр можно содержательно описывать весьма разнообразные явления: экономические, правовые ж классовые конфликты, взаимодействие человека с природой, биологическую борьбу за существование и так далее. В последнее время вопросы, связанные с реальными конфликтами, стали привле^мъ пристальное внимание экономистов, социологов, математиков и представителей других специальностей. Несмотря на определенную ограниченность ма

- «. тематических моделей и трудность проверки адекватности реальности, их исследование все же помогает правильно оценить обстановку и выбрать рекомендации по разрешению конфликта. Математический аппарат исследования дифференциальных игр в основном базируется на идеях и методах теории оптимального управления, динамического программирования, теории игр с непротивоположными интересами и развит в трудах Понтрягина JL С. [67], Беллмана Р. [4], Гермейера Ю. Б. [21], Горелика В. А. [23], Ма-медова М. В., Кононекко А. Ф. [43], [44], Молодцова Д. А. [57]. Кроме того используется аппарат теории оптимизации [13], [14], [18], [39], [58], [65], [66], [68], [72], [74], выпуклого анализа [27], [69], теории матриц [3], [19].

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

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

Число игроков. Будем считать, что в игре участвует не менее двух игроков. Роль игроков могут выполнять руководители промышленных и торговых предприятий., профсоюзы, министерства, руководители государств, командиры кораблей и самолетов и тале далее, то есть те, кто имеет право принимать решения, давать указания к их выполнению. Число игроков обозначим через N, причем это число конечно. Множество всех игроков обозначим через М = {1,.,//}. Основное внимание до сих пор уделялось играм двух-трех, максимум - четырех лиц, в настоящей работе рассматриваются игры, в которых участвует более трех игроков. Таким образом, N > 3 . ^

Управляемая система. Все N игроков оказывают воздействие на управляемую систему £. В экономике это могут быть промышленные предприятия, разного рода объединения, супермаркеты и так далее, в экологии - те же предприятия, очистные сооружения, в механике - группа кораблей, самолетов, "мечтающих", например, о встрече. Математическая модель системы £ может быть описана различным образом. Название "дифференциальные игры" произошло из-за того, что эта модель задается дифференциальным уравнением (в векторном виде), например n х = А{1)х + V В{(г)щ +

1)

Данное уравнение описывает изменение фазового вектора х во времени I под действием управляющих воздействий игроков и неопределенности. Предполагаем, что , матрицы Спхп[0,г?] , •?? > 0, то есть их элементы непрерывны. "Механический и экономический смысл" координат векторов для каждой прикладной задачи различен.

Пару (/,, х) называют позицией игры. Обычно задана начальная, позиция , такая, что для системы (1) где координаты вектора ж* характеризуют состояние системы X е момент начала игры ¿* > 0 . Заканчивается Игра в момент времени > Ц, причем момент д > 0 фиксирован.

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

Стратегии. Ограничимся случаем, когда можно строго очертить множество 1АХ, элементы 1){ которого может в качестве стратегий выбирать г -ый игрок. Элемент III € Ы{ назовем допустимой стратегией г-го игрока.

В теории игр под стратегией понимается правило, по которому каждому состоянию информированности игрока ставится в

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

Стратегии г-го игрока будем отождествлять с функциями х) = (¿¿(1.)х . Тогда множество стратегий г-го игрока (г£М) задается в виде: щ = {и^хф.х) I щ{1,,х) = д,(1)х} а(-) € с»ХЛМ]}'. (з)

Правомочность выбраапю.го вида стратегий обосновывается как "инженерной", та.к и "математической" точкой зрения. ''Инженерная" состоит в том, что управляющее воздействие вида — на систему Е легче реализуется в празстичесзаах задачах, чем разрывное или ж^линейжю (по х). С "математической" точки зрения, такие стратегии позволяют во многих случаях получить явный аналитический вид разыскиваемого решения игры.

Все игроки, получая ту или иную информацию о состоянии системы Е, выбирают каждый свою стратегию (7; € % . Б результате складывается ситуация игры V = из множества ситуаций 1А — Ы\ х . х Кн *

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

Итак, неопределенность , по аналогии со стратегией, будем отождествлять с функцией г(£, ж) = Р(1)х. Тогда множество неопределенностей (помех) имеет вид: • = {2-г *(*,*) | = Р(ф,Р(-) € (4)

Функция выигрыша. В результате воздействия ситуации и и неопределенности Z на систему Б вычисляются значения величин </,-(£/, 2), характеризующие исход игры "с точки зрения" ¿-го игрока; /;(£/, ¿Г) называется функцией выигрыша. Примем, что в интересах каждого игрока выбрать такую свою допустимую стратегию, чтобы добиться большего значения функции выигрыша. Это значение называется выигрышем игрока. В качестве функции выигрыша для промышленного или торгового предприятия могут служить прибыль, различные показателя качества выпускаемого изделия, для механических - расстояния между объектами, стремящимися сблизиться, для экологических - минимизация ущерба окружающей среде.

В общем виде функция выигрыша г-го игрока задается функционалом

1Я (£, х(С)щ [11. (г € М), (5) 4 где называ.ется термипалъиььм, а J Е{й1 ~ интегральным и слагаемым функции выигрыша. Смысл каждого из слагаемых в (5) различен в каждом конкретном случае. В дальнейшем функции выигрыша игроков будем задавать квадратичными функционалами, то есть в (5) n

Fi(t1x) w,, z) = uJ[t]DijUj[t\ + zJ'mLiz\fl (i € N), j=i где матрицы С,-, DliyL{ порядка n x rc постоянны и симметричны. Тогда функция выигрыша г -го игрока примет вид: xT{ti)Cix{-d) +

Партия игры развертывается следующим образом. Каждой из игроков выбирает и использует свою конкретную стратегию Ui-r-u^tyx) из множества (3). В результате складывается ситуация U=(Uiy.,U/v) • Независимо от такого выбора на систему Е действует некоторая неопределенность из (4). Затем строится решение z(t), , системы (1), (2) при «=«(*,£), 2=2(^3;). С помощью этого решения формируются реализации и»ж(£)) выбранных игроками стратегий Ui и реализация неопределенности , действующей на £. Затем вычисляются значения функций выигрыша игроков, ж игра заканчивается.

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

Формализация дифференциальной игры при неопределенности. Под дифференциальной игрой многих лиц при неопределенности понимается упорядоченный набор

М, £, {Ц-К-ем, Z, {Ji(0\ Z> x.)}ieM), (Г) N

DijUjlt] + zT[i]Liz[t] > dt, ieM. (6) j-i где М - множество номеров игроков; изменение управляемой системы £ описывается линейным дифференциальным уравнением (1).,(2); Щ - множество стратегий г -го игрока; X - множество неопределенностей; «/,•(£/, - функция выигрыша г-го игрока.

Под решением игры (7) будем понимать ситуацию (набор стратегий игроков) и*£Ы и векторную гарантию 3* — =(./*,., 3*^) такие, что

1. Ситуация и* отвечает интуитивным представлениям о выгодности, устойчивости и справедливости. Для построения ситуации и* используется о,дин из следующих принципов оптимальности: принцип, гарантированлого результата (принцип максимина), концепции: равновесий по Нашу, Вержу, угроз-контругроз* активных равновесий' Для учета неопределенности широко применяются минимумы по Слейтеру, Парето, Джоффриону, Ворвейну.

- •

2. Соответствующая компонента 3* вектора 3* определяет тот г&рантированный выигрыш, на который игрок может рассчитывать при реализации любой неопределенности Z £ 3, если этот игрок придерживается правила поведения, "диктуемого? его стратегией и* из ситуации V*.

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

Одним из возможных вариантов протекания игры является бескоалиционный, когда каждый игрок при выборе стратегий руководствуется яичной выгодой и не имеет права "общаться" с кем-либо из оставшихся участников игры. Если в игре участвует два игрока, то игра может носить антагонистический характер. В случае же большего количества участников характер игры неантагонистический. Бескоалиционные игры в рамках теории дифференциальных игр являются наиболее изученной областью. В этой связи можно отметить работы Бардина А. В., Вайсмана К. С., Гайдова С. Д., Горелика В. А., Горелова М. А., Житомирского Г. И., Жуковского В. И., Клейменова А. Ф., Кононенко А. Ф., Малафеева О. А., Матвеева В. А., Молодцова Д. А., Молоство-ва В. С., Мухина В. В., Раджефа Е. М.> Салуквадзе М. Е., Смирновой Л. Вм Тынянского Н. Т., Чикрия А. А., Чистякова Ю. В. и других. При этом следует заметить, что большинство работ посвящено равновесию по Нашу, в то время как равновесие угроз-контругроз, равновесие по Бержу остаются мало изученными.

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

Тогда коалиционная структура будет иметь вид К—{Кг, К2} . В настоящей работе рассматриваются коалиции с равным количеством участников. И для удобства обозначений будем считать, что общее количество игроков равно 2 А7 , тогда каждая коалиция будет состоять ровно из N участников. •

Разработке теории коалиционных игр посвящены работы Вайсборда Э. М., Господинова М. Г., Данилова В. И., Жуковского В. И., Зинича В. С., Клейменова А. Ф., Наурузбаева М. С., Салуквадзе М. Е., Сотскова А. И., Стоянова С. В., Субботиной И. В., Суховского Е. С., Тараканова А. Ф. и других. Основное внимание уделялось вопросам образования коалиций [8], [25], [73], [75], [78], их устойчивости [9], [26], [60], [81], существования решений без неопределенности [36], [42], оптимизации стратегий коалиций [38], [76].

В большинстве работ, посвященных коалиционным играм, рассматриваются игры с небольшим количеством участников (максимум - четыре игрока), без неопределенности и с фиксированной коалиционной структурой. Так, в [37] рассматривается коалиционная игра четырех лиц без неопределенности, для которой сформулированы определения угроз-контругроз коалиций, ситуации равновесия угроз-контругроз, ситуации, ¿-оптимальной по Паре-то, приведены условия существования ситуации равновесия угроз и контругроз. В [31] эта же игра двух коалиций рассматривается уже при неопределенности. Для этой задачи также сформулированы определения угроз-контругроз коалиций, ситуации £ — 5 равновесия угроз-контругроз и предложено доказать утверждение о достаточных условиях оптимальности и виде рассматриваемого равновесия. Кроме того, введены понятия угроз-контругроз в игре "на перетягивание" игроков из одной коалиции в другую и на их основе определена устойчивость коалиций и предложено доказать соответствующее достаточное условие устойчивости.

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

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

Поскольку не все конфликты в нашей жизни носят антагонистический характер, и достаточно часто встречаются конфликты с непротивопояожными интересами, то возникает необходимость построения и исследования решения же антагонистической коалиционной игры при неопределенности. Лля этого в настоящей работе предлагается использовать принцип оптимальности, основанный на понятии равновесия по Вержу. В работах Вайсмана К. С., Жуковского В. И. [10] - [12], [31], [37], [82], Гайдова С. Д. [77], Дергачевой Е. И. [28], Жаркынбаева С., Ворибековой К. [29], Кузнецовой В. Е. [48], Салуквадзе М. Е. [33] достаточно подробно рассмотрено это равновесие для бескоалиционных * статических игр", с использованием функции Веллмана сформулированы необходимые и достаточные условия существования гарантированных равновесий по Бержу в линейно-квадратичной дифференциальной игре трех лиц. Выявлена структура таких решений, найден их явный вид. Для не антагонистических коалиционных игр многих лиц при неопределенности такое решение вообще не рассматривалось, что связано с трудностями при определении стратегии, оптимальной как для каждого игрока в отдельности, так и для каждой коалиции в целом, кроме этого необходимо учитывать и влияние неопределенности на ситуацию.

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

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

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

Провести численные эксперименты на ЭВМ. Проблема исследования заключается в определении понятия решения для коалиционных игр многих лиц при неопределенности (из-за необходимости одновременного учета таких факторов, как многокритериально сть, коалиционная структура игры, наличие неопределенности, динамика процесса).

Для реализации поставленной цели потребовалось решить следующие задачи: ввести понятие С--гарактированного равновесия угроз-контругроз для коалшщошшх дифференциальных игр многих лиц при неопределенности; ввести понятие устойчивости коалиционной структуры в ситуации в-гарактированного равновесия угроз-контругроз и установить достаточные условия устойчивости;

• ввести понятие гарантированно го равновесия Бержа-Слейтера для коалиционных дифференциальных игр многих лиц при неопределенности; исследовать основные свойства введенных равновесий; установить связь введенных равновесий с решением специальной бескоалиционной игры трех лиц без неопределенности;

• для линейно-квадратичного варианта игры установить достаточные условия оптимальности указанных решений; найти индивидуальные выигрыши игроков.

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

Научная новизна. Коалиционные диффере^иальные игры многих лиц при неопределенности являются недостаточно изученным разделом теории дифференциальных игр. На основе принципа гарантированного результата в совокупности с равновесием угроз-контругроз и равновесием по Вержу для указанных игр решения не строились. Все основные результаты работы являются новыми.

Практическая значимость. Предложенный математический аппарат позволяет теорию коалиционных дифференциальных игр многих лиц при неопределенности применять к различным прикладным задачам: техническим, экономическим, экологическим и другим. Кроме того, в сведенных к коалиционным играм задачах, несмотря на существенную сложность (необходимость решения систем дифференциальных уравнений типа Риккати), может быть получен численный ответ. Для преодоления указанного затруднения автором использовалась среда MathC&d 7.0 Pro, позволяющая решать разнообразные дифференциальные уравнения и их системы. „.,.'. На защиту выносятся: о понятие коалиционного С-гарантировашюго равновесия угроз-контругроз для коалиционной игры многих лиц при неопределенности и его основные свойства; понятие устойчивости коалиционной структуры в ситуации О-гарантировэнного равновесия угроз-коятругр оз; понятие коалиционного гарантированного равновесия Бержа-Слейтера для коалиционной игры многих лиц при неопределенности и его основные свойства; достаточные условия оптимальности коалиционного О-га-рантироваштого равновесия угроз-контругроз для линейно-квадратичного варианта, игры;

• достаточные условия устойчивости, коалиционной структуры в ситуации С-га.р актированного равновесия угроз-контругроз; достаточные условия существ ов ания коалиционного гарантированного равновесия Бержа-Слейтера для линейно-квадратичного варианта игры;

Апробация. Результаты докладывались на научных семинарах СГУ им. Н.Г. Чернышевского, РосЗИТЛП, международной конференции "Естествознание на рубеже столетий1'(Дагомыс, 2001), V Всероссийской научно-практической конференции "Современные технологии в машиностроении" (ГГенза, 2002), научно-методических семинарах кафедры информатики, кафедры математического анализа, на аспирантском объединении Балашовского филиала СГУ. Кроме того, результаты исследования апробированы при численном решении задач, что отражено в настоящей работе.

Структура работы. Диссертация содержит три главы, заключение и приложение.

Первая глава (§§1.1-1.4) посвящена исследованию коалиционных дифференциальных игр многих лиц при неопределенности и построению коалиционного И -гарантированного равновесия угроз-контругроз. В §1.1 рассматривается постановка задачи, определяются такие понятия, как угроза и контругроза коалиции, на их основе формализуется понятие коалиционного О-гарантироваиыого равновесия угроз-контругроз. В §1.2 исследуются основные свойства введенного равновесия: динамическая устойчивость, "гарантироваш-юсть" суммарного выигрыша коалиции. Установлено, что выполнение внутри любой коалиции условия коллективной рациональности является достаточным для того, чтобы соответствующая • ;.••»>а решений была максимальна по Джоффриону. Далее (§1.3) исходной игре ставится в соответствие специальная бескоалиционная игра трех лиц без ие-определенности, определяется равновесная по Нэшу ситуация новой игры и устанавливается ее связь с решением исходной игры. В §1.4 доказываются теоремы о достаточных условиях оптимальности введенного равновесия, позволяющие отыскать индивидуальные выигрыши игроков. §1.5 посвящен исследованию устойчивости коалиционной структуры в ситуации (^-гарантированного равновесия угроз-контругроз и установлению достаточных условий устойчивости.

Вторая глава (§§2.1-2.5) посвящена исследованию коалиционных дифференциальных игр многих лиц при неопределенности и построению коалиционного гарантированного равновесия Бер-жа-Слейтера. В §2.1 рассматривается постановка задачи. В §2.2 формализуется понятие коалиционного гарантированного равновесия Бержа-Слейтера, рассматриваются особенности введенного определения, доказывается теорема о классе игр, в которых отсутствуют максимивы. В §2.3 исследуются основные свойства введенного равновесия: динамическая устойчивость, "гарад-тиров аивость" суммарного выигрыша коалиции. Доказывается, что выполнение внутри любой коалиции условия коллективной рациональности является достаточным, для того, чтобы соответствующая пара решений была, максимальна по Джоффриону. В §2.4 рассмотрена специальная бескоалиционная игра трех лиц без неопределенности, которая ставится в соответствие исходной. Для введенной специальной игры определяется понятие разновесной ситуации и устанавливается связь между указанной ситуацией и коалиционным гар антир о в ат гпъгм равновесяем^Вержа-Слейтера исходной игры. В §2.5 доказываются теоремы о достаточных условиях оптимальности, позволяющие отыскать индивидуальные выигрыши игроков.

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

Третья глава (§§3.1-3.5) посвящена рассмотрению конкретной дифференциальной игры при неопределенности и ее численному решению. Чтобы не усложнять вычисления, рассматривается игра четырех лиц. В §3.1 приводится общая постановка задачи. В §3.2 для указанной задачи в случае бескоалиционной игры строится Б-гарантированное равновесие угроз-контругроз, определяется суммарный выигрыш игроков, при помощи некоторого изменения оптимальной стратегии одного из игроков показывается, что построенное равновесие действительно оптимально, определяются индивидуальные выигрыши каждого из участников игры. В §§3.3

23 ~ - <9

3.4 в рамках сформулированной задачи рассматривается коалиционная игра с фиксированной коалиционной структурой. В §3.3 для коалиционной игры строится коалиционное О-гарантированное равновесие угроз-контругроз. В §3.4 — коалиционное гарантированное равновесие Вержа-Слейтера. Как и в случае бескоалиционной игры, здесь путем изменения стратегии одного из игроков показывается оптимальность построенных равновесий. В обоих случаях определяются суммарные выигрыши- коалиций и индивидуальные выигрыши игроков. В §3.5 по результатам проведенных вычислений формулируются выводы.

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

Основные результаты диссертацио>шого исследования опубликованы в работах [49]-[55].

Несколько слов о системе обозначений и нумерации. Диссертация состоит из трех глав, разбитых на параграфы. Каждый параграф имеет двойную нумерацию: первая цифра означает номер главы, вторая - номер параграфа внутри данной главы. Утверждения, формулы и рисунки имеют тройную нумерацию: первая цифра означает номер главы, вторая - номер параграфа, в которых находится формула, рисунок или утверждений, а третья цифра -это номер указанного элемента внутри данного параграфа.

Заключение диссертации по теме «Теоретические основы информатики», Максимушкина, Елена Викторовна

ЗАКЛЮЧЕНИЕ ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

2. Сформулировано определение устойчивости коалиционной структуры в ситуации коалиционного С -гарантированного равновесия, установлены достаточные условий«устойчивости.

3. Для коалиционной игры многих лиц при неопределенности на основе равновесия Бержа и. минимума по Сяейтеру сформулировано определение коалиционного гарантированного равновесия' Бержа- С л ейтер а, установлены свойства введенного равновесия.

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

5. Получены достаточные условия существования коалиционного гарантированного равновесия Б ер жа-С л ейтера коалиционной игры при неопределенности.

Список литературы диссертационного исследования кандидат физико-математических наук Максимушкина, Елена Викторовна, 2002 год

1. Айзеке Р. Дифференциальные игры,- М.: Мир, 1967.- 479с.

2. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление.- М.: Наука, "1979.- 432с.

3. Беллман Р. Введение в теорию матриц.- М.: Наука, 1969.-367с.

4. Беллман Р. Динамическое программирование.- М.: ИЛ, 1960.- 400с.

5. Бесконечные антагонистические игры / Под ред. Воробьева Н. Н.- М.: Физматгиз, 1963.- 503с.

6. Болтянский В. Г. Математические методы оптимального управления.- М.: Наука, 1969,- 408с.

7. Болтянский В. Г. Оптимальное управление дискретными системами.- М.: Наука. Главная редакция физико-математической литературы, 1973,- 448с,

8. Вайсборд Э. М., Жуковский В. И. Введение в дифференциальные игры нескольких лиц и их приложения.- М.: Советское радио, 1980.- 304с.

9. Вайсборд Э. М., /Куков с кий В. й- О существовании решения в коалиционной дифферешдиальяой лгре // Систем, анализ, моделирование и оптимиз. прикл. задач: Сб. пауч. тр.- М., 1990.- С.31-34.

10. Вайсман К. С. Равновесие по Бержу в одной дифференциаль^ной игре // Сложные динамические системы: Сб. науч. тр.-Псков: Псковский пед. ии-т, 1994.- С.59-63.

11. Вайсман К. С., Жуковский В. И Свойства равновесия по Бер-жу // Математические проблемы экологии: Тез. докл.- Чита, 1994.- С.27-28.

12. Вайсмав К. С., Жуковский В. И. Структура равновесных по Бержу решений // Потггрягинскке чтения V: Тез. докл.-Воронеж, 1994.- С.29.

13. Васильев Ф. П. Численные методы решения экстремальных задач.- М.: Наука, 1980.- 520с.

14. Васильев Ф. П. Методы решения экстремальных задач.- М.: Наука, 1981 400с.

15. Вестник Псковского Вольного университета. "Математика и информатика".- Специальное приложение к журналу, 1997, Выпуск 1.- 177с.

16. Воробьев Н. Н. Основы теории игр. Вескоалюдаонные игры.-М.: Наука, 1984.- 945с.

17. Воробьев И. Н. Теория игр для экономистов-кибернетиков.-М.: Наука, 1985.- 271с. '

18. Галиев Э. М., Тихомиров В. М. Краткий курс теории экстремальных задач.- М.: Изд-во Моск. ун-та, 1989.- 204с.

19. Гантмахер Ф. Р. Теория матриц.- М.: Государственное издательство технико-теоретической литературы, 1953.- 492с.

20. Гермейер Ю. Б. Введение в исследование операций.- М.: Наука, 1971.- 384с.

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

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

23. Горелик В. А. Принцип гарантированного результата в не антагонистических играх двух лиц с обменом информацией // Исследование операций. М.: ВЦ АН СССР ~ 1971.- Вып/2-С.102-108.

24. Горелик В. А., Ушаков И. А., Исследование операций.- М.: М ашиностр оен и:е, 19 8 б. 2 8 8 с.

25. Господинов М. Г. Один способ образования коалиций в дифференциальных играх с запаздываниям // Тр. III конф. по дифференциальным уравнениям и их применениям, 30 июня -6 июля, 1985.- Русе /НРБ/,- 1987. С.87-90.;

26. Данилов В. И., Сотсков А. И. Коалициошго-устойчжвые механизмы группового выбора. // Экон. и мат. методы.- 1988.-Т.25, N 1.- С.1.13-124.

27. Демидович Б. ТТ., Марон И. А., Шувалова Э. 3. Численные методы анализа,. Приближение функций, дифференциальные и интегральные уравнения/ Под ред. Демидовича Б. П.- М.: Наука. Главная редакция физико-математической литературы, 1987.- 368с.

28. Дергачева. Е. И. Равновесие по Бержу в дифференциальных играх // Многокритериальные системы при неопределенности и их приложения: Сб. науч. тр.- "Челябинск, 1988.- С.61-87.

29. Жаркьшбаев С,, Борибекова К. Линейно-квадратичная игра Бержа, // Систем, анализ., моделир. и олтимиз. прикл. задач: Сб. науч. тр.- М., 1990.- С.27-30.

30. Жаутыков О. А., .Жуковский В. И., Жаркьшбаев С. Дифференциальпые игры нескольких лиц (с запаздыванием времени).- Алма-Ата: Наука,5 1988.- 319с.

31. Жуковский В. И. Введение в дифференциальные игры при неопределенности.-- М., 1997,- 461с.

32. Жуковский В. И., Молоствов В. С. Многокритериальное принятие решений в условиях неопределенности.- М.: МНИИПУ, 1988. "130с.

33. Жуковский В. И., Салуквадзе М. В. Игровые линейно-квадратичные задачи / -Препринт.- Тбилиси: Ин-т Систем Управления АН Грузии, 1992. 64с.

34. Жуковский В. И., Салуквадзе М, Е. Многокритериальные задачи. в условиях неопределенности.- Тбилиси: МЕПНИЕРЕ-ВА, 1991.- 129с.

35. Жуковский В. И., Салуквадзе М. В. Оптимизация гарантий в многокритериа л ьпых задачах управления.- Тбилиси, 1996.-480с.

36. Жуковский 13. И., СухокскаЙ Е. С. Некоторые задачи коалиционных дифференциалып.тх игр // Тез. докл. VII Всес. кокф. по проблемам теоретической кибернетики. Ч.П.- Иркутск: Иркутский ун-т, 1985. С.51-52.

37. Жуковский В. И., Читсрий А. А. Л*шейпо-квадратичные дифференциальные игры.- Киев: Наухова думка, 1994.- 320с.

38. Зинич В. С., Субботина. И. В. Охтшизация стратегий двух коалиций в условиях конфликтной ситуации // Вопросы кибернетики.-- М. 1.992.- N168.- С. 107-128.

39. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач.-М.: Наука. Главная "к1;.-акция физико-математической литературы, 1974.- 480с.

40. Карлин С. Математические методы в теории, игр, программировании и экономике.- М.: Мир, 1964.- 838с.

41. Клейменов А. Ф. Неаитаголистические позиционные .дифференциальные игры.- Екатеринбург: Наука, 1993.- 185с.

42. Клейменов А. Ф. Равновесные коалиционные контр стратегии в дифференциальных играх // Прикл. математика и механика.-1982.- Т.46, /VS.- С.714-721.

43. Кононеико А. Ф., Мамедов М. Б- JIинейно-квадраткчные дифференциальные игр ы с и е пр оти в он о ложными интересами./ Problems of Control and Information Theory, 1980, Vol.9 (4),- PP.297312.

44. Кононенко А. Ф. О равновесных позиционных стратегиях в неантагонистических дифферешщальных играх // Локл. АН СССР.- 1976. Т.231, N 2- С.285-288.

45. Кононенко А. Ф., Халезов А. Д., Чумаков В. В. Принятие решений в условиях неопределенности./ Под ред. Л. Г. Гурина.-М.: Вычислительный центр АН СССР, 1991.- 198с.

46. Красовский PI. PL, Субботин А. И. Позиционные дифференциальные игры.- М.: Наука, 1974.-- 455с.

47. Крушевсжий А. В. Теория игр,- РСиев: Изд. объединение "Би-ща школа", 1977.- 216с.

48. Кузнецова В. Е. Об условии, равновесия по Вержу // Сложные динамические системы: Сб. науч. тр.- Псков: Псковский нед. ин-т, 1994.- С.77 78.

49. Максимупнаша Е. В, Возможная модель управления комплексом предприятий // Сов решенные технологии в машиностроении: Сборник материалов V Всеросийской научно-практической конференции. Ч. II.- Пенза, 2002.- С.68-71.

50. Максимухпкина Е. В. .Ива возможных решения одной коалиционной игры // Мате риалы международной конференции '"Естествознание на рубеже столетий''. 8-10 октября 2001г. Т.1. Технические науки.-Дагомыс, 2001 С.46-47.

51. Максимувпсина Е. В. .Два равновесия в коалиционной диф■ /ферешщальиой игре многих лиц при неопределенности //

52. Материалы ежегодной научно-практической конференции молодых ученых (13-20 апреля 2000г.)/ Под общ. ред. A.B. Шатиловой.- Балашов: Изд-во БГПИ, 2000 С.55-59.

53. М.аксиму шкина Ё. В. Дифференциальная игра двух коалиций при неопределенности // Образование на пороге нового тысячелетия: Сборник научных статей. Ч.1.- Балашов: Изд-хю БГПИ, 1999.- С.49-50.

54. Максимушкина. Е. В. • Равновесие Бержа-Слейтера в дифференциальной игре двух коалиций у/ри неопределенности // Международный академический журнал.-1999.- iV 2.-С.15-23.

55. Максимушкина Е. В. S-гараптировянное равновесие; угроз и контругроз в коалиционной диффере:-.щиалъной игре в условиях неопределенности // Междувл.родиый академический журнал.- 2000.- JV 1.- С.3-11.

56. Многокритериальные дашамичесхсие задачи при неопределенности/ Сборник научных трудов.- Орехово-Зуево, 1991.-138с.

57. Молодцов Л. А. О решении одного класса, неантагопистг^зе-ских игр // Журнал вычислительно.!.! математики и вычислительной физики.- 1976.- Т. 16, N 6.- 0.1451-1456.

58. Мухачева Э. А., Ругш:в:^те№/ Г". П1. Математическоепрограммирование.- Новосибирск: 'Я аук&> 1977.- 320с.

59. Мухтаров У. M,, Чистяков Ю. Б. О решении некоторых классов дифференциальных игр.- М.: Вычислительный центр АН СССР, 1985.- 38с.

60. Наурузбаев М. С. Устойчивые коалиции в кооперативных играх // Сб. науч. тр./ ВНИИ системных исследозанжй.-1987.- N 5.- С. 13-17.

61. Ногин В. Л., Протодьяконов И. О., Евлампиев И. И. Основы теории оптимизации: Учеб. пособие для студентов втузов/ Под ред. И. О. Протодьяконов а. М.: Высш. шк., 1986.-384с.

62. Оуэн Г. Теория игр.- М.: Мир, 1971.-- 230с.

63. Петросян Л. А. ж др. Теория игр: Учеб. пособие для ун-тоз / JI. А. Петросян, Н. А. Зенкевич, Е. Â. Оемийа- М,: Высш.шк., Книжный дом "Университет**, 1998.- 304с.

64. Подиновский В. В., Ногин В. Д. Парето-оптимальные реле-ют многокритериальных задач.- М.: Наука, 1982 256с.

65. Полак Э. Численные методы оптшлЕзадки. Единый подход. -М.: Мир, 1974.- 376с.

66. Поляк Б. Т. Введение в оптимизацию.- М.: Наука. Главная редакция физико-математической литературы, 1983.- 384с.

67. Понтрягин Л. С. и др. Математическая теория оптимальных процессов./ Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкре-лидзе, Е. Ф. Мшценко.- М.: Наука. Главная редакция физтсо-математической литературы, 1969 384с.

68. Пшеничный В. Н., Данилин Ю. М. Численные методы в экстремальных задачах.- М.: Наука, 1975.- 320с.

69. Пшеничный Б. Н. Выпуклый анализ я экстремальные зада.чи.-М.: Наука. Главная редакция физико-математической литературы, 1980.- 320с.

70. Пшеничный Б. Н., Остапенко В. В. Дифференциальные игры.-Киев: Наукова думка, 1992.- 260с.

71. Салуквадзе М. Е., Смирнова Л. В. Принцип пессимизма-оптимизма в многокритериальных задачах / Препринт.- Тбилиси,1995.- 16с.

72. Спирин А. А., Фомин Г. П. Экономико-математические методы и модели в торговле: Учеб. пособие для экон. и товаровед, фак. торг. вузов М.: Экономика,, 1988.- 149с.

73. Стоянов Н. В. Один способ образования коалиций в дифференциальных играх // Мат. и Мат. образ.: Докл. 19-й пролет, конф. Съюза мат. Вългария, Слънчев бряг, 6-9 апр. 1990.-София, 1990.- С.404-407.

74. Сухарев А. Г., Тимохов А. В., Федоров -В. В. Курс, методов оптимизации.- М.: Наука. Главная редакция физико-математической литературы, 1986.- 328с.

75. Суховский Е. С. К устойчивости коалиционной структуры в одной дифференциальной игре // Многокритериальные системы при неопределенности и их приложения: Межвуз. сб. науч. тр.- Челябинск, 1988.- С.54-58.

76. Тараканов А. Ф. Достаточные условия оптимальности в дифференциальной игре двух коалиций при неопределенности // Международный академический журнал-1999.- N 2.-С.З-14.

77. Gaidov S. D. Beige-equilibrium in stochastic differential games // Math. Balkanika, N.S. 1987.- V.l, N1.- PP.25-32.

78. Multiple criteria problems under uncertainty: Abstracts./ The Third International Workshop.- Grekhovo-Zuevo. Russia. 4994- 110р.

79. Multiple criteria and game problems under uncertainty (abstracts)/ The Fourth Internationa! Workshop (8-14 September, 1996).- Moscow,1996.- 186p.1 ** V A .A I

80. Topchishvili A. L., Maisuradze V. G., Saiakvadze M. E. Connection of multicriteria pioblems under uncertainties and antagonistic games with, vector-valued payoff functions / Preprint. Tbilisi, 1996- 26p.

81. Zhukovskiy V. L À stability of coalition structure in a diggerential three-person game // Proc. 3rd Coni Differential Equations and AppL, Rousse, June 30-July 6, 1985. Vol. 2.- Rcusee, 1986.- PP.951-953.

82. Zhukovskiy V. I., Sahikvadze M. E., Vaisman'K. S. The Berge equili- «.brium / Preprint.- Tbilisi, 1994.- 32p.