Моренець Володимир Ігорович Ігрові задачі з нечіткою множиною агентів

Краткое описание

Моренець Володимир Ігорович, тимчасово не працює: «Ігрові задачі з нечіткою множиною агентів» (01.05.04 - системний аналіз і теорія оптимальних рішень). Спецрада Д 26.001.35 у Київському національному університеті імені Тараса Шевченка

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Рукопис
МОРЕНЕЦЬ ВОЛОДИМИР ІГОРОВИЧ
УДК 519.8

ДИСЕРТАЦІЯ
ІГРОВІ ЗАДАЧІ З НЕЧІТКОЮ МНОЖИНОЮ АГЕНТІВ
01.05.04 – системний аналіз і теорія оптимальних рішень
Подається на здобуття наукового ступеня кандидата фізико-математичних наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело
___________________________
(підпис, ініціали та прізвище здобувача)
Науковий керівник Мащенко Сергій Олегович, доктор фізикоматематичних наук, професор

Київ - 2017

ЗМІСТ
ВСТУП………………………………………………………………………. 14
РОЗДІЛ 1. Огляд літератури з теорії ігор в умовах нечіткої
інформації. Допоміжні результати……………………………………….. 19
1.1. Основні принципи оптимальності в некооперативних іграх в умовах
нечіткою інформації…………………………………………………………. 19
1.1.1. Ігри з нечітко заданими цілями гравців.…………………….. 19
1.1.2. Ігри з нечіткими множинами стратегій………………………. 20
1.1.3. Ігри з нечітко заданими функціями виграшу гравців……….. 21
1.2. Основні підходи до розв’язання кооперативних ігор в умовах
нечіткої інформації………………………………………………………….. 22
1.2.1. Ігри з нечіткою характеристичною функцією……………… 22
1.2.2. Ігри з нечіткими коаліціями…………………………………... 23
1.3. Основні підходи до ігор з обмеженою кооперацією…………………. 26
1.4. Допоміжні результати з теорії нечітких множин…………………….. 28
1.4.1. Нечіткі множини типу 2……………………………………... 28
1.4.2. Перетин нечіткої множини чітких множин………………….. 32
1.5. Висновки до розділу 1………………………………………………….. 35
РОЗДІЛ 2. Оптимізація функцій на нечітких множинах типу-2…….. 36
2.1. Задача максимізації функції на нечіткій множині типу-2…………… 37
2.1.1. Постановка задачі…………………………………………….. 37
2.1.2. Декомпозиція на множини рівня……………………………... 38
2.1.3. Побудова розв’язку задачі оптимізації на НМТ-2………….... 40
2.2. Оптимізація на НМТ-2 з ефективними ступенями допустимості та
недопустимості………………………………………………………………. 47
2.2.1. Концепція розв’язку………………………………………….. 47
2.2.2. Побудова розв’язку задачі оптимізації на НМТ-2 з
бульовими ступенями належності ………………………………………… 51
12
2.2.3. Множина ефективних нечітких розв’язків НМТ-2………….. 54
2.3. Висновки до розділу 2………………………………………………….. 57
РОЗДІЛ 3. Некооперативні ігри з нечіткою множиною гравців…….. 58
3.1. Рівновага за Нешем в некооперативній грі з нечіткою множиною
гравців………………………………………………………………………... 59
3.1.1. Множина ефективних нечітких рівноваг за Нешем…………. 61
3.1.2. Вибір ефективних рівноваг……………………………………. 64
3.1.3. Алгоритм знаходження ефективних рівноваг за Нешем…… 66
3.1.4. Множини рівнів НМТ-2 ефективних нечітких рівноваг за
Нешем………………………………………………………………………... 67
3.2. Альтруїстична рівновага за Бержем з нечіткою множиною гравців... 72
3.2.1. Множина ефективних нечітких альтруїстичних рівноваг за
Бержем……………………………………………………………………….. 74
3.2.2. Вибір ефективних альтруїстичних рівноваг…………………. 77
3.2.3. Алгоритм знаходження ефективних альтруїстичних
рівноваг за Бержем………………………………………………………….. 80
3.2.4. Множини рівнів НМТ-2 ефективних нечітких
альтруїстичних рівноваг за Бержем………………………………………... 80
3.3. Рівновага за Бержем з нечіткою множиною гравців, які
«співчувають»………………………………………………………………... 86
3.3.1. Рівновага за Бержем в іграх з нечіткими коаліціями гравців,
які не «співчувають»………………………………………………………… 87
3.3.2. Нечітка множина сприятливих ситуацій……………………... 88
3.3.3. Максимально допустимі рівноваги за Бержем……………… 90
3.3.4. Максимально допустимі рівноваги за Бержем із заданим
рівнем ступеня неналежності………………………………………………. 97
3.4. Висновки до розділу 2………………………………………………….. 111
РОЗДІЛ 4. Кооперативні ігри з нечіткою множиною допустимих
коаліцій……………………………………………………………………… 113
13
4.1. C-ядро кооперативної гри з нечіткою множиною допустимих
коаліцій……………………………………………………………………… 114
4.1.1. Узагальнення поняття C-ядра………………………………… 115
4.1.2. «Найкращий» розв’язок з C-ядра…………………………….. 119
4.1.3. Алгоритм знаходження часткового найкращого розв’язку з
C-ядра гри з нечіткою множиною допустимих коаліцій…………………. 123
4.2. Вектор Шеплі кооперативної гри з нечіткою множиною допустимих
коаліцій………………………………………………………………………. 127
4.2.1. Вектор Шеплі в іграх з обмеженою кооперацією…………… 129
4.2.2. Побудова часткових значень вектору Шеплі………………... 131
4.2.3. Алгоритм знаходження часткових значень вектору Шеплі.. 137
4.3. Висновки до розділу 4………………………………………………….. 143
ВИСНОВКИ………………………………………………………………… 144
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ………………………………... 146
ДОДАТОК А. Наукові опубліковані праці……………………………….. 158
ДОДАТОК Б. Акт впровадження…………………………………………. 161
14
ВСТУП
Актуальність теми. Теорія ігор – це наука про оптимальні стратегії в
конфліктних ситуаціях. У більшості випадків методи теорій ігор
використовуються в економіці, соціальних науках, наприклад у психології,
політології, соціології. Ще із 70-х років XX століття теорія ігор почала
використовуватися також у біології для вивчення поведінки тварин. На
сьогоднішній день, теорія ігор має велике значення в галузі кібернетики та
штучного інтелекту.
Поняття оптимальних стратегій в області математичного моделювання
були запропоновані вченими ще у XVIII столітті. У XIX столітті проблеми
ціноутворення та виробництва в ринкових умовах із малою конкуренцією
стали класичними прикладами теорії ігор. В першу чергу тут слід відмітити
роботи Ж. Бертрана та А. Курно. А на початку XX століття відомими
математиками Е. Борелем та Е. Цермело була запропонована ідея математичної
теорії, яка б вивчала конфлікти інтересів. Витоки математичної теорії ігор були
покладені у роботі О. Моргенштерна та Дж. фон Неймана «Теорія ігор та
економічна поведінка» у 1944 році. Окремо слід виділити лауреата
Нобелівської премії з економіки 1994 р. Джона Неша. У перших концепціях
теорії ігор розглядалися в основному ігри антагоністичного типу, де одні
гравці, отримували виграші за рахунок інших, які програвали. Дж. Нешем були
розроблені методи аналізу ігор з непротилежними цілями гравців. Завдяки цим
дослідженням теорія ігор отримала значний поштовх у своєму розвитку.
За останні тридцять років Нобелевськими лауреатами з економіки за
досягнення в галузі теорії ігор стали J. Nash, R. Selten, J. Harsanyi, R. Aumann,
T. Schelling, A. Roth, L. Shapley. Значний внесок у розвиток теорії ігор зробили
К. Berge, Е. Mulen, J. Neumann, O. Morgenstern, Н. Воробйов, Ю. Гермейєр, М.
Красовський, Б. Пшеничний, А. Чикрій.
В деяких конфліктних ситуаціях гравці можуть об'єднуватися в групи
(коаліції). Це вони роблять для збільшення спільної вигоди, яку вони
15
розподіляють між собою в залежності від вкладів кожного. Для опису таких
ситуацій застосовується теорія кооперативних ігор, яка полягаю у вивченні
питання «справедливого» розподілу сукупного виграшу між гравцями у
випадку їхньої співпраці. Цим кооперативні ігри відрізняються від
некооперативних, в яких кожен гравець грає лише сам за себе. В класичних
кооперативних іграх припускається, що будь-яка коаліція гравців є
допустимою. В реальному житті це не завжди так. Тому дослідження
кооперативних ігор з обмеженою кооперацією є безумовно актуальним.
Оскільки у реальних, наближених до життя ситуаціях, гравцям або
коаліціям гравців іноді буває досить важко чітко визначити свої стратегії,
постає питання нечіткості в іграх. Для розгляду ігор такого класу доцільно
використовувати підходи теорії нечітких множин. Математичний апарат теорії
нечітких множин, запропонований Л. Заде і розвинений протягом останніх
десятиріч, зокрема завдяки дослідженням D. Dubois, N. Karnik, M. Mizumoto, J.
Mendel, H. Tanaka, R. Yager H. Zimmermann R. Bellman, С. А. Орловського,
Ю. П. Зайченко та інших, істотно полегшує формалізацію задач і дозволяє
успішно розв’язувати складні задачі прийняття рішень в умовах
невизначеності, нечіткості й суб’єктивності оцінок.
У дисертаційній роботі розв’язуються задачі теорії як некооперативних,
так і кооперативних ігор із нечіткими множинами агентів (гравців, коаліцій
гравців).
Зв'язок роботи з науковими програмами, планами, темами.
Дисертаційна робота є складовою частиною наукових робіт, які виконуються на
кафедрі системного аналізу та теорії прийняття рішень та в науково-дослідному
підрозділі Київського національного університету імені Тараса Шевченка.
Дослідження виконувалися в рамках науково-дослідної теми №16БФ015-02
“Розробка нових математичних методів системного аналізу і теорії
оптимальних рішень та їх застосування” (державний номер реєстрації
0116U002529, термін виконання 2016-2018 р.р.).
16
Мета і задачі дослідження. Метою дисертаційної роботи є розробка
методів розв’язання ігрових задач із нечіткими множинами гравців та їхніх
коаліцій, що спрямовані на вирішення наукових проблем теорії ігор в умовах
нечіткої інформації.
Для досягнення поставленої мети в роботі розв’язуються наступні задачі:
- дослідити задачу «максимізації» функцій на нечіткій множині типу-2 та
розробити концептуальну модель вибору «допустимих» альтернатив;
- розробити основні принципи оптимальності у некооперативних іграх із
нечіткою множиною гравців;
- розробити методи розв’язання кооперативних ігор з нечіткою множиною
допустимих коаліцій.
Об’єктом дослідження є ігри із нечіткими множинами агентів, які можуть
бути представлені в некооперативних іграх нечіткими множинами гравців, а в
кооперативних іграх –– нечіткими множинами допустимих коаліцій.
Предметом дослідження є методи розв’язання ігрових задач із нечіткими
множинами гравців та нечіткими множинами допустимих коаліцій.
Методи дослідження. Теоретичною основою дисертаційного дослідження
є класичні теоретичні роботи провідних вчених з теорії ігор та теорії нечітких
множин.
Методологічну основу дисертаційної роботи складають методи
багатокритеріальної оптимізації, теорії нечітких множин, теорії прийняття
рішень, системного аналізу та математичного моделювання.
Комплексне застосування підходів теорії ігор та теорії нечітких множин
дало можливість визначити кооперативну та некооперативну поведінку гравців
на випадок нечітких множин гравців та іхніх коаліцій в ігрових задачах.
Наукова новизна одержаних результатів. В дисертаційній роботі
отримано нові науково обґрунтовані результати в галузі теорії ігор, які
полягають у побудові та обґрунтуванні методів розв’язання задач із нечіткою
17
структурою. Усі основні результати дисертації є новими і опубліковані у
фахових журналах.
В процесі розв’язання поставлених задач вперше:
- розроблено метод розв’язання задачі максимізації функції на нечіткій
множині типу 2 (НМТ-2);
- розроблено метод вибору допустимих альтернатив з НМТ-2;
- розроблено методи побудови НМТ-2 ефективних рівноваг за Нешем та
альтруїстичних рівноваг за Бержем у некооперативних іграх із
нечіткими множинами гравців;
- розроблено метод побудови НМТ-2 рівноваг за Бержем
некооперативної гри з нечіткими коаліціями гравців, які «співчувають»;
- розроблено методи побудови НМТ-2 векторів Шеплі та розв’язків з Cядра кооперативних ігор із нечіткими множинами допустимих коаліцій,
які мають максимальну допустимості та ступінь недопустимості, яка не
перевищує задану величину.
Подальшого розвитку набули:
- концепції рівноваг за Нешем та альтруїстичних рівноваг за Бержем у
некооперативних іграх у випадку нечітких множин гравців;
- концепція рівноваги за Бержем у некооперативних іграх за умови
нечітких множин гравців, які «співчувають»;
- концепції C-ядра і вектора Шеплі в кооперативних іграх у випадку
нечітких множин допустимих коаліцій.
Практичне значення одержаних результатів. Дисертація носить
теоретичний характер. Отримані результати можуть мати подальше
застосування в різних розділах теорії ігор та теорії прийняття рішень. Оскільки
некооперативні ігри зустрічаються в багатьох прикладних галузях, результати
роботи можуть також формувати складову математичного апарату необхідного
для розв’язання конфліктів в економіці, біології, соціології, політології,
психології, етиці та інших галузях. Матеріал, викладений у дисертації, був
використаний в навчальному процесі кафедри системного аналізу та теорії
18
прийняття рішень факультету комп’ютерних наук та кібернетики Київського
національного університету імені Тараса Шевченка при викладанні
нормативного курсу «Теорія прийняття рішень» (напрям підготовки 6.0403.03
«системний аналіз»), що підтверджено відповідними актами впровадження
(додаток Б).
Особистий внесок здобувача. Дисертація є самостійною науковою
працею, в якій висвітлені власні ідеї і розробки автора, що дозволили
розв’язати поставлені завдання. Теоретичні та методичні положення і висновки,
сформульовані в роботі, одержані автором самостійно і відображені в
опублікованих працях. У спільних роботах із науковим керівником
С.О.Мащенком, вибір методів дослідження та доведення основних результатів
виконано Моренцем В.І., науковому керівнику належать постановки задач, а в
праці [6] співавтору належить також участь в обговоренні результатів.
Апробація результатів дисертації. Результати дисертаційної роботи
доповідалися та обговорювались на наукових семінарах в Київському
національному університеті імені Тараса Шевченка та на наукових
конференціях та міжнародних конференціях: “Problems of decision making
under uncertainties” (Yalta, 2011; Mukachevo, 2012; Mukachevo, 2014; Odessa,
2015; Skhidnytsia, 2015; Tbilisi-Batumi, 2016; Brno, 2016; Mukachevo, 2017;
Vilnus, 2017), «Математическое моделирование, оптимизация и
информационные технологии» (Кишинэу, 2016), «Проблеми інформатики та
комп’ютерної техніки» (Чернівці, 2016). Всеукраїнська науково-практична
конференція за міжнародною участю «Інформатика та системні науки»
(Полтава, 2017).
Публікації. За результатами дисертаційних досліджень опубліковано 19
наукових праць, серед яких 7 наукових статей у фахових журналах України [1 –
7], в їх числі 1 наукова стаття [6] у виданні, що включене до міжнародної
наукометричної бази, 12 тез доповідей у збірниках матеріалів наукових
конференцій [8 − 19].

Список литературы

ВИСНОВКИ
В дисертаційній роботі отримані нові науково обґрунтовані результати в
області теорії прийняття рішень у конфліктно-керованих ситуаціях,
обумовлених нечіткою початковою інформацією. Розроблені і застосовані на
модельних прикладах методи розв’язання ігрових задач з нечіткими
множинами гравців та їхніх коаліцій.
Дисертація є новим комплексним дослідженням, яке розв’язує важливі
актуальні наукові проблеми як теоретичного напряму, пов'язані з теорією ігор в
умовах нечіткої інформації, так і практичного – побудови й обґрунтування
методів розв’язання ігрових задач з нечіткою структурою.
Основними науковими і практичними результатами дисертації є:
1. Розроблено новий метод розв’язання задачі «максимізації» функції на
НМТ-2. Показано, що множина «оптимальних» розв’язків цієї задачі також є
НМТ-2. Побудовані її функція належності і носій.
2. Розроблено новий метод вибору «допустимих» альтернатив з НМТ-2.
Уведене поняття множини ефективних нечітких розв’язків. Досліджений
зв’язок множини розв’язків задачі "максимізації" функції на НМТ-2 з
множиною ефективних нечітких розв’язків.
3. Одержали подальший розвиток концепції рівноваг за Нешем та
альтруїстичних рівноваг за Бержем у некооперативних іграх із нечіткими
множинами гравців. Показано, що рівноважні ситуації утворюють НМТ-2,
побудовані їхні функції належності , досліджені їхні властивості.
4. Розроблено нові методи побудови носіїв НМТ-2 ефективних нечітких
рівноваг за Нешем та альтруїстичних рівноваг за Бержем в некооперативних
іграх з нечіткими множинами гравців.
5. Одержали подальший розвиток концепція рівноваг за Бержем у
некооперативних іграх із нечіткими множинами гравців, які «співчувають».
Показано, що множина рівноваг є НМТ-2, побудована її функція належності.
145
6. Розроблено новий метод побудови знаходження елементів носія НМТ-2
множини рівноваг за Бержем некооперативної гри з нечіткими коаліціями
гравців, які «співчувають».
7. Одержали подальший розвиток концепції C-ядра і вектора Шеплі в
кооперативних іграх із нечіткими множинами допустимих коаліцій. Показано,
що вони представляють НМТ-2. Вивчені їхні властивості. Побудовані їхні
функції належності.
8. Розроблено нові методи побудови носіїв НМТ-2 розв’язків з C-ядра та
множини векторів Шеплі кооперативних ігор із нечіткими множинами
допустимих коаліцій, які мають максимальний ступень допустимості та ступень
недопустимості, який не перевищує задану величину.
Результати наукового дослідження були впроваджені в 2016-2017 р.р. в
навчальний процес кафедри системного аналізу та теорії прийняття рішень
факультету комп’ютерних наук та кібернетики Київського національного
університету імені Тараса Шевченка