Тема 9. Продовження деяких питань теорії ігор. Лекція 11

1.

Теорія прийняття рішень
Decision Making

2.

Тема 9
Лекція 11
Продовження деяких питань теорії ігор

3.

Парадокс Браєса
Німецький математик Дитрих Браєс (Dietrich Braess, нар.
1939) D. Braess, Über ein Paradoxon aus der Verkehrsplanung.
Unternehmensforschung 12, 258—268 (1968)

4.

Парадокс Браєса
• Розглянемо дві точки Start та End, між якими є два шляхи , що проходять через точки А і В. Пропускна здатність
траси Start -А дорівнює 100 машин \ хв і дорівнює пропускний здатності траси В- End . Час , що витрачається
машинами на проходження цих трас , що дорівнює Т\p, де n - кількість машин, що проходять по трасі , а p = 100 пропускна здатність траси . Пропускна здатність трас А - End і Start -В не залежить від кількості машин ( дуже
потужні траси ), та середнє час проходження машин по них дорівнює 45 хв .
• Припустимо , що 4000 машин прагнуть потрапити з точки Start до точки End . Кожна їх вибирає собі найбільш
оптимальний шлях. Через симетричність ситуації половина машин (2000) вибере шлях Start -А- End , а інша
половина - шлях Start -В- End . Час , що витрачається ними на проходження того й іншого шляху , дорівнює 65 хв
(2000/100 + 45 або 45 + 2000/100).
• А тепер уявімо, що держава вирішило скоротити це час і відкрило між точками А та В додаткову потужну
односторонню трасу , час проходження якої складає всього 5 хв . Оскільки старі траси ніхто не закриває , то у водіїв ,
теоретично , з'являється додатковий вибір . Але ось парадокс: у цій ситуації всі водії вибирають шлях Start -А-В- End ,
оскільки у своїй початковий частини ( Start -А) він складає всього 40 хв навіть у самому гіршому варіанті ( коли всі
4000 машин прямують по ньому ), тоді як шлях Start -В - 45 хв . Далі вибору знову практично ні , оскільки на шлях АВ витрачається 5 хв , а на шлях В - End - знову ж таки в самому гіршому варіанті - 40 хв . Зрозуміло , всі сподіваються
на краще варіант ( оскільки на шлях А- End також витрачається 45 хв , і є надія , що якісь машини _ виберуть його),
коли хоча б одна машина вибирає продовження А- End . В результаті всі вибирають шлях А-В- End , і загальне час
проходження шляхи Start -А-В- End становить 85 хв (4000100 + 5 + 4000100). Тобто загальне час проходження шляхи
між точками А і В збільшується на 20 хв , хоча , здавалося б , нова траса була відкрита саме для зменшення цього
часу .
• Але саме парадоксальне в даній ситуації полягає в тому, що скоротити це час можна, можливо тільки одним
способом - закривши знову відкриту трасу А-В і повернувшись до старої структурі транспортної мережі.

5.

Як подолати ПБ?
Відповідь
Власне кажучи , рішення даного парадоксу вже названо - це видалення
додаткового елемента мережі та повернення до неї колишній структурі . Таке
рішення називається тривіальним. Більше складне завдання: аналіз існуючих
мереж на наявність парадоксу Браєса та видалення парадоксального елемента
мережі. Така задача поки що не вирішена , оскільки не відомий алгоритм, який
дозволяв б однозначно встановлювати вказаний елемент . Або що
рівносильно , встановлювати оптимальну конфігурацію мережі.
Інше рішення полягає у централізованому керуванні потоками в мережах .
Таке управління навіть малої частиною потоку може дати значний ефект .
Проблема в тому, що витрати на централізацію можуть звести до нуля цей
ефект і навіть зробити мережу нерентабельною .
Ще одне рішення – це запровадження « плати » за проходження елементів
мережі, що автоматично регулює інтенсивність проходять через них потоків .

6.

Ціна анархії
Ціна анархії (англ. Price of Anarchy, PoA) – це концепція в теорії ігор, яка вимірює, наскільки
ефективність системи деградує через егоїстичної поведінки гравців. У прикладі Браєса вона має
місце через розбіжність ефективності за Парето та рівноваги за Нешем. Припустимо, вам треба
якнайшвидше дістатися з пункту А в пункт В. Зрозуміло, ви намагатиметеся скористатися свіжою
інформацією про найкоротші шляхи, про ситуацію на дорогах. Можливо, ви навіть зайдете на
«Гугл.Пробки» або загляньте за цією інформацією в навкручений навігатор GPS. Однак це не
допоможе: вчені довели, що всі ці дані, навпаки, можуть уповільнювати рух. Корейськоамериканська група - Хейджін Йон (Hyejin Youn), Хавунг Еонг (Hawoong Jeong) і Макйл Гастнер
(Michael Gastner) - стверджує, що найсерйозніші затримки створюють саме такі «просунуті» водії,
які безперервно обирають «оптимальну» стратегію їзди раз у раз її міняючі. Цей ефект вони
назвали "витрати анархії" (The Price of Anarchy, POA) - неминуча ціна, яку ми змушені платити за те,
що на дорозі кожен водій відповідає лише сам за себе, і загальна координація та керівництво
відсутні. Високе значення РОА говорить про те, що громадяни, що всіма способами намагаються
знайти для себе найкращий маршрут, помітно знижують швидкість руху в цілому. Вчені вивчали
трафік у трьох великих містах – Лондоні, Бостоні та Нью-Йорку – і виявили, що водії в них
витрачають, відповідно, 24%, 30% та 28% часу в дорозі через те, що намагаються вийти на
«оптимальний» маршрут замість того, щоб їхати, як усі.

7.

Коаліційні чи кооперативні ігри

8.

Гра «Черевики»
Льоня
Льова
Паша
=0
+
=600

9.

Мета кооперативної гри

10.

Властивості вектору виграшів

11.

С-Ядро (Core)
Паша

12.

Игра «Шкарпетки»
Андрій
Борис
+
= 60

13.

Игра «Млинці»

14.

Ядро гри «Млинці»

15.

Гра «Піца» та провал ядра

16.

Ллойд Стауелл Шеплі
Ллойд Стауелл Шеплі ( Lloyd Stowell Shapley; 1923 — 2016) — американський
економіст і математик, лауреат Нобелівської премії (2012) за “алгоритм
оптимального паросполучення Шеплі и Гейла”

17.

Вектор Шеплі

18.

Вектор Шеплі_2

19.

Теорема Шеплі

20.

Вектор Шеплі як мат_очікування

21.

Зміст вектора Шеплі

22.

ВШ для «Млинців»
ShV (50;250)

23.

ВШ для «Піци»

24.

Ще приклад – «лабухи» або джазоркестр
Кооперативна гра «джаз-оркестр» ((Young 1979)
Гравець 1 ("співак"), гравець 2 ("піаніст") та гравець 3 ("ударник") можуть
отримати від господаря клубу 10 000 грн., якщо виступатимуть разом.
Співак та піаніст удвох можуть отримати 8 000 грн., ударник та піаніст – 6
500 грн., один піаніст – 3 000 грн., співак та ударник – 5 000 грн., один
співак – 2 000 грн., а один ударник нічого не може заробити.
Розрахунок вектора Шеплі знайдете в конспекті.
+
+

25.

Рефлексівні ігри. Рефлексія.
Рефлексія. Однією з фундаментальних властивостей буття людини є те, що
поряд із природною («об'єктивною») реальністю існує її відображення у
свідомості. При цьому між природною реальністю та її чином у свідомості
(вважатимемо цей образ частиною особливої – рефлексивної реальності) існує
неминучий зазор, розбіжність.
Термін «рефлексія (лат. reflexio – звернення тому) означає відбиток. Для
прояснення розуміння суті рефлексії розглянемо спочатку ситуацію з одним
суб'єктом. У нього є уявлення про природну реальність, але може і
усвідомлювати (відбивати, рефлексувати) ці уявлення, і навіть усвідомлювати
усвідомлення цих уявлень тощо. Так формується рефлексивна дійсність.
Рефлексія суб'єкта щодо своїх власних уявлень про реальність, принципи своєї
діяльності тощо називається авторефлексією чи рефлексією першого роду.
Рефлексія другого роду має місце щодо уявлень про реальність, принципи
прийняття рішень, авторефлексії тощо інших суб'єктів.

26.

Рефлексівні ігри
Рефлексивною є гра, у якій інформованість гравців перестав бути
загальним знанням і гравці приймають рішення з урахуванням ієрархії
своїх уявлень.
З погляду теорії ігор та рефлексивних моделей прийняття рішень
поділяють стратегічну та інформаційну рефлексію. Інформаційна
рефлексія – процес і результат роздумів гравця у тому, які значення
невизначених параметрів, що про ці значення знають і думають його
опоненти (інші гравці). При цьому, власне, «ігрова» компонента
відсутня, оскільки жодних рішень гравець не приймає. Стратегічна
рефлексія – процес результат роздумів гравця у тому, які принципи
прийняття рішень використовують його опоненти (інші гравці) у межах
тієї поінформованості, що він їм приписує внаслідок інформаційної
рефлексії.

27.

Пенальті
Гравцями є нападник, який б'є по воротах, і воротар. Припустимо для простоти, що у
нападника є дві дії - "бити в лівий кут воріт" і "бити в правий кут воріт". У воротаря також є дві
дії – «ловити м'яч у лівому кутку» та «ловити м'яч у правому кутку». Якщо воротар вгадує, у
який кут б'є нападник, він ловить м'яч.
Промоделюємо міркування гравців. М’яч летить в середньому 0,4 с. Нехай воротареві відомо,
що нападник зазвичай б'є в правий кут. Отже, треба ловити м'яч у правому кутку. Але, якщо
воротар знає, що нападнику відомо, що воротар знає, як зазвичай чинить нападник, то
воротареві слід моделювати міркування нападника. Він може думати так:
«Нападнику відомо, що я знаю його звичайну тактику. Тому він очікує, що я ловитиму м'яч у
правому кутку і може вдарити в лівий кут. І тут мені треба ловити м'яч у лівому кутку». Якщо
нападник має достатню глибину рефлексії, то він може здогадатися про міркування воротаря і
спробувати його перехитрити, вдаривши у правий кут. Цей же ланцюжок міркувань може
провести і воротар і на цій підставі ловити м'яч у правому кутку. І нападник, і воротар можуть
збільшувати глибину рефлексії до нескінченності, проводячи міркування один за одного, і
жоден з них не має раціональних підстав зупинитися на деякому кінцевому кроці. Отже, у
межах моделювання взаємних міркувань не можна апріорі визначити результат цієї гри.

28.

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

29.

Погоня
Розглянемо ситуацію погоні.
Персонаж X намагається втекти від персонажа Y. Знаючи, що Y бігає швидше за нього, X вирішує
скористатися рефлексивним міркуванням, вважаючи, що Y до нього не здатний. Він вбігає в печеру,
показану на малюнку, і за наявності двох коридорів А та В вибирає коридор В. Чому він це робить?
Схема його міркувань така. Коридор А більш пристосований для пересування, в ньому можна бігти,
а у вузькому коридорі доведеться пробиратися майже повзком.
Іншими словами, А > В, де знаком > позначено, що коридор А краще В. І персонаж Y про це теж
знає. Але оскільки Y не вміє рефлективно міркувати (це відповідає тому, що Y має нульовий ранг
рефлексії), то схема міркувань Y матиме такий вигляд: X і я знаємо, що А > В, отже, ХА і, отже, УА . Тут
ХА і YА позначають відповідно те, що X і Y вибирають рух коридором А. Але для X така ситуація
нікуди не годиться. Не надто розумний, але швидконогий Y його наздожене або в печері, або після
виходу з неї через вихід А. Саме тому X вдається до рефлексивного міркування. Воно виглядає так: Y
думає, що А отже , YA і, отже, Хв .
Нехай тепер Y спробує наздогнати X, адже вихід розташований зовсім в іншому місці, ніж вихід А. У
цьому міркуванні персонаж X продемонстрував наявність першого рангу рефлексії. Перш ніж
прийняти рішення, він провів міркування за Y, припустивши, що його знання такі, що він має
нульовий ранг рефлексії.
Але чи правильне це припущення? Адже X міг і прорахуватися, не підозрювати, що Y сам має
перший ранг рефлексії. В цьому випадку Y не кидається одразу в коридор А тому, що А а також
вдається до рефлексивного міркування виду: X думає, що А та Y A. Отже, Ув .
І тут X програє. А що буде, якщо X має другий ранг рефлексії? У цьому випадку він припускає, що Y
здатний до рефлексивних міркувань першого рангу. У умовах міркування X може виглядати так: Y
думає, що X думає, що А>В і, отже, Хв і, отже, Y B звідси Х А .
І якщо X правильно оцінив можливості К, він пішов від погоні. Але якщо X провів рефлексивне
міркування на рівні другого рангу рефлексії, a Y мав лише нульовий ранг, то X попався. Він
«перемудрив сам себе», вважаючи, що Y має змогу міркувати, які тому і не снилися.

30.

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

31.

Граничний ранг рефлексії
Який граничний ранг рефлексії? Як інформаційне обмеження візьмемо
загальноприйняте в психології число Міллера – 7±2, що відображає
максимальну кількість об'єктів (ознак, альтернатив тощо), якими людина
може одночасно оперувати. Якщо w – ранг рефлексії, то кількість варіантів
дій (інших гравців), які необхідно брати до уваги гравця, дорівнює 2 (w +
1), а кількість зв'язків між ними – (w + 1)! (при цьому передбачається, що
гравець вважає опонента приблизно таким самим раціональним, яким і
себе).Якщо врахувати інформаційні обмеження, то отримаємо, що має
виконуватися або 2 (w + 1) 7±2, або (w + 1)! 7±2. Вирішення першої
нерівності в цілих позитивних числах дає w = {0; 1; 2; 3}, другої – w = {0; 1;
2}.
При числі Міллера, що дорівнює 7, отримуємо, що максимальний (з
урахуванням інформаційних обмежень) ранг стратегічної рефлексії
дорівнює двом.

32.

Рефлексивне управління
Рефлексивне управління це процес, у якому один із супротивників
передає іншій підставі для прийняття рішень. Іншими словами,
відбувається підміна факторів мотивації противника з метою змусити
його прийняти невигідні для себе, але вигідні для противника рішення.
Прийоми рефлексивного управління під назвою «стратагеми» з давніхдавен займали важливе місце в історії військового мистецтва.
Наприклад, Сунь Цзи виніс у заголовок першого розділу одного зі своїх
трактатів твердження «Війна – це шлях обману», таким чином
визначаючи військове ремесло як мистецтво введення в оману
(дезінформація).

33.

Рефлексивне управління_далі
Рефлексивне управління – це
взаємодія
інтерферуючих функцій когнітивної та впливової .
двох
Рефлексивне управління - вплив на прийняті противником
рішення через підсовування ( нав'язування ) йому таких
вихідних посилок , на підставі яких він діє бажаним для
маніпулятора чином.
Методи рефлексивного управління знайшли широке
застосування в самих різних областях: рекламної сфері ,
зв'язки з громадськістю , військовому мистецтві тощо.
Такою стратегією може бути навмисне програвання
картковим шулером перших партій у грі , систематичні
відволікаючі атаки на маловажному ділянці бойових дій
тощо.
Рефлексивне управління це процес , в якому один з
супротивників передає іншому підставу для прийняття
рішень . Іншими словами, відбувається підміна факторів
мотивації супротивника з метою спонукати його на
прийняття невигідних для себе рішень .
Нарративи

34.

Лекція закінчена
Будь ласка, запитання, коментарі ? ? ?
Дякую за увагу!