Індивідуально-оптимальні рівноваги в некооперативних іграх

(28)

Наслідками цієї теореми є сильна індивідуальна-оптимальність рівноваги у перевагах гравців; умови узгодженості () компонент векторів параметрів , , та рівність між собою значень функцій сукупної корисності гравців (,).

Зв'язок рівноваг у перевагах гравців з оптимальними за Парето ситуаціями гри встановлює таке твердження.

Твердження 5.2. Нехай ситуація задовольняє умові

, . (29)

Тоді .

Важливим наслідком цього твердження є умови існування рівноваг у перевагах.

Наслідок 5.10. Нехай у грі G множини стратегій гравців , , - компактні, а функції виграшу , , - напівнеперевні зверху. Тоді множина рівноваг у перевагах гри G є непорожньою компактною множиною.

Рівновагу у перевагах гравців гри G будемо називати оптимальною, якщо існує вектор такий, що виконуються нерівності:

, , , . (30)

Будемо позначати множину оптимальних у перевагах рівноваг .

Умови оптимальності рівноваг у перевагах гри G встановлює така теорема.

Теорема 5.10. Ситуація буде оптимальною рівновагою у перевагах гри G тоді й лише тоді, коли вона задовольняє умові (29). Якщо ситуація є оптимальною рівновагою у перевагах, то вона задовольняє умовам (30) у парі з вектором , який обчислений за формулою (28).

Будемо вважати множини стратегій гравців заданими у вигляді , де - функція обмежень, , - множина індексів обмежень на стратегії гравця .

Теорема 5.11. Нехай у грі GR функції виграшу гравців , та функції обмежень на стратегії гравців є неперервно-диференційованими та опуклими вниз, а множини стратегій гравців , задовольняють умові регулярності Слейтера (для кожного гравця існує така стратегія , що ). Тоді множини рівноваг у перевагах та оптимальних рівноваг у перевагах є рівними між собою, тобто .

У четвертому підрозділі узагальнюється поняття слабкої індивідуально-оптимальної рівноваги на випадок, коли гравці можуть нечітко враховувати інтереси своїх партнерів. Іншими словами, кожний гравець не може упевнено сказати, що він шукатиме компроміс із рештою гравців, але може задати нечітку множину гравців, інтереси яких він збирається враховувати.

Нехай - функція належності нечіткої множини гравців , інтереси яких збирається враховувати гравець .

Для кожного гравця агрегуємо відношення переваги гравців у відношення переваги їх спільноти . Отримане відношення пред-ставляє собою об'єднання нечіткої множини чітких відношень , .

Позначимо

- функцію належності нечіткої підмножини множини N з носієм , .

Об'єднанням нечіткої множини чітких відношень , , називатимемо - нечітке відношення типу 2, яке визначене на множині , та задається трійками , , де - функція належності нечіткого відображення , яке виконує роль “нечіткої функції належності” нечіткого відношення типу 2, і для має вигляд

Позначимо , . Наступна теорема дозволяє конструктивно побудувати функцію .

Теорема 5.12. Нехай , , - чіткі відношення, які задані на множині відповідними характеристичними функціями , , ; , , - функція належності нечіткої множини . Для того, щоб нечітка множина типу 2, яка задана функцією належності ; ; , була об'єднанням нечіткої множини відношень , , тобто, необхідно й достатньо, щоб для :

Формалізоване поняття нечіткої індивідуально-оптимальної рівноваги. Нехай - нечітке відношення типу 2 переваги всієї спільноти гравців, інтереси яких збирається враховувати гравець , яке задається функцією належності , , . Побудуємо для гравця нечітку множину (позначимо її ) ситуацій , які не домінуються за відношенням іншими ситуаціями , що отримані з ситуації зміною цим гравцем своєї стратегії на іншу . Тоді нечітка множина типу 2 недомінованих для гравця ситуацій задаватиметься функцією належності такого вигляду

,,.

Значення можна розуміти як “ступінь недомінованості” ситуації для гравця жодною іншою ситуацією , яка отримана зміною ним своєї стратегії на . Відповідно значення можна розуміти як ступінь домінованості ситуації для гравця усіма ситуаціями , які отримані зміною ним своєї стратегії на .

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

Нечітку множину з функцією належності вигляду , , будемо називати множиною нечітких індивідуально-оптимальних рівноваг і позначати . Множину будемо називати носієм .

Встановлений зв'язок множин нечітких індивідуально-оптимальних рівноваг та слабких індивідуально-оптимальних рівноваг .

Теорема 5.13. Нехай - загальна гра у нормальній формі (1). Тоді . Якщо функція належності нечіткої множини гравців , інтереси яких збирається враховувати гравець , є нормальною () для кожного , то . Оскільки гравців, як правило, цікавить вибір якоїсь єдиної ситуації гри, яка могла б стати основою стабільної угоди між ними, то їм варто вибрати нечітку індивідуально-оптимальну рівновагу із максимальним ступенем недомінованості . Ці міркування приводять до наступного поняття. Ситуацію назвемо максимізуючою нечіткою індивідуально-оптимальною рівновагою гри , якщо . Обґрунтовується існування максимізуючої нечіткої індивідуально-оптимальної рівноваги. Твердження 5.3. Для загальної гри у нормальній формі (1) завжди існує максимізуюча нечітка індивідуально-оптимальна рівновага.

ВИСНОВКИ

У дисертаційній роботі отримано нові науково обґрунтовані результати в галузі теорії прийняття багатокритеріальних рішень в умовах невизначеності, обумовленої конфліктом, при некооперативній поведінці гравців. Розроблено новий принцип оптимальності - принцип індивідуальної оптимальності, який реалізує концепцію компромісу кожного гравця з іншими заради вирішення конфлікту між ними. Дисертація є новим комплексним дослідженням, що розв'язує важливі актуальні наукові проблеми як теоретичного напряму, пов'язані з існуванням та властивостями мажорантних та індивідуально-оптимальних рівноваг, так і конструктивного: побудови й обґрунтування точних та наближених методів знаходження індивідуально-оптимальних рівноваг і оцінок їх стабільності; розробки методів вибору індивідуально-оптимальних рівноваг.

Основними науковими результатами дисертації є:

1. Запропоновані та досліджені поняття відношень NE-переваги, NE-домінування коаліцій гравців та множини найбільших і максимальних елементів за ними, встановлені та обґрунтовані їхні основні властивості та умови існування.

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

3. Запропоновані та досліджені поняття слабкої та сильної індивідуально-оптимальної рівноваги в загальних іграх та іграх із функціями виграшу гравців, обґрунтована їхня стабільність.

4. Узагальнені та досліджені поняття обережних стратегій та індивідуально-раціональних ситуацій для ігор, які задаються відношеннями переваги гравців. Встановлені та обґрунтовані достатні умови їхнього існування.

5. Встановлено зв'язок між індивідуально-оптимальними рівновагами та індивідуально-раціональними ситуаціями гри, оптимальними за Парето ситуаціями, рівновагами за Нешем, за Бержем та коаліційними рівновагами.

6. Встановлені та обґрунтовані необхідні й достатні та достатні умови слабкої та сильної індивідуальної оптимальності. Встановлені умови існування індивідуально-оптимальних рівноваг.

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

8. Розроблено процедуру пошуку індивідуально-оптимальних рівноваг в умовах часткової інформованості гравців. Обґрунтовано збіжність цієї процедури та одержано оцінки швидкості її збіжності.

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

10. Розроблено наближений метод оцінки максимальної та мінімальної стабільності індивідуально-оптимальних рівноваг в іграх n осіб.

11. Запропоновані поняття рівноваги у перевагах гравців та оптимальної рівноваги у перевагах гравців. Встановлені їх властивості. Обґрунтовані необхідні й достатні умови їхнього існування.

12. Запропоноване поняття нечіткої індивідуально-оптимальної рівноваги, в якій кожний гравець враховує інтереси нечіткої множини інших гравців. Для цього уведене та досліджене поняття об'єднання нечіткої множини чітких відношень. Розроблені конструктивні формули для побудови функції належності цього відношення. Встановлений зв'язок множин нечітких та чітких індивідуально-оптимальних рівноваг та обґрунтоване існування максимізуючої нечіткої рівноваги.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мащенко С.О. Розподілена процедура прийняття рішень в умовах нечіткої інформації / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 1999. - № 4. - С. 205 - 211.

2. Мащенко С.О. Рівновага за Нешем у багатокритеріальній грі / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2001. - № 3. - C. 292 - 300.

3. Мащенко С.О. Рівновага за Нешем у нечітких іграх / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2004. - № 2. - С. 302 - 309.

4. Мащенко С.О. Векторні рівноваги у змішаних стратегіях / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2006. - № 1. - C. 171 - 177.

5. Мащенко С.О. Слабкі індивідуально-оптимальні рівноваги / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2006. - № 2. - С. 216 - 223.

6. Мащенко С.О. Исследование стабильности равновесий на основе принципа индивидуальной оптимальности / С.О. Мащенко // Кибернетика и системный анализ. - 2007. - № 4. - С. 162 - 169.

7. Мащенко С.О. Індивідуально-оптимальні рівноваги в некооперативних опуклих іграх / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2008. - № 2. - С.105 - 110.

8. Мащенко С.О. Локальні умови слабкої індивідуальної оптимальності рівноваг / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2008. - № 3. - С. 142 - 147.

9. Мащенко С.О. Багатоцільові ігри у відношеннях переваги гравців / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2008. - № 4. - С. 135 - 140.

10. Мащенко С.О. Индивидуально-оптимальные равновесия некооперативных игр в отношениях предпочтения / С.О. Мащенко // Кибернетика и системный анализ. - 2009. - № 1. - С. 171 - 179.

11. Мащенко С.О. Відношення NE-переваги і домінування в некооперативних іграх та їх властивості / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2009. - № 1. - С. 115 - 120.

12. Мащенко С.О. Достатні умови індивідуальної оптимальності / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2009. - № 2. - С. 119 - 124.

13. Мащенко С.О. Стабільні за перевагами рівноваги в одноцільових некооперативних іграх / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2009. - № 3. - С. 152 - 157.

14. Мащенко С.О. Вибір індивідуально-оптимальних рівноваг за критерієм стабільності / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2009. - №4. - С. 113 - 118.

15. Мащенко С.О. Індивідуальна раціональність індивідуально-оптимальних рівноваг / С.О. Мащенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2010. - № 2. - С. 124 - 129.

16. Мащенко С.О. Використання функції корисності для пошуку обережних і домінуючих стратегій в багатокритеріальній грі / С.О. Мащенко, О.В. Бабенко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2000. - № 4. - С. 249 - 258.

17. Мащенко С.О. Пошук оптимальних за Слейтером ситуацій у багатокритеріальній грі / С.О. Мащенко, О.Г. Павлюченко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2002. - № 4. - С. 216 - 220.

18. Мащенко С.О. Загальні умови векторної рівноваги за Нешем / С.О. Мащенко, О.Г. Павлюченко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2004. - № 4. - C. 212 - 216.

19. Мащенко С.О. Рівновага за набором цілей гравців / С.О. Мащенко, С.О. Бровченко // Вісник Київського університету. Серія: фіз.-мат. науки. - 2010. - № 1. - С. 126 - 131.

20. Волкович В.Л. Алгоритмы поиска допустимого решения в линейных распеределенных системах / Волкович В.Л., Коленов Г.В., Мащенко С.О. // Проблемы управления и информатики (Автоматика). - 1988. - № 4. - С. 70 - 77.

21. Волкович В.Л. Алгоритмы решения линейной оптимизационной задачи в распределенной системе системах / Волкович В.Л., Коленов Г.В., Мащенко С.О. // Проблемы управления и информатики (Автоматика).-1989.- № 1. - С. 38 - 46.

22. Волошин А.Ф. Субэкспонентциальный алгоритм решения задачи о ранце / А.Ф. Волошин, С.О. Мащенко // Докл. АН УССР. Сер. А. физ.-мат. и техн. науки. - 1986. - № 10 . - С. 55 - 58.

23. Волошин О.Ф. Алгоритм послідовного анализу варіантів для розв'язання балансових моделей / Волошин О.Ф., Мащенко С.О., Охрименко М. Г. // Доповіді АН УРСР. Сер. А. Фіз.-мат. та техн. науки. - 1988. - № 9 . - С. 67 - 70.

24. Применение методов последовательного анализа вариантов для аппроксимации многогранных множеств / [Волкович В.Л., Волошин А.Ф., Мащенко С.О., Козаченко Т.Б.] // Кибернетика и системный анализ (Кибернетика). - 1991. - № 2 . - С. 116 - 120.

25. Мащенко С.О. Замена переменных в задачах линейного программирования с переменными коэффициентами / С.О. Мащенко // Проблемы создания интеллектуальных систем поддержки принятия решений : Сб. науч. тр. / АН УССР. Ин-т кибернетики им. В.М. Глушкова; науч. совет по пробл. “Кибернетика”; Редкол. : Волкович В.Л. (отв. ред.) и др. - Киев, 1990. - С. 45 - 51.

26. Мащенко С.О. Нечіткі ігри з відношеннями переваги гравців / Сергій Мащенко // Фізико-математичне моделювання та інформаційні технології. - Львів : Центр мат. мод. Інституту прикладних проблем механіки і математики ім. Я. С. Підстригача НАНУ, 2010, вип. 11. - С. 105 - 112.

27. Мащенко С.О. Нечеткие индивидуально-оптимальные равновесия / С.О. Мащенко // Кибернетика и вычислительная техника.- 2010, вип.159.- С. 19 - 29.

28. Mashchenko S.O. A Decision Making Algorithm in a Distributed System / S.O. Mashchenko // Information Theories & Applications.-1996.- 4.-N 2.-P.33 - 39.

29. Мащенко С.О. Индивидуально-оптимальные равновесия в играх двух лиц / С.О. Мащенко // International Book Series “Information Science & Computing”. - 2008. - N 7. - P. 157 - 163.

30. Мащенко С.О. Поиск индивидуально-оптимальных равновесий в условиях частичной информированности игроков / С.О. Мащенко // International Book Series “Information Science & Computing”. Knowledge - Dialog - Solution. - 2009. - N 15. - P. 180 - 188.

31. Волошин А. Методологические принципы распределения квот на выбросы парниковых газов / Волошин А., Горицына И., Мащенко С. // Natural and Artificial Intellegence; K. Markov, V. Velychko, O. Voloshin (editors). - Sofia: ITHEA, 2010. - P. 85 - 93.

32. Voloshin O. Individually optimal principles of distribution of greenhouse gas emmision quotas / Olexij Voloshin, Sergij Mashchenko // Information Models of Knowledge; K. Markov, V. Velychko, O. Voloshin (editors). - Kiev-Sofia: ITHEA, 2010. - P. 209 - 214.

33. Мащенко С.О. Процедура принятия решений в задачах с распределенными критериями / С.О. Мащенко // KDS-97: Шестая международная конференция “Знания - диалог - решение”, 15-20 сент. 1997 г. : сб. научн. трудов в 2-х томах. - Ялта, 1997. - 2. - С. 381 - 385.

34. Mashchenko S.O. Multicriterial game with isolatad players behavior / S.O. Mashchenko // Труды междунар. научн.-практ. конф. KDS-2001 “Знание - диалог - решение” KDS-2001: июнь, 2001 г., Санкт-Петербург. - СПб.: Лань. - 2001. - 2. - С. 476 - 480.

35. Мащенко С.О. Векторные равновесия / С.О. Мащенко // XI-th International Conference KDS -2005 “Knowledge - Dialogue - Solution”: June, 2005, Varna, Bulgaria. Proceedings.-Sofia:FOI-COMMERCE.- 2005. - P. 226- 231.

36. Мащенко С.О. Принцип индивидуальной оптимальности в играх // Сергей Мащенко / XII-th International Conference KDS -2006 “Knowledge - Dialogue - Solution”: June, 2006, Varna, Bulgaria. Proceedings. - Sofia: FOI-COMMERCE. - 2006. - P. 217 - 223.

37. Мащенко С.О. Один подход к равновесиям в играх в условиях неопределенности / С.О. Мащенко // XIII-th International Conference KDS -2007 “Knowledge - Dialogue - Solution”: June, 2007, Varna, Bulgaria. Proceedings. - Sofia: ITHEA. - 2007. - 1. - P. 129 - 137.

38. Мащенко С.О. Умови існування мажорантних рівноваг у загальних багатокритеріальних іграх / С.О. Мащенко // V міжнародна школа-семінар “Теорія прийняття рішень” : Праці школи-семінару, Ужгород, 27 вересня - 1 жовтня, 2010 р. - Ужгород: УжНУ, 2010. - С. 151.

39. Мащенко С.О. Нечіткі індивідуально-оптимальні рівноваги / С.О. Мащенко // ХVІ Intern. Conference “Problems of decision making under uncertainties” (PDMU-2010) : Abstracts, Yalta, Ukraine, October 4-8, 2010. - К.: Вид-во “Освіта України”, 2010. - С. 100.

АНОТАЦІЯ

Мащенко С.О. Індивідуально-оптимальні рівноваги в некооперативних іграх. - Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.04 - системний аналіз і теорія оптимальних рішень. - Київський національний університет імені Тараса Шевченка, Київ, 2011.

Дисертаційна робота присвячена розробці та обґрунтуванню принципу індивідуальної оптимальності в некооперативних іграх, який реалізує концепцію компромісу кожного гравця з іншими заради вирішення конфлікту між ними. Формалізоване поняття індивідуально-оптимальної рівноваги, встановлені та доведені умови її існування, досліджено зв'язок з іншими типами рівноваг. Побудовано моделі, критерії та методи оцінки стабільності індивідуально-оптимальних рівноваг. Формалізоване поняття рівноваги у перевагах гравців. Встановлені та доведені умови її існування та досліджені її властивості. Формалізоване поняття нечіткої індивідуально-оптимальної рівноваги, в якій кожний гравець враховує інтереси нечіткої множини інших гравців. Встановлений її зв'язок з множиною індивідуально-оптимальних рівноваг та обґрунтоване існування максимізуючої нечіткої рівноваги.

Ключові слова: некооперативна гра, рівновага Неша, індивідуально-оптимальна рівновага, компроміс, принцип оптимальності, стабільність.

АННОТАЦИЯ

Мащенко С.О. Индивидуально-оптимальные равновесия в некооперативных играх. - Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.04 - системный анализ и теория оптимальных решений.- Киевский национальный университет имени Тараса Шевченко, Киев, 2011.

Диссертационная работа посвящена разработке и обоснованию принципа индивидуальной оптимальности в некооперативных играх, который реализует концепцию компромисса каждого игрока с другими ради разрешения конфлик-та между ними. Введены понятия отношений NE-предпочтения, NE-доминиро-вания коалиций игроков и множеств наибольших и максимальных элементов, установлены их основные свойства и условия существования. Предложены и исследованы понятия слабого и сильного мажорантного равновесия в неко-оперативных играх с целями игроков, которые задаются множествами отноше-ний предпочтения. Разработаны критерии слабого и сильного мажорантного равновесия, в частности, и для случая существования функций выигрыша игроков. Формализованы понятия слабого и сильного индивидуально-оптимального равновесия в обобщенных играх и играх с функциями выигрыша игроков, обоснована их стабильность в некооперативных играх. Исследована связь между индивидуально-оптимальными равновесиями и индивидуально-рациональными ситуациями игры, оптимальными по Парето ситуациями, равновесиями по Нэшу, по Бержу и коалиционными равновесиями. Установ-лены и доказаны условия слабой и сильной индивидуальной оптимальности. Построены модели и критерии оценки стабильности равновесий, которые позволяют оценить компромисс, на который должен согласиться каждый игрок для установления стабильного соглашения, в обобщенных играх, играх с функциями выигрыша игроков, выпуклых играх и играх с дифференци-рованными функциями выигрыша. Разработана процедура поиска индивиду-ально-оптимальных равновесий в условиях частичной информированности игроков. Обоснована сходимость процедуры и получены оценки скорости ее сходимости. Получены оценки стабильности индивидуально-оптимальных равновесий для игр двух лиц. Разработан приближенный метод оценки макси-мальной и минимальной стабильности равновесий в играх n лиц. Для игр с функциями выигрыша игроков формализованы понятия равновесия в предпоч-тениях игроков. Установлены и доказаны условия их существования, исследо-ваны их свойства. Формализовано понятие нечеткого индивидуально-оптималь-ного равновесия, в котором каждый игрок учитывает интересы нечеткого множества других игроков. Для этого введено понятие объединения нечеткого множества четких отношений. Разработаны конструктивные формулы для построения функции принадлежности этого отношения. Исследована связь множеств нечетких и четких индивидуально-оптимальных равновесий, обосновано существование максимизирующего нечеткого равновесия.

Ключевые слова: некооперативная игра, равновесие Нэша, индивидуально-оптимальное равновесие, компромисс, принцип оптимальности, стабильность.

ABSTRACT

Mashchenko S.O. Individual-optimal equilibriums in non-cooperative games. - Manuscript.

Thesis submitted for a Doctor's degree of physics and mathematics on proficiency 01.05.04 “System analysis and theory of optimal decisions.” - Taras Shevchenko Kyiv National University, Kyiv, 2011.

This thesis is devoted to development and justification of the principle of individual optimum in the non-cooperative games, which implements the conception of compromise of every player with others for the sake of resolving the conflict between them. The notion of individual-optimal equilibrium was formalized, defined and the conditions of its existence were proved. Connection with other types of equilibriums was explored. Models, criterions and methods of stability estimation of individual-optimal equilibriums were built. The notion of equilibrium in players' preferences was formalized. Conditions of equilibrium existence were defined and its properties were explored. The notion of fuzzy individual-optimal equilibrium, where every player takes the interests of the fuzzy set of other players into consideration, was defined. The connection of the fuzzy equilibrium with the set of individual-optimal equilibriums was researched and the existence of the maximizing fuzzy equilibrium was defined.

Keywords: a non-cooperative game, Nesh's equilibrium, a individual-optimal equilibrium, a compromise, principle of optimum, stability.

Размещено на Allbest.ru