Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри
A mathematical model of a stochastic game for decision making in hierarchical systems under uncertainty conditions is developed. The essence of the game consists in aligning the players' pure strategies to achieve a consensus or a majoritarian collective solution. The parameterization of the ga...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| 1. Verfasser: | |
| 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/163589 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1866302306916499456 |
|---|---|
| author | Kravets, Petro A. |
| author_facet | Kravets, Petro A. |
| author_sort | Kravets, Petro A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-12-13T15:15:18Z |
| description | A mathematical model of a stochastic game for decision making in hierarchical systems under uncertainty conditions is developed. The essence of the game consists in aligning the players' pure strategies to achieve a consensus or a majoritarian collective solution. The parameterization of the game model for the separation of the autocratic, anarchic, and democratic hierarchical structures of decision-making systems is carried out. A Markov recurrent method for solving a stochastic game based on a stochastic approximation of the complementary slackness condition has been developed. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2019.3.06 |
| first_indexed | 2025-07-17T10:24:29Z |
| format | Article |
| fulltext |
П.О. Кравець, 2019
Системні дослідження та інформаційні технології, 2019, № 3 63
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 004.852; 004.942
DOI: 10.20535/SRIT.2308-8893.2019.3.06
ІГРОВІ СТРАТЕГІЇ ПРИЙНЯТТЯ РІШЕНЬ
В ІЄРАРХІЧНИХ СИСТЕМАХ. І. МАТЕМАТИЧНА МОДЕЛЬ
СТОХАСТИЧНОЇ ГРИ
П.О. КРАВЕЦЬ
Анотація. Розроблено математичну модель стохастичної гри для прийняття
рішень в ієрархічних системах в умовах невизначеності. Суть гри полягає у
вирівнюванні чистих стратегій гравців для досягнення консенсусного або ма-
жоритарного колективного рішення. Виконано параметризацію ігрової моделі
для відокремлення автократичної, анархічної та демократичної ієрархічних
структур систем прийняття рішень. Розроблено марковський рекурентний ме-
тод розв’язування стохастичної гри на основі стохастичної апроксимації умови
доповняльної нежорсткості.
Ключові слова: прийняття рішень, ієрархічна система, умови невизначеності,
стохастична гра, математична модель.
ВСТУП
Ієрархічна структура прийняття рішень використовується у багатьох розпо-
ділених системах, наприклад, біологічних, інформаційних, штучного інтеле-
кту, економічних, соціальних, у військовому та державному управлінні. По-
пулярність ієрархічної організації обумовлена необхідністю декомпозиції
процесу прийняття рішень у зв’язку з інтегральною складністю таких сис-
тем — великою розмірністю, наявністю численних горизонтальних та вер-
тикальних зв’язків між елементами, пріоритетністю у прийнятті рішень
окремими підсистемами, відсутністю адекватної моделі системи, наявністю
декількох синергетичних або конкурентних цілей розвитку підсистем, гете-
рогенністю складових елементів, неповнотою інформаційного опису
об’єктів тощо [1–7].
Ієрархічні системи складаються з активних елементів, інакше — агентів
[8, 9], здатних приймати автономні рішення та функціонально пов’язаних
між собою за відношенням старшинства. У таких системах виникає потреба
у прийнятті скоординованих колективних рішень для досягнення поставле-
них цілей або для виведення системи на потрібний режим функціонування.
Прийняття скоординованих колективних рішень в ієрархічних системах
є актуальною науково-практичною проблемою [10–13]. Загалом її
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 64
розв’язування спрямоване на оптимізацію техніко-економічних показників
функціонування системи: підвищення точності та оперативності прийнятих
рішень; синхронізацію керувальних впливів між підсистемами з різною інер-
ційністю вироблення та опрацювання рішень; забезпечення стійкості рішень
до впливу зовнішніх факторів; підвищення надійності роботи системи;
зменшення витрат часу та ресурсів на організацію керування ієрархічною
системою [10].
В ієрархічних системах рішення приймаються здебільшого в умовах
цільової, функціональної, комбінаторної або стохастичної невизначеності
[2, 14]. У зв’язку з цим виникає потреба у розробленні адаптивних методів
прийняття рішень, здатних у процесі самонавчання хоча б частково компен-
сувати існуючу невизначеність та cформувати стратегії поведінки з очіку-
ваним оптимальним результатом.
Процес ієрархічного прийняття рішень спрямований на досягнення спіль-
ної колективної мети усієї системи і окремих, можливо конкурентних, цілей
її підсистем. Прийняття збалансованих колективних рішень вивчається
теорією ігор [15], а в умовах невизначеності — теорією стохастичних ігор
[16–19].
Об’єктом цього дослідження є процеси ігрового прийняття рішень в
умовах невизначеності. Предметом дослідження є ігрова модель прийняття
рішень в ієрархічно організованих системах. Метою роботи є розв’язування
стохастичної гри для прийняття рішень в ієрархічній системі. Наукова нови-
зна роботи полягає у розробленні математичної моделі та застосуванні адап-
тивного методу розв’язування стохастичної гри для прийняття рішень в іє-
рархічній системі в умовах невизначеності. Практична цінність виконаного
дослідження визначається можливістю застосування отриманих результатів
для побудови ефективних організаційних, інформаційних та кібернетичних
систем з ієрархічною структурою.
ПРОБЛЕМА ПРИЙНЯТТЯ РІШЕНЬ В ІЄРАРХІЧНИХ СИСТЕМАХ
Функції прийняття рішень в ієрархічних системах розподілені між агентами
різних рівнів. Агент середнього рівня, опрацьовуючи рішення агента вищого
рівня, виробляє власне рішення і доводить його до відома агентів нижчого
рівня, які перебувають у його прямому підпорядкуванні.
В ієрархічній системі наявні вертикальні (між різними рівнями підпо-
рядкування) та горизонтальні (на одному рівні ієрархії) зв’язки між підсис-
темами. Дії вищих та нижчих рівнів ієрархічної структури є взаємозалежни-
ми. Рішення підсистем вищого рівня домінує над діями підсистем нижчого
рівня. У межах наданих повноважень рішення окремих агентів середніх рів-
нів ієрархічної системи є автономними в управлінні підлеглими агентами.
Як правило, агенти вищого рівня вирішують стратегічні, а підпорядковані їм
агенти — тактичні завдання, що сприяє підвищенню точності та оператив-
ності прийняття рішень [1].
Успішність колективного вироблення рішень в ієрархічних системах
забезпечується координацією дій усіх учасників прийняття рішень [9–12].
Координація — це зведення дій агентів до певної відповідності для досяг-
нення узгодженої, упорядкованої роботи всіх ланок системи прийняття рі-
шень. У вузькому розумінні, прийнятому у цій роботі, координація полягає
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 65
у вирівнюванні чистих стратегій гравців ієрархічної системи у ході прове-
дення динамічної стохастичної гри. Тобто колективне рішення буде вважа-
тися сформованим, якщо його обрали всі (консенсусне рішення) або більша
частина учасників системи прийняття рішень (мажоритарне рішення).
Координація може бути централізованою або децентралізованою. У сис-
темах з централізованою координацією функції прийняття рішень концент-
руються на найвищому рівні ієрархії, а у системах з децентралізованою ко-
ординацією — делегуються на нижчі рівні ієрархії. Ряд дослідників
активних розподілених систем вважають, що для ефективного прийняття
рішень необхідний баланс між централізованою і децентралізованою коор-
динацією, але зі зростанням структурної та функціональної складності роз-
поділеної системи щодо оперативності, надійності та економічної ефектив-
ності розв’язування задачі доцільнішими будуть методи децентралізованої
координації агентів [12, 13].
Координація необхідна для узгодження індивідуальних цілей і варіан-
тів поведінки агентів, які забезпечують досягнення оптимальних колектив-
них рішень. Колективні рішення є скоординованими, якщо вони задоволь-
няють вимоги вигідності, стійкості та справедливості для всіх учасників
прийняття рішень. Вигідність колективного рішення полягає в тому, що ко-
жен агент покращує або не погіршує значення своєї функції корисності, а
система в цілому покращує якість розв’язування загального завдання. Мож-
ливо, діючи самостійно або в інших умовах, агент досягнув би кращих для
себе результатів, але система накладає обмеження на значення його виграшу
на користь усіх учасників прийняття рішень. Певний компроміс між агента-
ми забезпечує виграш колективу в цілому. Стійкість колективного рішення
полягає в тому, що відхилення стратегії поведінки одного або групи агентів
від оптимального колективного рішення не зможе підвищити значення їх
функцій корисності. Справедливість колективного рішення полягає у тому,
що кожен агент отримує свою частку виграшу, обумовлену значенням його
платіжної функції.
На практиці найбільш поширені критерії рівноваги за Нешем, Слейте-
ром, Джофріоном, Байєсом, корельованої рівноваги, оптимальності за
Парето.
Методологічні засади колективного прийняття рішень в ієрархічних
системах закладені в теорії керування, теорії автоматів, теорії оптимального
планування, дослідження операцій, теорії активних систем [20], теорії вибо-
ру варіантів рішень [21, 22], теорії ігор [23–29], теорії мультиагентних сис-
тем [8, 9, 11], інформаційній теорії ієрархічних систем [5–7].
Основним методом досліджень ієрархічних систем є теоретико-ігрове
моделювання [2, 23, 24], яке дозволяє передбачити поведінку агентів та об-
рати способи управління, які переводять систему в оптимальні стани згідно
з обраними критеріями функціонування.
Ігри з прийняття рішень в ієрархічних системах є підкласом ігор на ме-
режах [25], серед яких можна виокремити такі: безкоаліційні або коаліційні;
некооперативні та кооперативні; антагоністичні та неантагоністичні; з ну-
льовою сумою та довільною сумою; ігри з природою та багатьох осіб; дис-
кретні та неперервні; одноетапні та повторювальні; нерефлексивні та рефле-
ксивні; з повною та неповною інформованістю гравців; детерміновані або
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 66
стохастичні; з постійною або змінною структурою; з фіксованими (програм-
ними) або динамічними стратегіями поведінки гравців; з наявною або відсу-
тньою інформованістю гравців про обрані стратегії та результати ходів гри;
з неперервним або дискретним часом; з обмеженим або безмежним часом; з
повною або локальною залежністю платіжних функції від стратегій гравців;
з інтегральною у часі або миттєвою залежністю функцій виграшів від стра-
тегій гравців; зі скалярними або векторними (або інтервальними) платежа-
ми; з наявністю або відсутністю обмежень на дії окремих гравців чи під-
множин гравців; із синхронним (одночасним) або асинхронним вибором
стратегій; ігри в нормальній формі та ігри з правом першого ходу.
Теорія ігор у нормальній формі оформилась у самостійну математичну
дисципліну в першій половині ХХ ст. після виходу фундаментальних праць
Дж. фон Неймана та О. Моргенштерна. Вивчення ієрархічних ігор з правом
першого ходу започатковано у працях Ю.Б. Гермейєра та його послідов-
ників.
На відміну від гри у нормальній формі, яка характеризується одночас-
ністю вибору дій усіма гравцями та незалежністю вибору одного гравця від
вибору інших, в ієрархічних іграх виділяють центрального гравця, який ро-
бить перший хід, та гравців, які вибирають свої дії на основі відомого їм рі-
шення центру.
Розв’язком гри є ситуація рівноваги, від якої невигідно відмовлятися ні
центру, ні агентам нижчих рівнів. Колективний розв’язок ієрархічної гри з
правом першого ходу описується рівновагою за Штакельбергом [23, 28],
яка реалізовується, якщо агент вибирає дію, максимізуючи свій виграш за
відомої йому на момент прийняття рішення дії центру, а центр, знаючи про
таку поведінку агента, вибором власної дії максимізує свій виграш, вважаю-
чи заданою реакцію агента на свої дії. Максимізуючи свій виграш, центр
сподівається на доброзичливість агента, тобто на те, що агент з множини
рівнозначних для нього дій вибере сприятливу для центру дію. У літератур-
них джерелах з цієї проблеми в основному подаються результати дослі-
дження детермінованих ієрархічних ігор в умовах повної інформації. Для
таких ігор характерне використання максимального гарантованого результа-
ту як основної концепції розв’язування гри [23, 24].
У реальних умовах процес прийняття рішень в ієрархічних системах
містить елементи невизначеностей, викликаних нечітко сформульованими
цілями, семантичною неоднозначністю мовних повідомлень, спотвореннями
передавання потоків інформації між елементами системи, комбінаторною
складністю системи, внутрішньою стохастичністю, пов’язаною із незалеж-
ним вибором агентами можливих варіантів дій, неконтрольованими зовніш-
німи впливами. Невизначеність прийняття рішень в ієрархічній системі мо-
же бути зумовлена тим, що проблема прийняття рішень на верхньому рівні
менш структурована та формалізована; підсистемі вищого рівня можуть бу-
ти не повністю відомі цілі та обмеження підсистем нижчих рівнів; керівники
та підрозділи нижчих рівнів, як правило, ознайомлені тільки зі своїм функ-
ціональним завданням і не завжди знають про загальні цілі системи; можуть
бути спотворення та втрата інформації у разі її передавання між рівнями іє-
рархії; невідповідність періодів планування рішень – періоди прийняття рі-
шень для агентів верхнього рівня більші, ніж для агентів нижчих рівнів; не-
відповідність періодів імплементації рішень – керовані підсистеми є більш
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 67
інерційними щодо реалізації рішень порівняно з підсистемами верхніх рів-
нів; наявність непередбачених, наприклад, ресурсних обмежень на процеси
функціонування підсистем; зростання кількості рівнів ієрархії та кількості
варіантів можливих рішень призводить до зростання ентропії ієрархічної
системи; агенти верхнього рівня ієрархії мають у підпорядкуванні більші
підсистеми з великою кількістю станів функціонування, перехід у які не
можна спрогнозувати апріорі [1, 14, 24].
Для ігрового розв’язування задачі прийняття рішень в умовах парамет-
ричної невизначеності необхідно використати адаптивні стратегії, які ком-
пенсують невизначеність платежів їх стохастичною ідентифікацією у ході
гри за рахунок самонавчання агентів [22]. Стохастичні ігри були винайдені
Л. С. Шеплі на початку 50-х років ХХ ст. Ігрові задачі адаптивного вибору
варіантів рішень започатковано у працях В. І. Варшавського, М. Л. Цетліна
з теорії колективної поведінки автоматів у випадкових середовищах. Стоха-
стичні ігри (ігри з природою, двох та багатьох осіб) у змішаних стратегіях
на основі методу стохастичної апроксимації, проекції градієнта та регуляри-
зації вивчено у працях Я.З. Ципкіна, А.В. Назіна, А.С. Позняка. Різноманітні
математичні моделі стохастичних систем на основі методів стохастичної
оптимізації та рекурентного оцінювання запропоновано і розвинуто у пра-
цях наукової школи академіка НАНУ В. С. Королюка.
У фахових літературних джерелах з цієї проблеми в основному дослі-
джуються повнозв’язні стохастичні ігри [16, 22]. Ігри з локальними
зв’язками між гравцями – ігри на неповнозв’язних графах, деревах, актуаль-
ні для моделювання процесів прийняття рішень в умовах невизначеності в
організаційних та ергатичних (людино-машинних) системах потребують
різностороннього та поглибленого вивчення.
ПОСТАНОВКА ІГРОВОЇ ЗАДАЧІ
Ідеалізовану структуру ієрархічної системи прийняття рішень можна зобра-
зити у вигляді дерева, вузли якого позначають агентів прийняття рішень, а
орієнтовані зв’язки між ними — залежність від стратегій рішень сусідніх
агентів. Будемо вважати, що всі рішення вищого рівня є рекомендаційними і
не обмежують свободу вибору агентів нижчого рівня. Завдяки цьому поточ-
ні рішення агентів нижчого рівня можуть відрізнятися від рішень агентів
вищого рівня. Агент з найвищим рангом (корінь дерева) приймає рішення на
основі власних стратегій та стратегій агентів безпосереднього нижчого рів-
ня. Рішення агентів середнього рівня залежать від власних стратегій та стра-
тегій агентів вищого і нижчого рівнів. Формування рішень агентами найни-
жчого рівня (листя дерева) визначається власними стратегіями та
стратегіями агентів безпосереднього вищого рівня.
Нехай D — організована у вигляді дерева множина гравців ( 2|| D —
кількість гравців), які здійснюють незалежний вибір варіантів рішень
з множини )}(...,),2(),1({ i
iiii NuuuU чистих стратегій Di у дискретні
моменти часу ,...2,1n .
Після завершення вибору варіантів рішень iii
n Uuu усіма гравцями
кожен з них отримує комплексний штраф за недотримання рекомендаційних
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 68
рішень. Штраф гравця середнього рівня визначається недотриманням керів-
ного рішення свого безпосереднього начальника та невиконанням його вла-
сного рішення підлеглими гравцями:
n
kDj
j
n
i
n
k
n
i
ni
D
n
i
n
i
i uuuuDu
}{\
1 ||)1(||||)( i D , (1)
де DDi — множина сусідніх гравців, стратегії яких визначають втрати
i -го гравця; j
Dj
DD
n UUu
i
ii
— колективна стратегія множини гравців
iD ; 1Rui
n — числовий еквівалент варіанта рішення; k — гравець вищого
рівня (керівник); i — гравець середнього рівня; j — гравець нижчого рів-
ня; ]1,0[ — ваговий коефіцієнт (для кореневого гравця 0 , а для грав-
ців найнижчого рівня 1 ); ),0(~ dNormaln — нормально-розподілена
випадкова величина з нульовим математичним сподіванням та дисперсією
0d або значення білого гауссівського шуму, який моделює вплив завад на
канали зв’язку між ігровими агентами.
Зроблено припущення, що випадкові програші }{ i
n гравців є неза-
лежними Uun , Di , ...,2,1n , мають постійне математичне споді-
вання const)()}({ ii DDi
n uvuE та обмежений другий момент
)(})]({[sup 22 ii DDi
n
n
uuE . Стохастичні характеристики випадкових
програшів не відомі гравцям апріорі.
Середні програші гравців після n кроків гри набудуть значення:
Di
n
u
n
t
i
t
D
n
i
n
i
1
})({
1
. (2)
Метою ієрархічної системи є вироблення узгодженого колективного
рішення, яке мінімізує функції середніх програшів гравців (2):
Di
i
nu
i
n
n
minlim
}{
. (3)
Отже, ігрова задача вибору варіантів рішень полягає у тому, що на ос-
нові спостереження поточних програшів }{ i
n у моменти часу ...,2,1n гра-
вці повинні навчитися вибирати чисті стратегії }{ i
nu так, щоб забезпечити
виконання системи цілей (3).
Залежно від методу формування послідовностей стратегій Diui
n }{
розв’язки ігрової задачі повинні задовольняти хоча б одну з умов колектив-
ної оптимальності, наприклад, Неша, Парето або іншу [27, 28].
ВИДИ ІЄРАРХІЧНИХ СИСТЕМ ПРИЙНЯТТЯ РІШЕНЬ
Параметр ]1,0[ у виразі (1) визначає переважання одноосібного чи гру-
пового способу вироблення рішення. Залежно від цього визначимо такі різ-
новиди ієрархічних систем прийняття рішень:
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 69
1 — автократична система;
0 — анархічна система;
10 — демократична система.
Слід зазначити, що прийняті в цій роботі назви ієрархічних систем є
умовними і повною мірою не відображають їх соціально-політичне або інше
відоме трактування.
Приклади деревоподібних структур відповідних ієрархічних систем зо-
бражено на рисунку. Вузли мультиграфів позначають гравців, а орієнтовані
дуги — вплив стратегій на формування втрат (програшів) гравців.
В автократичній системі прийняття рішень втрати гравців середнього
та найнижчого рівнів визначаються лише власними стратегіями та стратегі-
ями гравців вищого рівня (рисунок, a). Втрати кореневого гравця визнача-
ються тільки власними стратегіями або додатково стратегіями сусідніх грав-
ців (в автократичних системах з колегіальним центром).
Структура прийняття рішень в автократичній системі є вертикально-
ієрархічною. Потік інформації спрямований згори вниз. Рішення приймає
керівник найвищого рівня. Можливість прийняття рішень на нижчих рівнях
є обмеженою. Прийняті на верхніх рівнях ієрархії рішення надходять на ниж-
чі рівні як директиви, які не підлягають обговоренню і обов’язкові до вико-
нання.
Системи з авторитарним управлінням ефективні у надзвичайних та
кризових ситуаціях. Позитивними аспектами в організації автократичної
системи є оперативність прийняття рішень, висока виконавча дисципліна та
висока мобільність. Негативний аспект — низька ініціатива низових ланок.
В анархічній системі прийняття рішень втрати гравців найвищого та
середнього рівнів визначаються стратегіями гравців нижчого рівня та влас-
ними стратегіями (рисунок, б). Втрати гравців найнижчого рівня визнача-
ються лише власними стратегіями, або додатково стратегіями інших гравців
найнижчого рівня (в анархічних системах з узгодженням рішень).
Ідеально анархічна організація заперечує наявність ієрархії. В анархіч-
ній спільноті в основному наявні горизонтальні зв’язки. Рішення прийма-
ється шляхом широкого обговорення завдань на найнижчому рівні. Верти-
кальні зв’язки можуть формуватися делегуванням мінімальних повноважень
на вищий рівень для узгодження рішення між окремими самоорганізовани-
ми спільнотами. У таких анархічних системах потік інформації спрямований
знизу вгору.
Структури ієрархічних систем прийняття рішень: а — автократичної;
б — анархічної; в — демократичної
а б в
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 70
Процес вироблення рішення в анархічній системі може займати трива-
лий час. Така система може бути дієвою у разі виокремлення у ній окремих
спільнот, здатних до самоорганізації та самоконтролю.
У демократичній системі прийняття рішень утрати гравців середнього
рівня визначаються власними стратегіями та стратегіями гравців як вищого
рівня, так і нижчого (рисунок, в). Утрати кореневого гравця визначаються
власними стратегіями та стратегіями гравців нижчого рівня. Утрати гравців
найнижчого рівня визначаються власними стратегіями та стратегіями грав-
ців вищого рівня.
Демократична система ґрунтується на колегіальному прийнятті рішень
керівниками всіх рівнів з можливим урахуванням думок підлеглих делегу-
ванням (у разі потреби) їм частини повноважень та залученням вузьких спе-
ціалістів для вироблення рішення. Потоки інформації спрямовані в обох на-
прямках — згори вниз та знизу вгору. Від вищого до нижчих рівнів
спрямовано потік керівних рішень. Зустрічний потік інформації породжений
делегуванням представницьких повноважень низових рівнів до вищих рівнів
ієрархії.
Демократична організація системи стимулює підлеглих до прийняття
самостійних рішень, але може призвести до низької виконавчої дисципліни
та невисокої мобільності у прийнятті рішень в екстремальних умовах.
Виділимо такі види демократичних систем, параметризованих коефіці-
єнтом )1,0( , з комбінованими властивостями анархічних та автократич-
них систем прийняття рішень:
15,0 — автократично-центрична демократична система (демо-
кратура, жорстка демократія);
5,00 — анархічно-центрична демократична система (ліберальна,
м’яка демократія);
5,0 — нейтральна демократична система (збалансована, чиста де-
мократія).
В автократично-центричних системах переважають процеси прийнят-
тя рішень на вищих рівнях ієрархії. Керівник найвищого рівня приймає са-
мостійні рішення, ураховуючи думку керівників низових підрозділів У та-
ких системах переважає потік інформації згори вниз.
В анархічно-центричних системах основні процеси прийняття рішень
здійснюються на нижчих рівнях ієрархії. Керівник найвищого рівня уникає
прийняття самостійних рішень, перекладає прийняття рішень та відпові-
дальність за них на керівників низових підрозділів. У таких системах пере-
важає потік інформації знизу вгору. Часто такий стиль керівництва дезорієнтує
роботу всієї системи. У ліберальній системі можуть самоорганізовуватись
групи ініціативних працівників «за інтересами», рішення яких доводяться до
відома керівництва.
За значенням коефіцієнта система нейтральної демократії перебу-
ває посередині між автократичною та анархічною системами. На прийняття
рішень працівниками середньої ланки чиниться збалансований вплив згори
від керівника та знизу від співробітників нижчої ланки.
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 71
МЕТОД РОЗВ’ЯЗУВАННЯ СТОХАСТИЧНОЇ ГРИ
Необхідні для розв’язування сформульованої ігрової задачі послідовності
варіантів рішень }{ i
nu отримаємо за допомогою динамічних векторів зміша-
них стратегій i
np Di , елементи яких є умовними ймовірностями вибору
чистих стратегій:
})1,...,2,1(,)({)( ntujuujp i
t
i
t
ii
n
i
n P , iNj ..1 ,
де )}1...,,2,1({ ntui
t — передісторія стратегій, вибраних гравцем з номе-
ром i ; )}1...,,2,1({ nti
t — передісторія отриманих за це програшів.
Змішані стратегії iNi
n Sp гравців набувають значень на одиничних
симплексах:
i
ii
N
j
NN jpRppS
1
1)(,| ,
де iNR — простір невід’ємних дійсних чисел, що має iN вимірів.
Поточні варіанти рішень i
nu Di будемо вибирати випадково на ос-
нові дискретного розподілу чистих стратегій гравців з імовірностями
)( i
n
i
n up :
j
k
i
i
n
j
ii
n Njkpjjuu
1
)..1()(minarg|)( , (4)
де ]1,0[ — випадкова величина з рівномірним розподілом.
Побудову методу розв’язування стохастичної гри виконаємо на основі
детермінованої матричної гри з матрицями програшів )]([ iDuv . Платіжна
функція детермінованої матричної гри є полілінійною функцією середніх
програшів:
iDiD iDj
i
ii
Uu uuDj
jjDiDi upuvpV
;
)()()( .
Відомо, що розв’язки гри за Нешем у змішаних стратегіях задовольня-
ють умову доповняльної нежорсткості [29]:
0)()( iii
i
DiNDi
p
pVepV Di ,
де
i
jii
Dj
NDD SSp — задані на опуклих симплексах iDS комбіновані
змішані стратегії гравців з локальних множин iD ; )( i
i
Di
p
pV — градієнт
полілінійної функції середніх програшів.
Щоб додатково врахувати розв’язки за Нешем у чистих стратегіях, ви-
конаємо покомпонентне зважування умови доповняльної нежорсткості еле-
ментами векторів змішаних стратегій:
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 72
0))()()((diag iii
i
DiNDi
p
i pVepVp Di , (5)
де )(diag ip — квадратна діагональна матриця порядку iN , побудована
з елементів вектора ip .
Пошук розв’язків ігрової задачі в умовах невизначеності будемо вико-
нувати у класі рекурентних марковських методів [22]:
ii Ni
n
i
n
i
nnn
i
n
N
n
i
+n Sx,p,uRp=p )}({11 Di , (6)
де iN
n 1 — перетворення, яке забезпечує належність вектора i
+np 1 до оди-
ничного симплексу iNS ; 0n — довжина кроку методу; iN
n RR )( —
вектор руху методу.
Вектор руху ігрового методу визначимо так, щоб у середньому він за-
довольняв модифіковану умову доповняльної нежорсткості (5):
}|])([{])[(diag}|{ ii
n
i
n
i
n
i
n
iNi
p
iii
nn pppueEVeVpppRM i
i , (7)
де iNi Sp ; {}E — функція математичного сподівання; )..1|1( ij
N Nje i
— вектор, всі компоненти якого дорівнюють 1; )( i
nue — одиничний вектор-
індикатор вибору чистої стратегії ii
n Uu .
Ураховуючи вирази (6) та (7), методом стохастичної апроксимації [30]
отримаємо таке рекурентне перетворення векторів змішаних стратегій
у часі:
]})([{
11
i
n
i
n
i
nn
i
n
Ni
n puepp i
n
, (8)
де i
n
N
1 — проектор на одиничний -симплекс ii
n
NN SS
1
; 0n — мо-
нотонно спадна послідовність додатних величин, яка регулює величину
кроку методу; 0n — монотонно спадна послідовність додатних величин,
яка регулює швидкість розширення -симплексу; 1Ri
n — поточний про-
граш гравця.
Оператор проектування на одиничний n -симплекс використано для
покращення статистичних характеристик зібраних даних про середовище
прийняття рішень, а параметр n — як додатковий елемент керування збіж-
ністю рекурентного методу. Цей оператор визначається такими умовами:
iii NNNi RqSpqpqp )( ,
де ii NN Sq )( . Проектор )(qiN
переводить точку iNRq у найближчу
до неї точку -симплексу iNS [22].
Стохастична гра розпочинається з ненавчених векторів змішаних стра-
тегій зі значеннями елементів i
i Njp /1)(0 , де iNj ..1 . У наступні момен-
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 73
ти часу динаміка векторів змішаних стратегій визначається марковським
рекурентним методом (8).
Збіжність змішаних стратегій (8) до оптимальних за Нешем значень (з
імовірністю 1 та у середньоквадратичному) визначається з фундаменталь-
них умов стохастичної апроксимації [22, 30], які можуть бути уточнені екс-
периментальним дослідженням.
За умови незалежності випадкових виграшів }{ i
n , незалежності вибо-
ру чистих стратегій }{ i
nu Di та виконання умов 0n , nn 1 ,
n
n , )min,0( 1
i
Di
n N , nn 1 метод (8) забезпечує виконання
умови доповняльної нежорсткості (5) у знакододатному середовищі
0min
iv Di з імовірністю 1, якщо
1
2
1 )|(|
n
nnn , та у середньо-
квадратичному, якщо 0)|(|lim 1
1
nnnn
n
. Результати отримано на
основі рекурентного оцінювання згори похибки виконання умови допов-
няльної нежорсткості, усередненої за передісторією подій на момент
часу n [17].
Порядок зменшення параметрів n та n впливатиме на швидкість
збіжності стохастичної гри. Ці параметри можуть бути обчислені так:
nn , nn ,
де 0 ; 0 , 0 ; 0 .
Стохастична гра складається з таких повторюваних кроків. У моменти
часу ,...2,1n кожен гравець Di на основі власної змішаної стратегії i
np
вибирає чисту стратегію i
nu (4), за що до моменту часу 1n отримує поточний
програш i
n (1), після чого обчислює змішану стратегію i
np 1 згідно
з методом (8). Динамічна перебудова змішаних стратегій на основі опрацю-
вання поточних програшів за обмежувальної дії умов стохастичної апрок-
симації забезпечує адаптивний вибір чистих стратегій, який з плином часу
зумовить отримання рівноважних за Нешем розв’язків.
ВИСНОВКИ
У роботі сформульовано актуальне науково-прикладне завдання координації
рішень в ієрархічних системах та отримано такі результати:
1. Виконано аналіз проблеми прийняття рішень в ієрархічних системах
в умовах невизначеності, що дозволило запропонувати стохастичні ігрові
стратегії для її розв’язування.
2. Запроваджено коефіцієнт залежності платіжних функцій гравців від
впливу елементів вищого та нижчого рівнів ієрархічної системи, що дало
змогу класифікувати ієрархічні системи з метою вивчення балансу одноосі-
бного та групового впливу гравців у процесі вироблення варіантів рішень.
П.О. Кравець
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 74
3. Розроблено математичну модель та запропоновано метод
розв’язування стохастичної гри, які забезпечують узгоджене прийняття рі-
шень в ієрархічних системах за рахунок вирівнювання стратегій гравців на
основі збирання поточної інформації та її адаптивного опрацювання.
ЛІТЕРАТУРА
1. Шарапов О.Д. Економічна кібернетика: навч. посіб. / О.Д. Шарапов, В.Д. Дер-
бенцев, Д.Є. Семьонов. — К.: КНЕУ, 2004. — 231 с.
2. Теорія і практика прийняття управлінських рішень / А.С. Крупник,
К.О. Линьов, Є.М. Нужний, О.М. Рудик. — К.: Видавничий дім «Простір»,
2007. — 119 с.
3. Дубовой В.М. Моделі прийняття рішень в управлінні розподіленими динаміч-
ними системами: моногр. / В.М. Дубовой, О.О. Ковалюк. — Вінниця:
УНІВЕРСУМ, 2008. — 185 c.
4. Бідюк П.І. Проектування комп’ютерних інформаційних систем підтримки при-
йняття рішень: навч. посіб. / П.І. Бідюк, Л.О. Коршевнюк. — К.: ННК
«ІПСА» НТУУ «КПІ», 2010. — 340 с.
5. Панкратова Н.Д. Моделі і методи аналізу ієрархій: Теорія. Застосування: навч.
посіб. / Н.Д. Панкратова, Н.І. Недашківська. — К.: ІВЦ Вид-во
«Політехніка», 2010. — 371 с.
6. Hierarchies in Distributed Decision Making / Christoph Schneeweiss. — Springer,
2013. — 341 p.
7. Krupa T. Hierarchical Decision-Making Problems / T. Krupa, T. Ostrowska // Mod-
eling and Solutions. Foundations and Management. The Journal of Warsaw Uni-
versity of Thechnology. — 2016. — Vol. 8, Issue 1. — P. 311–324. — DOI
10:1515/fman-2016-0024.
8. Evolutionary Multi-Agent Systems: From Inspirations to Applications / A. Byrski,
M. Kisiel-Dorohinicki. — Springer. — 2017. — 224 p.
9. Zheng Y. Consensus of Hybrid Multi-Agent Systems / Y. Zheng, J. Ma, L. Wang //
IEEE Transactions on Neural Networks and Learning Systems. — 2018. —
Vol. 29, Issue 4. — P. 1359–1365. — DOI: 10.1109/TNNLS. 2017.2651402.
10. Катренко А.В. Механізми координації у складних ієрархічних системах /
А.В. Катренко, І.В. Савка / Інформаційні системи та мережі: вісн. НУ
«Львівська політехніка». — 2008. — № 631. — С. 156 – 166.
11. Sun Z. Cooperative Coordination and Formation Control for Multi-agent Systems /
Z. Sun. — Springer. — 2018. — 179 p.
12. Veetil V.P. Coordination in Centralized and Decentralized Systems / V. P. Veetil //
International Journal of Microsimulation. — 2017. — N 10 (2). — P. 86–102.
13. Романюк С.А. Децентралізація: теорія та практика застосування: моногр. /
С.А. Романюк. — К., 2018. — 216 с.
14. Decision Making Under Uncertainty: Theory and Application / M.J. Kochenderfer.
— Massachusetts Institute of Thechnology: The MIT Press, 2015. — 323 p.
15. Harrington J.E. Games, Strategies, and Decision Making / J.E. Harrington, Jr. —
Worth Publishers, 2014. — 540 p.
16. Neyman A. Stochastic Games and Applications / A. Neyman, S. Sorin. — Springer
Science & Business Media, 2012. — 473 p.
17. Кравець П.О. Ігрова модель самоорганізації мультиагентних систем /
П.О. Кравець // Інформаційні системи та мережі: вісн. НУ «Львівська
політехніка». — 2015. — № 829. — С. 161–176.
18. Кравець П.О. Ігрова модель прийняття рішень в ієрархічних системах /
П.О. Кравець // Інформаційні системи та мережі: вісн. НУ «Львівська
політехніка». — 2017. — № 872. — С. 111–120.
Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель …
Системні дослідження та інформаційні технології, 2019, № 3 75
19. Кравець П.О. Ігрова модель системи з авторитарним прийняттям рішень /
П.О. Кравець // Інформаційні системи та мережі: вісн. НУ «Львівська
політехніка». — 2018. — № 901. — С. 61–67.
20. Бурков В.Н. Теория активных систем: состояние и перспективы / В.Н Бурков,
Д.А. Новиков. — М. Синтег, 1999. — 128 с.
21. Айзерман М.А. Выбор вариантов: основы теории / М.А. Айзерман,
В.Ф. Алескеров. — М.: Наука, 1990. — 240 с.
22. Назин А.В. Адаптивный выбор вариантов / А.В. Назин, А.С. Позняк. — М.:
Наука, 1986. — 288 с.
23. Гермейер Ю.Б. Игры с непротивоположными интересами / Ю.Б. Гермейер. —
М.: Наука, 1976. — 328 с.
24. Губко М.В. Теория игр в управлении организационными системами / М.В. Губ-
ко, Д.А. Новиков. — М.: Синтег, 2002. — 148 с.
25. Новиков Д.А. Игры и сети / Д.А. Новиков // Математическая теория игр и ее
приложения. — Т. 2, Вып. 1. — 2010. — С. 107–124.
26. Tadelis S. Game Theory: An Introduction / S. Tadelis. — Princeton University Press,
2013. — 416 p.
27. Petrosjan L.A. Game Theory and Application / L.A. Petrosjan, V.V. Mazalov. —
New York: Nova Science Publishers, 2007. — 227 p.
28. Ungureanu V. Pareto-Nesh-Stackelberg Game and Control Theory: Intelligent Para-
digms and Applications / V. Ungureanu. — Springer, 2018. — 343 p.
29. Neogy S.K. Mathematical Programming and Game Theory / S.K. Neogy, R.B. Bapat,
D. Dubey. — Springer, 2018. — 226 p.
30. Kushner H. Stochastic Approximation and Recursive Algorithms and Applications /
H. Kushner, G. George Yin. — Springer Science & Business Media, 2013. —
417 p.
Надійшла 15.04.2019
|
| id | journaliasakpiua-article-163589 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:24:29Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/cc/1132f8e9fc85058e8ba7ee38329519cc.pdf |
| spelling | journaliasakpiua-article-1635892019-12-13T15:15:18Z Game strategies for decision making in hierarchical systems. I. Mathematical model of stochastic game Игровые стратегии принятия решений в иерархических системах. I. Математическая модель стохастической игры Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри Kravets, Petro A. decision making hierarchical system conditions of uncertainty stochastic game mathematical model принятие решений иерархическая система условия неопределенности стохастическая игра математическая модель прийняття рішень ієрархічна система умови невизначеності стохастична гра математична модель A mathematical model of a stochastic game for decision making in hierarchical systems under uncertainty conditions is developed. The essence of the game consists in aligning the players' pure strategies to achieve a consensus or a majoritarian collective solution. The parameterization of the game model for the separation of the autocratic, anarchic, and democratic hierarchical structures of decision-making systems is carried out. A Markov recurrent method for solving a stochastic game based on a stochastic approximation of the complementary slackness condition has been developed. Разработана математическая модель стохастической игры для принятия решений в иерархических системах в условиях неопределенности. Суть игры состоит в выравнивании чистых стратегий игроков для достижения консенсусного или мажоритарного коллективного решения. Выполнена параметризация игровой модели для обособления автократической, анархической и демократической иерархических структур систем принятия решений. Разработан марковский рекуррентный метод решения стохастической игры на основе стохастической аппроксимации условия дополняющей нежесткости. Розроблено математичну модель стохастичної гри для прийняття рішень в ієрархічних системах в умовах невизначеності. Суть гри полягає у вирівнюванні чистих стратегій гравців для досягнення консенсусного або мажоритарного колективного рішення. Виконано параметризацію ігрової моделі для відокремлення автократичної, анархічної та демократичної ієрархічних структур систем прийняття рішень. Розроблено марковський рекурентний метод розв’язування стохастичної гри на основі стохастичної апроксимації умови доповняльної нежорсткості. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-10-07 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/163589 10.20535/SRIT.2308-8893.2019.3.06 System research and information technologies; No. 3 (2019); 63-75 Системные исследования и информационные технологии; № 3 (2019); 63-75 Системні дослідження та інформаційні технології; № 3 (2019); 63-75 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/163589/183692 Copyright (c) 2021 System research and information technologies |
| spellingShingle | прийняття рішень ієрархічна система умови невизначеності стохастична гра математична модель Kravets, Petro A. Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title | Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title_alt | Game strategies for decision making in hierarchical systems. I. Mathematical model of stochastic game Игровые стратегии принятия решений в иерархических системах. I. Математическая модель стохастической игры |
| title_full | Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title_fullStr | Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title_full_unstemmed | Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title_short | Игрові стратегії прийняття рішень в ієрархічних системах. I. Математична модель стохастичної гри |
| title_sort | игрові стратегії прийняття рішень в ієрархічних системах. i. математична модель стохастичної гри |
| topic | прийняття рішень ієрархічна система умови невизначеності стохастична гра математична модель |
| topic_facet | decision making hierarchical system conditions of uncertainty stochastic game mathematical model принятие решений иерархическая система условия неопределенности стохастическая игра математическая модель прийняття рішень ієрархічна система умови невизначеності стохастична гра математична модель |
| url | https://journal.iasa.kpi.ua/article/view/163589 |
| work_keys_str_mv | AT kravetspetroa gamestrategiesfordecisionmakinginhierarchicalsystemsimathematicalmodelofstochasticgame AT kravetspetroa igrovyestrategiiprinâtiârešenijvierarhičeskihsistemahimatematičeskaâmodelʹstohastičeskojigry AT kravetspetroa igrovístrategííprijnâttâríšenʹvíêrarhíčnihsistemahimatematičnamodelʹstohastičnoígri |