Содержание к диссертации
Общая характеристика работы 5
Введение 11
1 Постановка задачи 19
Постановка задачи 21
Предварительные сведения из теории игр 23
Бескоалиционные игры 23
Кооперативные игры 25
1.3 Предварительные сведения из теории
случайных событий 27
2 Решение задачи 29
2.1 Случайные коалиции событий как псевдоигроки
и игровые модели их поведения 31
Независимое поведение псевдоигроков 32
Совместное поведение псевдоигроков 35
2.2 Случайные коалиции событий как игроки и игровые модели
их поведения 37
2.2.1 Независимое поведение игроков 39
2.2.2 Совместное поведение игроков 48
СОДЕРЖАНИЕ З
2.3 Необходимое и достаточное условие
случайно - коалиционного дележа
по Нейману - Моргенштерну 50
2.3.1 Случайно - множественный подход
к формуле дележа Вилкаса 66
2.3.2 Класс распределений случайных коалиций
событий, управляющий функцией Шепли 67
Проверка условия дележа для класса распределений, управляющих функцией Шепли ... 75
Индекс Банзафа и случайная коалиция,
им управляющая 77
Проверка условия дележа для класса распределений, управляющих индексом Банзафа ... 80
Задача максимизации выигрыша игрока
при классическом дележе 84
2.4 Случайно-множественное значение игры
в играх двух случайных коалиций событий 88
3 Применение полученных результатов 91
3.1 Моделирование товарной политики
на основе трехмерной матрицы БКГ 92
3.2 Эвентологическое игровое моделирование
товарной политики 99
3.2.1 Антагонистическая эвенто логическая модель
поиска товарной политики для фирмы 100
3.2.2 Эвентологическая модель поиска
товарной политики для фирмы
на основе кооперативного поведения игроков
с необязательными соглашениями 102
3.2.3 Эвентологическая модель поиска
товарной политики для фирмы
на основе кооперативного поведения игроков 104
3.2.4 Применение эвентологической игровой модели для фор
мирования товарной политики 104
3.3 Рекомендации по использованию результатов диссертации . 111
Заключение 112
Список использованных источников 114
Список обозначений и предметный указатель 125
Общая характеристика работы
Актуальность темы. Теоретико-игровые методы анализа случайных множеств событий развиваются автором для построения и обобщения математических моделей принятия оптимальных решений в условиях конфликта. Характерной особенностью рассматриваемых систем является то, что они зачастую трудно поддаются формализации. Практический интерес к изучению этой важной задачи обусловлен потенциальными возможностями наиболее полно объяснить структуру зависимостей и взаимодействий случайных событий. В большинстве случаев участники сложных системы играют несколько ролей одновременно, причем данные роли между собой взаимодействуют. На данный момент существует ограниченное количество игровых математических моделей, описывающих игру N лиц, в которой игроки участвуют в конфликте двух сторон, при этом игроки влияют на действия каждого участника конфликта.
В теории игр N лиц основной задачей является задача дележа выигрыша коалиции игроков между ее участниками. Основоположниками теории игр Дж. фон Нейманом и О. Моргенштерном сформулировали определение дележа. В теории коалиционных игр наиболее известны три дележа: функция Шепли, индекс Банзафа и формула Вилкаса, причем первые два являются частным случаем формулы Вилкаса. В самой формуле Вилкаса не ясно из каких условий выбирать распределения для каждого игрока,
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 6
которыми описывается участие каждого игрока в кооперативной игре.
Научная проблема заключается в создании методов построения игровых математических моделей, описывающих игру N лиц, в которой игроки участвуют в конфликте двух сторон. Поскольку рассматривается игра N лиц, то возникает необходимость в том, чтобы полученное решение можно было использовать в задаче дележа. В задаче дележа теории игр необходимо обобщить формулу дележа Вилкаса, с целью устранения произвола в выборе распределений для игроков, которыми описывается участие игроков в кооперативной игре.
Основная идея диссертации состоит в применении теории случайных множеств событий — эвентологии для построения эвентологических теоретико-игровых моделей принятия решений в условиях конфликта и для решения задачи дележа на основе классического определения.
Таким образом, объектом исследования диссертации являются множества случайных событий и их эвентологические распределения, а методы построения зависимостей и взаимодействий случайных событий представляют собой предмет исследования.
Целью работы является развитие теоретико-игровых методов анализа случайных множеств событий, позволяющих решать задачи принятия решений в сложных системах и задачу коалиционного дележа в игре N лиц.
Данная цель достигается решением следующих задач:
разработка теоретико-игровых методов моделирования кооперативного поведения игроков с помощью аппарата теории случайных множеств событий;
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 7
выявление и исследование вида структуры зависимости между игроками в играх двух случайных коалиций событий;
постановка и решение задачи распределения выигрыша случайной коалиции событий между игроками коалиции, на основе классического определения дележа теории игр (дележа по Нейману-Моргенштерну);
разработка алгоритмов построения классов эвентологических распределений, проекции которых на любого игрока совпадают с распределением в функции Шепли, в индексе Банзафа.
Методы исследования основаны на использовании теории вероятности, математической статистики, теории случайных событий и случайных множеств, теории игр, методов оптимизации, системного анализа, управления и обработки информации.
Основные результаты диссертации
Разработаны теоретико-игровые методы кооперативного поведения игроков с применением теории случайных множеств событий: определена игра двух случайных коалиций событий, сформулирована и доказана теорема о существовании равновесия по Нэшу в игре двух случайных коалиций событий, сформулирована и доказана теорема о максимине для игры двух случайных коалиций событий.
Выявлена и исследована двухступенчатая структура зависимостей в играх двух случайных коалиций событий: введено понятие нового объекта в теории игр — псевдоигрока, установлена его связь с обычными с точки зрения теории игр игроками.
Поставлена и решена задача распределения выигрыша случайной ко-
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 8
алиции событий между игроками коалиции, на основе классического определения дележа теории игр: сформулировано и доказано необходимое и достаточное условие случайно - коалиционного дележа по Нейману - Моргенштерну.
4. Предложены и теоретически обоснованы алгоритмы построения классов эвентологических распределений, проекции которых на любого игрока совпадают с распределением в функции Шепли, в индексе Бан-зафа.
Научная новизна.
Предложенные методы построения статистических зависимостей случайных событий основаны на случайно - множественной переформулировке теоремы о существовании равновесия по Нэшу и теоремы о максимине, что позволило упростить процесс построения множественных и количественных зависимостей между случайными событиями.
Обоснованы модели поведения игроков и псевдоигроков в антагонистической игре, в игре с равновесием по Нэшу, в игре с совместным поведением случайных коалиций событий.
Предложен и обоснован новый алгоритм построения класса распределений случайной коалиции событий, для которого выполнено условие дележа, что позволило уточнить формулу Вилкаса, сделать вывод, что индекс Банзафа не является дележом в смысле рассматриваемого определения.
Предложены и обоснованы новые алгоритмы построения классов распределений случайной коалиции событий, проекции которых на любо-
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 9
го игрока совпадают с распределением в функции Шепли, с индексом Банзафа.
Теоретическая значимость. Применение эвентологических методов позволило обобщить ранее известные в теории игр формулы дележа, сформулировать и доказать необходимое и достаточное условие случайно - коалиционного дележа по Нейману - Моргенштерну.
Достоверность полученных результатов. Все результаты работы подтверждены сформулированными и доказанными теоремами.
Личный вклад автора. Все результаты диссертации получены автором самостоятельно.
Практическая значимость. Предложенный в работе аналитический способ нахождения оптимальных, в смысле рассмотренных критериев, двух эвентологических распределений позволяет использовать полученные эвен-тологические распределения для решения задачи дележа.
Результаты работы были применены для формирования товарной политики двух фирм. Полученные в работе результаты используются в учебном процессе Красноярского государственного университета при преподавании следующих дисциплин: «Прикладная эвентология», «Введение в эвентологию», «Экономическая эвентология».
Результаты диссертационной работы могут быть использованы в разнообразных экономических, социальных приложениях, требующих принятия решения в условиях конфликта, а также в задачах распределения ресурсов между элементами системы, которую можно описать с помощью случайного множества событий.
Апробация работы. Основные результаты, отдельные положения, а
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 10
также результаты конкретных прикладных исследований и разработок докладывались и обсуждались на следующих Всероссийских и региональных конференциях и научных семинарах: I, II, III и IV Всероссийская конференция по финансово-актуарной математике и смежным вопросам (Красноярск, 2002, 2003, 2004, 2005); Межрегиональная конференция «Математические модели природы и общества» (Красноярск, 2002); I, II и III Всеси-бирский конгресс женщин - математиков (Красноярск, 2000, 2002 и 2004); Конференция молодых ученых по математике, математическому моделированию и информатике (ИВТ СО РАН, Новосибирск, 2000, 2001); Конференция молодых ученых ИВМ СО РАН (Красноярск, 1999, 2000, 2001, 2002); V ежегодная городская конференция по Финансово-Актуарной Математике (2000); XXXVII Международная Научная Студенческая Конференция (Новосибирск, 1999); ФАМ семинар ИВМ СО РАН (Красноярск, 1998-2006); Семинар кафедры прикладной математики (Красноярск, Крас-ГУ, 1998-2006); Семинар ИВМ СО РАН (2003,2006);
Публикации. По результатам научных исследований опубликовано 12 печатных работ, из которых 1 статья в периодическом издании по перечню ВАК, 1 депонированная статья, 10 работ в трудах всероссийских конференций.
Структура и объем работы. Диссертационная работа состоит из введения, 3 разделов, содержит основной текст на 127 с, 12 иллюстраций, 5 таблиц, список использованных источников из 80 наименований.
Введение к работе
Приводится обзор литературы и работ, имеющих отношение к теме диссертации, в том числе, по теории случайных множеств и теории игр.
Идея создания математической теории конфликтов «носилась» в воздухе с начала XX века. Этот период завершился докладом Джона фон Неймана 7 декабря 1926 года на заседании Геттингенского математического общества. Систематично же теория игр была детально разработана американскими учеными Джоном фон Нейманом и Оскаром Моргенштерном [43] в 1944 году как средство математического подхода к явлениям конкурентной экономики. Теория игр строится как теория математических моделей конфликтов. При этом под конфликтом понимается явление, в котором участвуют различные стороны, наделенные различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. При этом уже в простейших случаях выясняется роль информации, которой располагает игрок о поведении партнеров. Вместе с тем с математической точки зрения абсолютно безразлично, будет ли этот противник реальным субъектом, действующим сознательно и при этом во вред, или же фиктивным, олицетворяющим лишь недостаточную осведомленность игрока о той обстановке, в которой ему приходится принимать свои решения. Таким образом, теорию игр можно рассматривать как математический аппарат, описывающий принятие решений в условиях неопре-
ВВЕДЕНИЕ 12
деленности.
В рамках теории игр поддаются математическому описанию военные и правовые конфликты, спортивные состязания, «салонные»игры, социально - экономические явления, а также явления, связанные с биологической борьбой за существование.
Очевидно, что рассматриваемые в теории игр объекты весьма разнообразны, и пока не удалось установить принципов оптимальности для всех классов игр. Поэтому прежде чем говорить о наивыгоднейшем поведении игрока необходимо уточнить, в каком смысле понимается выгодность. В бескоалиционных играх основным принципом оптимальности считается принцип осуществимости цели, приводящий к ситуациям равновесия, которые характеризуются тем свойством, что любой игрок, отклонившись от ситуации равновесия не увеличит своего выигрыша (при условии, что остальные игроки не изменят своих стратегий). Например, в случае антагонистических игр принципом оптимальности является принцип максимина. Важным результатом в теории антагонистических игр явилось доказательство существования ситуации равновесия в смешанных стратегиях для любой игры двух лиц с нулевой суммой.
Рассматривая игру, в которой больше двух игроков стало очевидным, что игроки могут объединяться друг с другом в коалиции с целью увеличения собственного выигрыша. Таким образом, возникла задача распределения выигрыша коалиции между ее игроками. Сначала Нейманом и Мор-генштерном была введена характеристическая функция, которая каждой коалиции ставила в соответствие вещественное число, причем ее значения получались с помощью фиктивного разыгрывания игр с нулевой суммой
ВВЕДЕНИЕ 13
коалиции против ее дополнения. В связи с проблемой дележа было введено его определение. Отказ от постоянства суммы выигрышей игроков, и тем более обращения ее в нуль, приводит Неймана и Моргенштерна к необходимости расширить ранее построенную теорию. На это пути значение характеристической функции превращается из значения реальной антагонистической игры в значение некоторой фиктивной игры и даже в чисто нормативную характеристику коалиции. Введение характеристической функции игры и определения дележа не дало конструктивного ответа на вопрос: каким образом осуществлять дележ между участниками коалиции?
На решение задачи дележа были направлены усилия многих исследователей, что привело к трем основным результатам, удивительно похожим друг на друга. Имеются в виду поиски значения игры, начатые Шепли, который ввел понятие значение игры [64], называемое теперь функцией Шепли. Шепли вместе с Шубиком [65] первыми начали исследовать распределение сил голосующих законодателей путем вычисления значения игры. Затем Банзаф [3] ввел понятие, получившее большую известность и признание в законодательных кругах США при определении решающего веса каждого законодателя и называемое теперь индексом Банзафа. Наконец, уже в 90-е годы Вилкас [12] подметил общие свойства функции Шепли и индекса Банзафа и предложил более общее понятие вероятностного значения игры, которые естественно назвать вероятностным значением Вил-каса.
Хотелось бы отметить, что все эти формулы имеют прозрачную вероятностную интерпретацию, но при вычислении значения среднего выигрыша
ВВЕДЕНИЕ 14
игрока исследователи смотрели на процесс образования коалиций лишь с точки зрения отдельного игрока и не заметили, что на самом деле процессом управляет случайная коалиция событий, где событие состоит в образовании коалиции и ее дополнения. Кроме того, не был до конца изучен вопрос являются ли полученные формулы дележами в смысле определения Неймана — Моргенштерна.
До сих пор отдельные группы статистических зависимостей между элементами в социально - экономических, экологических, военных и других системах анализировались, и довольно успешно, не только с помощью теории игр, но и методами многомерного статистического анализа, которые, однако, всегда были направлены на моделирование и измерение статистических зависимостей, в основном, между случайными величинами, векторами или функциями.
Вместе с тем, подавляющее большинство событий, которые происходят в природе и обществе, имеют случайный и множественный характер, и поэтому могут быть статистически «измерены» полностью только случайными множествами. Разумеется, что количественные характеристики подобных случайных и множественных событий измерялись, измеряются и будут измеряться случайными величинами, векторами и функциями — иначе говоря, классическими методами многомерного статистического анализа. Но использовать классические количественные методы для анализа случайно - множественной информации — это заведомо обрекать себя на потерю наиболее важной ее части — информации о полной структуре зависимостей случайных событий, как случайных множеств.
Идея использовать результаты современной теории случайных конеч-
ВВЕДЕНИЕ 15
ных абстрактных множеств (СКАМ) для анализа статистических взаимодействий позволяет взглянуть с общих позиций на структуру взаимодействий во всех подобных системах. Это не только открывает путь к построению общей статистической теории таких систем, но и предлагает новые эффективные на практике методы их статистического анализа. Теория СКАМ — это теория случайных элементов со значениями из множества всех подмножеств конечного абстрактного множества. Основная идея современной теории случайных множеств состоит в том, что структура статистических взаимозависимостей подмножеств конечного множества полностью определяется распределением случайного множества, заданного на множестве всех его подмножеств. Распределение случайного множества — это удобный математический аппарат для описания всех мыслимых способов объединения элементов в коалиции, иными словами, всех способов взаимодействия элементов между собой. Хотя теория случайных множеств имеет хорошо прослеживаемые связи с многомерным статистическим анализом, но предмет ее исследований — случайное конечное абстрактное множество — существенно отличается от случайного вектора тем, что принадлежит абстрактным пространствам, не имеющим привычных линейных структур.
Полных аналогов случайно - множественных методов анализа, измерения и генерации структур зависимостей и взаимодействий событий в мировой статистической практике пока не существует. Есть лишь отдельные разрозненные результаты, не объединенные общей теорией. Причина — отсутствие хорошо разработанной теории случайных множеств событий, соединенной с эффективными методами статистических оценок распределений и генерации случайных множеств. Разумеется, следует указать на су-
ВВЕДЕНИЕ 16
ществование общепризнанных мировых центров по исследованию случайных множеств, а также интегральной геометрии, во Франции (Ж. Серра и Ж. Матерон, Фонтебло под Парижем), Аргентине (Л. Сантало, Буэнос-Айрес), Германии (Д. Штойян, Фрайберг в Саксонии), Нидерландах (X. Хейманс, Амстердам), Великобритании (Д. Кендалл, Лондон, И. Молчанов, Глазго), и Австралии (А. Бэддли, Сидней)[15]. Однако, исследования, проводимые во всех этих центрах, тяготеют к математической морфологии — науке, которая изучает форму, в том числе и случайную форму пространственных объектов. Основные объекты в этой области — случайные множества элементов числовой природы — например, случайные подмножества евклидова пространства. Поэтому в анализе таких случайных множеств можно на полную мощность использовать традиционные методы работы с числовыми объектами — классические методы, что и делается повсеместно. Принципиальное отличие методов, предлагаемых в работах по случайным событиям, от методов математической морфологии заключается в том, что они направлены на изучение случайных событий — случайных множеств, состоящих из произвольных абстрактных элементов, не принадлежащих пространствам с привычной линейной или любой другой структурой. Эти так называемые случайные конечные абстрактные множества событий требуют для своего изучения особой теории и специальных методов статистических оценок распределений и генерации, что составляет основное содержание данного направления и отличает его от других исследований по случайным множествам, проводимых в настоящее время в мире.
Развитие теории случайных конечных абстрактных множеств и теории
ВВЕДЕНИЕ 17
случайных событий имело место в последние десятилетия. Первые монографии по случайным конечным абстрактным множествам были опубликованы О.Ю. Воробьевым в 1978 и 1984 годах [15]. Затем в 1993 году вышла его же монография по сет-суммированию [17], посвященная математическому аппарату, который используется в теории случайных множеств и случайных событий. Довольно полное представление о современном состоянии теории случайных множеств и их статистических оценок можно сделать по ряду статей (И.В Баранова, А.О. Воробьев, Е.Е. Голденок, Т.В. Куприянова, Д.В. Семенова, А.Ю. Фомин ), опубликованных в трудах пяти ежегодных городских ФАМ - конференций (1997 - 2001) и в трудах I Всероссийской ФАМ'2002, II Всероссийской ФАМ'2003, III Всероссийской ФАМ'2004 и IV Всероссийской ФАМ'2005 конференциях по финансово -актуарной математике и смежным вопросам.
Теория случайных множеств и случайных событий находит применение в работах по анализу товарных рынков и в портфельном анализе. В работах О.Ю. Воробьева и Е.Е. Голденок [18], [21], были предложены методы построения статистической модели потребительского выбора, опирающейся на разработанные методы моделирования и измерения структур зависимостей и взаимодействий событий в статистических системах, дана математическая интерпретация таких важных экономических понятий как взаимодополняемость и взаимозаменяемость товаров. В работах О.Ю Воробьева и Д.В. Семеновой [57], [56] рассматривалось применение случайно - множественных методов при анализе рыночных систем и позволили дать новую интерпретацию классической задаче Марковица. Идеи, высказанные в этих работах дали новый толчок в применении случайно - множествен-
ВВЕДЕНИЕ 18
ных методов к теории игр и позволили дать случайно - множественную интерпретацию основной теореме теории игр и по-новому взглянуть на коалиционный дележ.
