Buchumschlag

Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри

An algorithm for solving a stochastic game for decision making in hierarchical systems under uncertainty is developed. An analysis of the results of computer modeling of a stochastic game for autocratic, anarchic and democratic hierarchical decision making systems with the binary tree structure is p...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2019
1. Verfasser: Kravets, Petro A.
Format: Artikel
Sprache:Ukrainisch
Veröffentlicht: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019
Schlagworte:
прийняття рішень
ієрархічна система
умови невизначеності
стохастична гра
комп’ютерне моделювання
Online Zugang:https://journal.iasa.kpi.ua/article/view/188564
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:System research and information technologies
Завантажити файл: Pdf

Institution

System research and information technologies
_version_ 1867334403211919360
author Kravets, Petro A.
author_facet Kravets, Petro A.
author_institution_txt_mv [ { "author": "Petro A. Kravets", "institution": "Національний університет “Львівська політехніка”, Львів" } ]
author_sort Kravets, Petro A.
baseUrl_str http://journal.iasa.kpi.ua/oai
collection OJS
datestamp_date 2020-03-02T17:05:10Z
description An algorithm for solving a stochastic game for decision making in hierarchical systems under uncertainty is developed. An analysis of the results of computer modeling of a stochastic game for autocratic, anarchic and democratic hierarchical decision making systems with the binary tree structure is performed. It has been established that autocratic-centric hierarchical systems have the smallest training time for achieving a close-to-consensus solution. The influence of parameters on the convergence of the game method in the process of finding a consensus or a majoritarian collective solution is studied.
doi_str_mv 10.20535/SRIT.2308-8893.2019.4.11
first_indexed 2025-07-17T10:26:37Z
format Article
fulltext  П.О. Кравець, 2019 Системні дослідження та інформаційні технології, 2019, № 4 105 УДК 004.852; 004.94 DOI: 10.20535/SRIT.2308-8893.2019.4.11 ІГРОВІ СТРАТЕГІЇ ПРИЙНЯТТЯ РІШЕНЬ В ІЄРАРХІЧНИХ СИСТЕМАХ. ІІ. КОМП’ЮТЕРНЕ МОДЕЛЮВАННЯ СТОХАСТИЧНОЇ ГРИ П.О. КРАВЕЦЬ Анотація. Розроблено алгоритм розв’язування стохастичної гри для прийняття рішень в ієрархічних системах в умовах невизначеності. Виконано аналіз ре- зультатів комп’ютерного моделювання стохастичної гри для автократичної, анархічної та демократичної систем прийняття рішень зі структурою бінарного дерева. Установлено, що найменший період навчання для досягнення близько- го до консенсусного рішення мають автократично-центричні ієрархічні систе- ми. Вивчено вплив параметрів на збіжність ігрового методу у процесі пошуку консенсусного або мажоритарного колективного рішення. Ключові слова: прийняття рішень, ієрархічна система, умови невизначеності, стохастична гра, комп’ютерне моделювання. ВСТУП Ієрархічна система прийняття рішень — це багаторівнева система з розмі- щенням елементів від вищого до нижчого рангу [1–4]. У такій організацій- ній структурі можна виокремити елементи вищого, середнього та нижчого рівнів. Елементи одного рівня зазвичай мають однаковий ранг або однакові можливості щодо прийняття рішень. Елементи найвищого рівня генерують керувальні рішення для елемен- тів нижчого рівня. Елементи середнього рівня на основі рішень, надісланих від елементів вищого рівня, виробляють власні рішення для елементів ниж- чого рівня. Рішення елементів найнижчого рівня спрямовані на виконання конкретних робіт. Для дослідження ієрархічних систем прийняття рішень в основному використовують методи теорії ігор — безкоаліційних або коаліційних, детер- мінованих або стохастичних, дискретних або диференціальних, у нормаль- ній формі (з одночасним вибором варіантів дій) або ієрархічних ігор (з пра- вом першого ходу) [3–8]. Залежно від постановки завдання досліджуються стратегії прийняття рішень, які забезпечують досягнення класичних колек- тивних розв’язків, оптимальних за Нешем, Парето, Слейтером, Джофріоном, Байєсом, Штакельбергом або інших [9, 10]. Серед різноманіття ігрових за- дач виділимо підклас стохастичних ігор у нормальній формі, які дають мож- ливість знаходити колективні розв’язки гри в умовах стохастичної невизна- ченості матриць платежів [8]. Гравець є активною інформаційною сутністю, здатною взаємодіяти з іншими гравцями, навчатися і приймати самостійні рішення на основі опра- цювання поточних даних. Використовуючи термінологію мультиагентних систем [11–15], таку активну сутність назвемо агентом прийняття рішень. П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 106 Оскільки прийняття рішень в ієрархічній системі спрямоване на колек- тивне розв’язування конкретного завдання, то дії агентів повинні бути скоор- динованими. Координація — це узгодження дій агентів системи прийняття рішень з метою досягнення поставлених цілей. Координація здійснюється шляхом виконання керівних рішень або через домовленості між елементами системи [13, 14]. У цій роботі розглядаються обидва варіанти: 1) рішення вважається сформованим, якщо у ході стохастичної гри більшість агентів вибрали стратегії, що збігаються з наперед заданою керівною стратегією; 2) агенти приймають скоординоване колективне рішення у ході взаємодії і самонавчання. Поряд з теоретичним дослідженням систем прийняття рішень важли- вим є розроблення комп’ютерних засобів моделювання для апробації та до- повнення теоретичних результатів на практиці. Комп’ютерне моделювання ієрархічних систем прийняття рішень є ак- туальною прикладною проблемою, вирішення якої дозволяє уточнити ре- зультати теоретичного оцінювання умов збіжності методів прийняття рі- шень у конкретних практичних ситуаціях. Практичні проблеми прийняття рішень в ієрархічних системах дослі- джуються спеціалістами з багатьох предметних галузей, пов’язаних з колек- тивною поведінкою та колективною взаємодією. Для цього використовують або готові інструментальні засоби, або спеціально розроблені програмні продукти, коли необхідно врахувати певні особливості постановки завдання колективного прийняття рішень [15–17]. Мета роботи — розроблення алгоритмічних та програмних засобів мо- делювання стохастичних ігор у нормальній формі для координації рішень в ієрархічних системах та визначення факторів, які впливають на збіжність ігрового методу в умовах стохастичної невизначеності. Результати роботи можуть бути використані для підтримання прийнят- тя скоординованих колективних рішень у системах з ієрархічною організа- цією. ІЄРАРХІЧНІ СИСТЕМИ ПРИЙНЯТТЯ РІШЕНЬ Нехай платежі ігрових агентів ієрархічної системи є функцією власних стра- тегій, стратегій агентів вищого і нижчого рівнів, зважених коефіцієнтом ]1,0[ . Значення коефіцієнта визначає ступінь впливу стратегій сусідніх агентів на формування платежів кожного агента і, відповідно, напрямки по- токів інформації між рівнями ієрархії системи прийняття рішень. Відхилен- ня від стратегії агента-керівника враховується з коефіцієнтом  , а відхи- лення від стратегій агентів-виконавців — з коефіцієнтом 1 . Залежно від значень цього коефіцієнта отримаємо різні види ієрархічних систем: 1 — автократична; 0 — анархічна; 10  — множина демократичних систем. Назви ієрархічних систем є умовними, а їх інтерпретація у цій роботі не замінює їх відомі трактування. Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 107 В автократичній системі агенти нижчого рівня беруть до виконання вказівні рішення агента вищого рівня. Потоки керування спрямовані згори вниз. Ієрархію анархічної системи слід розуміти як делегування повнова- жень на вищі рівні від самоорганізованих спільнот агентів найнижчого рів- ня. Потоки інформації в анархічній системі спрямовані знизу вгору. У демо- кратичних системах на вироблення рішень впливають потоки інформації як згори вниз, так і знизу вгору. Експериментальне дослідження ігрового методу прийняття рішень ви- конаємо для стохастичної гри зі структурою бінарного дерева. Симетричне бінарне дерево складається з 12  mL вузлів, де m — кількість рівнів іє- рархічної системи прийняття рішень ( ...,2,1m ). Вузли дерева позначають гравців, а дуги – їх стратегії, які впливають на формування поточних про- грашів гравців. Нехай поточні втрати гравців визначаються власними стра- тегіями та стратегіями сусідніх гравців так, як це показано на рис. 1, що від- повідає структурі демократичної системи з параметром 10  . Для граничних значень параметра 1 та 0 зі структури демокра- тичної системи відповідно отримаємо структури автократичної та анархіч- ної систем прийняття рішень, зображені на рис. 2–5. Рис. 1. Структура демократичної системи Рис. 2. Структура автократичної системи Рис. 3 Структура автократичної системи з колегіальним центром П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 108 Поведінка гравця найвищого рівня в автократичній системі, зображеній на рис. 2, є вільною від впливу стратегій інших гравців. Якщо кореневий гравець вибирає власні стратегії rootroot Uun  за деяким дискретним розподі- лом rootroot NSp  , то його стратегія змінюється у часі: varroot nu , ...,2,1n . Чим ближче розподіл rootp до рівноймовірного вибору чистих стратегій, тим більше кореневий гравець дезорієнтує гравців нижчих рівнів. У результаті вихід системи на узгоджене колективне рішення є проблематич- ним або неможливим. Можливі такі два працездатні способи формування чистих стратегій цього гравця, які забезпечують координацію автократичної системи. Пер- ший спосіб полягає в тому, що стратегії кореневого гравця є постійними constrootroot =uun  у часі ...,2,1n . У цьому випадку маємо автократичну систему з догматичним центром. Другий спосіб відповідає структурі авто- кратичної системи з колегіальним центром, як це показано на рис. 3. У цьому випадку на формування втрат кореневого гравця впливають власні стратегії та стратегії хоча б одного із гравців нижчого рівня. Аналогічно, якщо гравці найнижчого рівня анархічної системи обира- ють власні стратегії ii n Uu  з дискретними розподілами iNi Sp  (рис. 4), то вони генеруватимуть змінні стратегії vari nu поведінки у часі і з близькою до 1 імовірністю система не зможе досягнути скоординованого консенсус- ного (вирівнювального) рішення. Для того щоб анархічна система вийшла на узгоджене рішення, можна скористатися одним із двох способів. Перший полягає у тому, що всі гравці найнижчого рівня, попередньо домовившись, дотримуються однакових стратегій поведінки const uui n у часі. У цьому випадку маємо анархічну систему з догматичною спільнотою. Другий спосіб полягає у тому, що грав- ці найнижчого рівня об’єднуються у спільноту і їх поточні втрати визнача- ються як власними стратегіями, так і стратегіями інших гравців спільноти. У цьому випадку (рис. 5) маємо анархічну систему з горизонтальними зв’язками на найнижчому рівні (з організованою спільнотою). Для праце- здатності такої анархічної системи повинен існувати циклічний шлях за- лежностей платіжних функцій від стратегій гравців, яким можна обійти усі елементи найнижчого рівня. Тоді однакові стратегії дерева агентів будуть формуватися динамічно в часі, у процесі навчання гравців. Розглянуті ієрархічні системи є активними системами прийняття рі- шень, оскільки агенти не просто транслюють рішення між рівнями ієрархії, а мають власні стратегії поведінки. Крім того, ієрархічні системи є системами з розподіленим (або колекти- вним) прийняттям рішень, виходячи з того, що вони складаються з організо- ваної за рангами множини автономних агентів (ураховано структурний ас- пект). Якщо у процесі навчання (вироблення рішень) розподілена система прагне вийти на рішення центру, то вона є централізованою. Рішення центру відоме до початку гри і не змінюється у ході гри. Центром може бути Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 109 один агент або група агентів з наперед узгодженим рішенням. Якщо ж у процесі навчання розподілена система формує узгоджене колективне рі- шення, яке не відоме до початку гри, то вона є децентралізованою (ура- ховано функціональний аспект). Із цих міркувань догматична автократична система є централізованою (з потоками керівних рішень згори вниз), автократична система з колегіаль- ним центром — децентралізованою, анархічна система з догматичною спі- льнотою — централізованою (знизу вгору), анархічна система з горизонта- льними зв’язками — децентралізованою, демократичні системи є децентралізованими. АЛГОРИТМ РОЗВ’ЯЗУВАННЯ СТОХАСТИЧНОЇ ГРИ Крок 1. Задати початкові значення параметрів гри: 0n — початковий мо- мент часу; D — множина (дерево) гравців; || DL  — потужність множини (кількість) гравців; iN — кількості чистих стратегій гравців Di ; )}(),...,2(),1({ i iiii NuuuU  Di — вектори чистих стратегій гравців; )/1,...,/1(0 ii i NNp  Di — змішані стратегії гравців; 0 — параметр кроку навчання; ]1,0( — порядок кроку навчання; 0 — параметр  -симплексу; 0 — порядок швидкості розширення  -симплексу; ]1,0[ — ваговий коефіцієнт поточних програшів; maxn — максимальна кількість кроків стохастичної гри. Крок 2. Вибрати поточні чисті стратегії:            j k i i n j ii n Njkpjjuu 1 )..1()(minarg|)( Di , де ]1,0[ — випадкова величина з рівномірним розподілом. Крок 3. Отримати значення поточних програшів: Рис. 4. Структура анархічної системи Рис. 5 Структура анархічної системи з горизонтальними зв’язками П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 110 n kDj j n i n k n i ni D n i n i i uuuuDu             }{\ 1 ||)1(||||)( Di , де iD — множина сусідніх гравців i -го гравця; j Dj DD n UUu i ii   — колек- тивна стратегія множини гравців iD ; 1Rui n  — числовий еквівалент варіа- нта рішення; k — гравець вищого рівня (керівник); i — гравець середнього рівня; j — гравець нижчого рівня; ),0(~ dNormaln — білий гауссівський шум з дисперсією 0d ; ]1,0[ — ваговий коефіцієнт. Для кореневого гравця 0 , а для гравців найнижчого рівня 1 . Крок 4. Обчислити значення параметрів:  nn ,  nn , де 0n — монотонно спадна послідовність додатних величин, яка регу- лює величину кроку методу; 0n — монотонно спадна послідовність до- датних величин, яка регулює швидкість розширення  -симплексу. Крок 5. Визначити нові значення векторів змішаних стратегій: }])([{ 11 i n i n i nn i n Ni n puepp i n   Di , де i n N 1 — проектор на одиничний  -симплекс ii n NN SS   1 [18]; i n Ni n Sp  — змішані стратегії i -го гравця; 1Ri n  — поточний програш гравця; )( i nue – одиничний вектор-індикатор вибору варіанта ii n Uu  . Крок 6. Розрахувати характеристики якості ігрового прийняття рішень: 1) функція усереднених у часі втрат системи:      n t Di i tn nL 1 1)( ; 2) коефіцієнт узгоджених рішень гравців:                n t Di Ds s t i tn i uunL 1 1 0||)( , де }1,0{)(  — індикаторна функція події; 3) середня похибка відхилення змішаних стратегій гравців від змішаної стратегії гравця-керівника найвищого рівня:      n t Di ttin ppnL 1 ,root, 1)( , де  — евклідова норма вектора. Крок 7. Задати наступний момент часу 1:  nn . Крок 8. Якщо maxnn  , то перейти до кроку 2, інакше — кінець гри. Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 111 РЕЗУЛЬТАТИ ЕКСПЕРИМЕНТАЛЬНИХ ДОСЛІДЖЕНЬ Результати комп’ютерного моделювання процесу ігрового прийняття рі- шень в ієрархічних системах зі структурою симетричного бінарного дерева подано у вигляді графіків на рис. 6 – рис. 15. Результати отримано для таких значень параметрів гри: 7L (для 3m рівнів ієрархічної системи прийняття рішень), 4 NNi , 1 , N/999,0 , 01,0 , 1 , крім випадків, коли вивчається вплив цих параметрів на збіжність ігрового методу. Для ком- пактного зображення результатів моделювання з великим діапазоном зна- чень використано логарифмічну шкалу. Ураховуючи те, що метою гравців ієрархічної системи є вирівнювання чистих стратегій, їх матриці платежів (програші) задаються так:        01 10 ][ iv Di . Якщо гравцями вибрано однакові стратегії, то їх про- граш дорівнює 0, інакше — 1. Для таких матриць платіжні функції  2,2 2 2 1 21,2 2 1 1 22,1 2 2 1 11,1 2 1 1 1 vppvppvppvppV i 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 2)1()1( pppppppp  мають вигляд сідлової поверхні у просторі змішаних стратегій гравців. На рис. 6 зображені зрізи значень сідлової платіжної функції, отримані з кроком 16/1h , і траєкторія навчання ланки ієрархічної стохастичної гри «керівник – підлеглий», кожен з яких має по два варіанти прийняття рішень (гра 22 ). Показано зрізи платіжної функції без дії завад ( 0d ) та в умо- вах дії завад ( 01,0d ). У вершинах та в центрі квадрата позначено значення платіжної функції для комбінованих стратегій двох гравців. Гра з вирівнювання стратегій має два стійкі рівноцінні розв’язки у чис- тих стратегіях, розміщені у вершинах (0, 0) та (1, 1) зі значеннями платіжних 2 1p 1 1p 1 0 1d=0 2 1p 1 1p 1 0 1d=0,1 Рис. 6. Проекція зрізів платіжної функції на площину П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 112 функцій 0iV , та нестійкий розв’язок у змішаних стратегіях у точці (0,5; 0,5) зі значеннями платіжних функцій 5,0iV . Для розв’язків у чистих стратегіях справедливі умови рівноваги за Нешем та оптимальності за Паре- то для гри у нормальній формі, а також умова оптимальності за Штакельбер- гом для послідовної гри. Розв’язок у змішаних стратегіях задовольняє умову рівноваги за Нешем. Якщо гравці дотримуються оптимальних стратегій у точці рівноваги за Нешем, то зі зміною стратегії одного з них він не зможе зменшити свій про- граш (для задачі мінімізації середніх втрат). Оптимальність за Парето ви- пливає з тотожності матриць платежів гравців. У точці оптимальності за Па- рето не існує спільної стратегії, яка дозволить зменшити середній програш одночасно для всіх гравців. Оптимальність за Штакельбергом визначається за деревом можливих комбінацій чистих стратегій, які мінімізують втрати гравців, з урахуванням попередніх ходів гравців вищих рівнів ієрархії, ви- ходячи із оптимістичної гіпотези про те, що гравці сприяють один одному у виборі ходів гри. За відсутності дії завад ( 0d ) пошукова траєкторія стохастичної гри прямує до однієї з точок рівноваги за найкоротшим, близьким до лінійного, шляхом. Дія завад ( 0d ) призводить до викривлення траєкторії пошуку. Графіки однієї з реалізацій функцій коефіцієнта скоординованих стра- тегій nK , середніх програшів гравців n та похибки змішаних стратегій n , які характеризують ефективність стохастичної гри демократичної ( 5,0 ) системи прийняття рішень, зображено на рис. 7. Результати отри- мано для системи без завад ( 0d ) та в умовах дії завад ( 1d ). Загальний вигляд та взаємне розташування графіків функцій зберігається у разі повто- рення експерименту для різних послідовностей випадкових величин. Для автократичної ( 1 , з догматичним або колегіальним центром) та анархіч- ної ( 0 , з догматичною або організованою спільнотою) систем отримаємо подібні залежності [3, 4]. Спадання функцій n , n та зростання коефіцієнта координації nK у часі свідчать про збіжність ігрового методу згідно із сформульованою ме- тою. Порядок швидкості збіжності може бути оцінений тангенсом кута  nlg nflg Kn n n  d=0 nlg nflg Kn n n d=1 Рис. 7. Характеристики ігрового прийняття рішень в демократичній системі Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 113 лінійної апроксимації графіка норми n відхилення змішаних стратегій гравців від контрольних значень та віссю часу. Як видно з рис. 7, за відпо- відного підбору параметрів досягається близький до 1 порядок степеневої швидкості збіжності розглянутої стохастичної гри. У системах із завадами для збіжності ігрового методу необхідна більша кількість пошукових кроків для досягнення оптимального колективного розв’язку. Запропонований метод розв’язування ієрархічної стохастичної гри прийняття рішень належить до класу реактивних методів і має відносно не- велику швидкість збіжності. Це зумовлено тим, що на початок гри немає ніякої інформації про середовище, з яким взаємодіють гравці. Інформація збирається у процесі навчання шляхом адаптивної перебудови векторів змі- шаних стратегій пропорційно до значень поточних програшів. Графіки на рис. 8–15 усереднено за 100 реалізаціями стохастичної гри з різними послідовностями випадкових величин. Графік залежності періоду n навчання гравців вибирати скоординовані рішення з коефіцієнтом 9,0nK показано на рис. 8, а залежності коефіцієн- та координації nK на момент 4 max 10n кроків гри від параметра  ієрар- хічної системи — на рис. 9. Значення параметра 10  відповідає одній з демократичних (див. рис. 1), 1 — автократичній (рис. 2) і 0 — анар- хічній (рис. 3) системам прийняття рішень. Як видно з рис. 9, близьке до консенсусного рішення отримується для діапазону значень параметра ]9,0;3,0[ . У цей діапазон потрапляють анар- хічно-центричні ( 5,00  ), нейтральна ( 5,0 ) та автократично- центричні ( 15,0  ) демократичні системи прийняття рішень. Аналіз графіка на рис. 8 показує, що анархічно-центричним системам необхідний більший період навчання для прийняття скоординованих рі- шень, ніж автократично-центричним. Для заданих початкових даних най- менший середній час навчання має автократично-центрична система з пара- метром 8,0 , значення якого вказує на те, що у ході формування колективного рішення стратегії гравців середнього рівня ієрархії на 80% визначаються стратегіями керівника і на 20% стратегіями підлеглих праців- ників. Ігрові моделі автократичної та анархічної систем, отримані з демокра- тичної системи для крайніх значень параметра  , не забезпечують коорди-  Рис. 8. Залежність періоду навчання гри від параметра   Рис. 9. Залежність коефіцієнта коорди- нації від параметра  П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 114 нації стратегій гравців. Для 1 кореневий гравець, а для 0 гравці най- нижчого рівня є ізольованими від інших гравців і вибирають змінні страте- гії: varroot nu , vari nu , ...,2,1n . У результаті це дезорганізує роботу ін- ших агентів відповідно автократичної або анархічної систем прийняття рішень. Для координації автократичної системи кореневий гравець повинен до- тримуватися постійної стратегії constroot  uun у часі ...,2,1n . Така стра- тегія задається ще до початку гри (догматичний центр), або може бути сфор- мована за взаємодії з агентами нижчого рівня у процесі навчання (колегіальний центр). Аналогічно для координації анархічної системи потрібна попередня домовленість між усіма агентами спільноти найнижчого рівня ієрархії const uui n , ...,2,1n (догматична спільнота), або наявність горизонталь- них зв’язків між агентами спільноти з можливістю навчання агентів у ході гри. Значний вплив на координацію рішень гравців має розмірність стохас- тичної гри, яка визначається кількістю гравців та кількістю їх чистих стра- тегій. Залежність періоду n навчання (середньої кількості кроків гри), необ- хідного для досягнення коефіцієнта узгоджених рішень 9,0nK , від кіль- кості агентів 12  mL , організованих у вигляді симетричного бінарного дерева прийняття рішень з ,...2,1m рівнями зображено на рис. 10, а від кількості чистих стратегій N для усіх вище розглянутих видів ієрархічних систем прийняття рішень за відсутності дії завад — на рис. 11. Номери гра- фіків відповідають таким ієрархічним системам: 1 — демократична ( 5,0 ), 2 — догматична автократична, 3 — автократична з колегіальним центром, 4 — анархічна з догматичною спільнотою, 5 — анархічна з гори- зонтальними зв’язками на найнижчому рівні ієрархії у вигляді повно- зв’язного мультиграфу. Як видно з рис. 10 та 11, зростання кількості гравців та їх чистих стра- тегій призводить до збільшення періоду навчання усіх видів ієрархічних стохастичних ігор. Рис. 10. Залежність періоду навчання гри від кількості агентів Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 115 Час збіжності ігрового процесу прийняття рішень в ієрархічних систе- мах залежить від того, які домовленості прийнято в системі перед початком гри. Чим більше агентів мають початкове узгоджене рішення, тим менший час навчання системи. Те, що анархічна система з догматичною спільнотою (графік 4) має найменший час вироблення рішення (час навчання) визнача- ється початковими умовами — усі 12 m агентів найнижчого рівня (половина від загальної кількості агентів) мають узгоджені (однакові) рішення ще до початку гри. Зі збільшенням кількості зв’язків між агентами зростає кількість станів ієрархічної системи, які використовуються для випадкового пошуку опти- мальних рішень і, відповідно, зростає час такого пошуку. У зв’язку з цим автократична система (графіки 2 та 3) є ефективнішою від демократичної системи (графік 1), догматична автократична система (графік 2) буде ефек- тивнішою від автократичної системи з колегіальним центром (графік 3), а анархічна система з догматичною спільнотою (графік 4) — ефективнішою від анархічної системи з горизонтальними зв’язками (графік 5) між агентами найнижчого рівня ієрархії. Період навчання стохастичної гри залежить від коефіцієнта координації ]1,0(nK , який задає потрібну частку гравців з узгодженими рішеннями. Залежність періоду навчання від коефіцієнта координації для різних видів ієрархічних систем за відсутності дії завад зображено на рис. 12. Рис. 11. Залежність періоду навчання гри від кількості стратегій агентів Рис. 12. Залежність періоду навчання гри від коефіцієнта координації П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 116 Як видно з рис. 12, зі зростанням вимог до ступеня координації ієрархіч- них систем зростає період їх навчання, причому зберігається порядок ран- жування систем за швидкістю збіжності стохастичної гри так, як це зобра- жено на рис. 10 та 11. Крім розмірності гри, на швидкість збіжності ігрового методу вплива- ють його параметри  та  , співвідношення яких повинні задовольняти фундаментальні умови стохастичної апроксимації [18–20]. Залежність пері- оду навчання гри n від параметрів  та  зображено на рис. 13, а залеж- ність коефіцієнта координації від цих параметрів — на рис. 14. Результати отримано для демократичної системи з параметром 5,0 за відсутності завад. Зростання параметра ]1;0( призводить до зменшення кроку на- вчання стохастичної гри (кроку зміни ймовірностей вибору чистих страте- гій). Зменшення параметра ]1;0( сповільнює швидкість розширення  -симплексу, що є додатковим фактором обмеження кроку навчання. Ре- зультатом цього є зменшення коефіцієнта координації та збільшення пері- оду навчання стохастичної гри. Для заданих параметрів ігрового методу мінімальна кількість кроків навчання стохастичної гри, яка забезпечує координацію понад 90% гравців, досягається для ]1,0;0( та 1 . Вплив випадкових завад у вигляді білого шуму з дисперсією d на пе- ріод n навчання стохастичної гри для різних видів ієрархічних систем зо- бражено на рис. 15. =0,5 =1  Рис. 13. Залежність періоду навчання гри від параметрів ігрового методу =0,5 =1  Рис. 14. Залежність коефіцієнта координації від параметрів ігрового методу Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання … Системні дослідження та інформаційні технології, 2019, № 4 117 Дія завад призводить до спотворення потоків даних між рівнями ієрар- хії системи прийняття рішень. Відповідно зі зростанням дисперсії завади збільшується період вироблення скоординованого колективного рішення в ієрархічній системі. Позитивним фактором практичної реалізації розглянутого ігрового ал- горитму внаслідок дії завад є забезпечення координації автократичної сис- теми прийняття рішень з недогматичним центром ( 1 , varroot nu , ...,2,1n ). Дія білого шуму зумовлює диференціацію елементів вектора змішаних стратегій гравців і за рахунок підсилювальної властивості ре- курентного методу кореневий гравець навчиться вибирати одну із чистих стратегій ( constrootroot  uun , ...,2,1n ) з близькою до 1 імовірністю. У ре- зультаті проведення самонавчальної стохастичної гри автократична система з недогматичним центром вийде на консенсусне рішення. ВИСНОВКИ Проведені експериментальні дослідження підтверджують збіжність стохас- тичної гри для координації рішень в ієрархічних системах. Аналіз результа- тів комп’ютерного моделювання дозволяє зробити такі узагальнення: 1. Розроблений алгоритм та виконане на його основі комп’ютерне мо- делювання стохастичної гри забезпечують узгоджене прийняття рішень в ієрархічних системах за рахунок вирівнювання стратегій гравців на основі збирання поточної інформації та її адаптивного опрацювання. 2. Час збіжності стохастичної гри визначається розмірністю ієрархічної системи (кількістю учасників прийняття рішення і кількістю чистих страте- гій гравців) та співвідношенням параметрів ігрового методу. Оптимізація параметрів ігрового методу за обмежувальної дії фундаментальних умов стохастичної апроксимації забезпечує близький до 1 степеневий порядок швидкості збіжності. 3. Достовірність результатів забезпечується належним плануванням комп’ютерного експерименту та підтверджується повторювальністю зна- чень характеристик стохастичної гри, отриманих у ході імітаційного моде- лювання для різних послідовностей випадкових величин. 4. Виконані у цій роботі дослідження можна розвинути в напрямі мо- делювання ресурсних обмежень на інформаційні потоки між рівнями Рис. 15. Вплив завад на період збіжності стохастичної гри П.О. Кравець ISSN 1681–6048 System Research & Information Technologies, 2019, № 4 118 ієрархії і врахування відновлювальних відмов агентів для вивчення надій- ності та гнучкості ієрархічних систем прийняття рішень. ЛІТЕРАТУРА 1. Hierarchies in Distributed Decision Making / Christoph Schneeweiss. — Springer, 2013. — 341 p. 2. Недашківська Н.І. Методологія та інструментарій підтримки прийняття рішень на основі ієрархічних та мережевих моделей: дис. … доктора техн. наук: 01.05.04 / Н. І. Недашківська. — К.: ННК «ІПСА» НТУУ «КПІ», 2018. — 407 с. — [Електрон. ресурс]. — Режим доступу: http://ela.kpi.ua/bitstream/ 123456789/25119/1/Nedashkivska_diss.pdf. 3. Кравець П.О. Ігрова модель прийняття рішень в ієрархічних системах / П.О. Кравець // Інформаційні системи та мережі: вісн. НУ «Львівська політехніка». — 2017. — № 872. — С. 111–120. 4. Кравець П.О. Ігрова модель системи з авторитарним прийняттям рішень / П.О. Кравець // Інформаційні системи та мережі: вісн. НУ «Львівська політехніка». — 2018. — № 901. — С. 61–67. 5. Гермейер Ю.Б. Игры с непротивоположными інтересами / Ю.Б. Гермейер. — М.: Наука, 1976. — 328 с. 6. Harrington J. E., Jr. Games, Strategies, and Decision Making / J.E. Harrington, Jr. — Worth Publishers, 2014. — 540 p. 7. Grabisch M. Set Functions, Games and Capacities in Decision Making / M. Grabisch. — Springer, 2016. — 473 p. — DOI: 10.1007/978-3-319-30690-2. 8. Ummels M. Stochastic Multiplayer Games: Theory and Algorithms / M. Ummels. — Amsterdam University Press, 2014. — 174 p. 9. Petrosjan L.A. Game Theory and Application / L.A. Petrosjan, V.V. Mazalov. — Nova Science Publishers, 2002. — 295 p. 10. Ungureanu V. Pareto-Nesh-Stackelberg Game and Control Theory: Intelligent Para- digms and Applications / V. Ungureanu. — Springer, 2018. — 343 p. 11. Wooldridge M. An Introduction to Multiagent Systems / M. Wooldridge. — John Wiley & Sons, 2009. — 461 p. 12. Radley N. Multi-Agent Systems – Modeling, Control, Programming, Simulations and Applications / N. Radley. — Scitus Academics LLC, 2017. — 284 p. 13. Iterative Learning Control for Multi-agent Systems Coordination / S. Yang, J.-X. Xu, X. Li, D. Shen. — John Wiley & Sons, 2017. — 272 p. 14. Sun Z. Cooperative Coordination and Formation Control for Multi-agent Systems / Zhiyong Sun. — Springer, 2018. — 179 p. 15. Agent for Games and Simulations: Trends in Techniques, Concepts and Design / F. Dignum, J.Bradshaw, B. G. Silverman, W. van Doesburg. — Springer, 2009. — 237 p. 16. Bekker K. The Guide to Computer Simulation and Games / K. Bekker, J.R. Parker. — John Wiley and Sons, 2011. — 456 p. 17. Simulation of Decision-Making as Active Learning Tools: Design and Effects of Po- litical Science Simulations / P.Bursens, V. Donche, D. Gijbels, P. Spooren (Edi- tors). — Springer, 2018. — 206 p. 18. Назин А.В. Адаптивный выбор вариантов / А.В. Назин, А.С. Позняк. — М.: Наука, 1986. — 288 с. 19. Kushner H. Stochastic Approximation and Recursive Algorithms and Applications / H. Kushner, G. G. Yin. — Springer Science & Business Media, 2013. — 417 p. 20. Benveniste A. Adaptive Algorithms and Stochastic Approximations / A. Benveniste, M. Metivier, P. Priouret. — Springer Science & Business Media, 2012. — 365 p. Надійшла 07.06.2019
id journaliasakpiua-article-188564
institution System research and information technologies
keywords_txt_mv keywords
language Ukrainian
last_indexed 2025-07-17T10:26:37Z
publishDate 2019
publisher The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format ojs
resource_txt_mv journaliasakpiua/e9/ff19ef5e413d129edb50cad848d52ae9.pdf
spelling journaliasakpiua-article-1885642020-03-02T17:05:10Z Game strategies for decision making in hierarchical systems. II. Computer simulation of stochastic game Игровые стратегии принятия решений в иерархических системах. II. Компьютерное моделирование стохастической игры Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри Kravets, Petro A. decision making hierarchical system conditions of uncertainty stochastic game computer modelling прийняття рішень ієрархічна система умови невизначеності стохастична гра комп’ютерне моделювання принятие решений иерархическая система условия неопределенности стохастическая игра компьютерное моделирование An algorithm for solving a stochastic game for decision making in hierarchical systems under uncertainty is developed. An analysis of the results of computer modeling of a stochastic game for autocratic, anarchic and democratic hierarchical decision making systems with the binary tree structure is performed. It has been established that autocratic-centric hierarchical systems have the smallest training time for achieving a close-to-consensus solution. The influence of parameters on the convergence of the game method in the process of finding a consensus or a majoritarian collective solution is studied. Разработан алгоритм решения стохастической игры для принятия решений в иерархических системах в условиях неопределенности. Выполнен анализ результатов компьютерного моделирования стохастической игры для автократической, анархической и демократической иерархических систем принятия решений со структурой бинарного дерева. Установлено, что наименьший период обучения для достижения близкого к консенсусному решению имеют автократически-центричные иерархические системы. Изучено влияние параметров на сходимость игрового метода в процессе поиска консенсусного или мажоритарного коллективного решения. Розроблено алгоритм розв’язування стохастичної гри для прийняття рішень в ієрархічних системах в умовах невизначеності. Виконано аналіз результатів комп’ютерного моделювання стохастичної гри для автократичної, анархічної та демократичної систем прийняття рішень зі структурою бінарного дерева. Установлено, що найменший період навчання для досягнення близького до консенсусного рішення мають автократично-центричні ієрархічні системи. Вивчено вплив параметрів на збіжність ігрового методу у процесі пошуку консенсусного або мажоритарного колективного рішення. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-12-23 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/188564 10.20535/SRIT.2308-8893.2019.4.11 System research and information technologies; No. 4 (2019); 105-118 Системные исследования и информационные технологии; № 4 (2019); 105-118 Системні дослідження та інформаційні технології; № 4 (2019); 105-118 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/188564/190161 Copyright (c) 2021 System research and information technologies
spellingShingle прийняття рішень
ієрархічна система
умови невизначеності
стохастична гра
комп’ютерне моделювання
Kravets, Petro A.
Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title_alt Game strategies for decision making in hierarchical systems. II. Computer simulation of stochastic game
Игровые стратегии принятия решений в иерархических системах. II. Компьютерное моделирование стохастической игры
title_full Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title_fullStr Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title_full_unstemmed Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title_short Ігрові стратегії прийняття рішень в ієрархічних системах. ІІ. Комп’ютерне моделювання стохастичної гри
title_sort ігрові стратегії прийняття рішень в ієрархічних системах. іі. комп’ютерне моделювання стохастичної гри
topic прийняття рішень
ієрархічна система
умови невизначеності
стохастична гра
комп’ютерне моделювання
topic_facet decision making
hierarchical system
conditions of uncertainty
stochastic game
computer modelling
прийняття рішень
ієрархічна система
умови невизначеності
стохастична гра
комп’ютерне моделювання
принятие решений
иерархическая система
условия неопределенности
стохастическая игра
компьютерное моделирование
url https://journal.iasa.kpi.ua/article/view/188564
work_keys_str_mv AT kravetspetroa gamestrategiesfordecisionmakinginhierarchicalsystemsiicomputersimulationofstochasticgame
AT kravetspetroa igrovyestrategiiprinâtiârešenijvierarhičeskihsistemahiikompʹûternoemodelirovaniestohastičeskojigry
AT kravetspetroa ígrovístrategííprijnâttâríšenʹvíêrarhíčnihsistemahííkompûternemodelûvannâstohastičnoígri

Ähnliche Einträge