У біматричній грі елемент bij є. Загальне запровадження теорію ігор
Московський міський університет управління уряду Москви
Факультет управління
Кафедра прикладної математики
Реферат
з навчальної дисципліни
"Математичні методи дослідження систем керування"
На тему: "Біматричні ігри. Пошук рівноважних ситуацій"
1. Біматричні ігри
Абсолютно будь-яка управлінська діяльність неспроможна існувати без конфліктних ситуацій. Це ситуації, де стикаються двоє чи більше сторін із різними інтересами. Цілком природно, кожна зі сторін хоче вирішити конфлікт на свою користь і отримати максимальну вигоду. Вирішення такого завдання може бути ускладнене тим, що конфліктуюча сторона не має повної інформаціїпро конфлікт у цілому. Інакше можна сказати, що в конфліктній ситуації необхідно ухвалити оптимальне рішення в умовах невизначеності.
Для вирішення таких завдань використовується математичне моделювання. Введемо кілька основних понять. Математична модель конфліктної гри називається грою. Сторони конфлікту – гравці, дія гравця – хід, сукупність ходів – стратегія, результат гри – виграш.
Обов'язковим моментом перед розв'язанням завдання є виявлення певних правил. Як правило, ці правила є сукупністю вимог і обмежень на дії гравців, обмін інформацією гравців про дії противників, функції виграшів противників і т.п. Правила мають бути чіткими, інакше гра не відбудеться.
На цей час існує кілька способів класифікації ігор. Основним є поділ на безкоаліційні кінцеві парні ігри з виграшами (матричні, позиційні, біматричні) та коаліційні. У цьому рефераті ми розглянемо біматричні ігри.
Ігри з фіксованої суми- Ігри, в яких інтереси гравців хоч і не збігаються, але не є повністю протилежними. Окремим випадком є біматричні ігри.
Біматрична гра – це кінцева градвох гравців з ненульовою сумою, в якій виграші кожного гравця задаються матрицями окремо для відповідного гравця (у кожній матриці рядок відповідає стратегії гравця 1, стовпець – стратегії гравця 2, на перетині рядка та стовпця у першій матриці знаходиться виграш гравця 1, у другій матриці – виграш гравця 2.)
Розглянемо парну гру, у якій кожен із учасників має такі можливості вибору своєї лінії поведінки:
гравець А – може вибрати будь-яку із стратегій А 1, …, А m;
гравець В - будь-яку із стратегій В 1, ..., В n;
Якщо гравець А вибрав стратегію А i, гравець В - В j, то в результаті виграш гравця А складе а ij, гравця В - b ij. Виграші гравців А та В можна записати у вигляді двох таблиць.
Таким чином, якщо інтереси гравців різні, але не обов'язково протилежні, для опису гри використовуються дві платіжні матриці. Цей факт і дав назву подібним іграм – біматричним.
2. Стан рівноваги в біматричних матрицях
Рішенням біматричної гри є таке рішення, яке в тому чи іншому сенсі влаштовує обох гравців. Дане формулювання дуже розпливчасте, що обумовлюється тим, що в бі матричних ігорах досить важко чітко сформулювати цілі для гравців. Як один із можливих варіантів – бажання гравця нашкодити своєму супернику на шкоду власному виграшу, або мета протилежна.
Зазвичай розглядаються два підходи до вирішення біматричної гри. Перший - пошук рівноважних ситуацій: шукаються умови, коли гра знаходиться в певній рівновазі, яку невигідно порушувати жодному з гравців окремо. Другий – пошук ситуацій, оптимальних щодо Парето: знаходження умов, за яких гравці спільними зусиллями не можуть збільшити виграш одного гравця, не зменшивши при цьому виграш іншого.
Зупинимо свою увагу першому підході.
У цьому вся підході застосовуються змішані стратегії, тобто. випадок, коли гравці чергують свої чисті стратегіїіз певними ймовірностями.
Нехай гравець А вибирає стратегію А 1 , з імовірністю р 1 , А 2 – р 2 , …, А m – p m , причому
Гравець використовує стратегію В 1 з ймовірністю q 1 , B 2 – q 2 , …, B n – q n , причому
Як критерій "вдалості" гри візьмемо математичні очікування виграшу гравців, які обчислюються за формулами:
Таким чином, можна сформулювати основне визначення:
Розподіл ймовірностей Р* (
) і Q () визначають рівноважну ситуацію, якщо для будь-яких інших розподілів P і Q одночасно виконані такі нерівності:Якщо рівноважна ситуація існує, то відхилення від неї невигідне самому гравцю.
Також справедлива теорема Дж. Неша. Будь-яка біматрична гра має хоча б одну рівноважну ситуацію у змішаних стратегіях.
3. Загальний принцип вирішення біматричних ігор
У першу нерівність системи послідовно підставляються всі чисті стратегії гравця А, при припущенні, що дотримується своєї оптимальної стратегії. У другу нерівність підставляються всі чисті стратегії гравця, при припущенні, що А дотримується своєї оптимальної стратегії.
Отримана система m+n нерівностей, вирішення якої дає значення оптимальних елементів змішаних стратегій(P*,Q*) та платежі, які отримують гравці у точці рівноваги.
приклад: боротьба за ринок.
Рішення завдання
v A =-10×1q 1 +2×1*(1-q 1)+(1-p 1)q 1 -(1-p 1)(1-q 1)=-14×1q 1 +3× 1+2q 1 -1
v B =5×1q 1 -2×1*(1-q 1)-(1-p 1)q 1 +(1-p 1)(1-q 1)=9×1q 1 -3×1- 2q 1+1
p 1 =1 тоді v A =2-12q 1
-14×1q 1 +3×1+2q 1 -1p 1 =0 тоді v A =-1+2q 1
-14×1q 1 +3×1+2q 1 -1q 1 =1тоді v B =-1+6×1
9×1q 1 -3×1-2q 1 +1q 1 =0 тоді v B =1–3×1
9×1q 1 -3×1-2q 1 +1Складаємо 4 системи, перетворюємо, отримуємо.
65. У графічному методі вирішення ігор 3*3 знаходження оптимальних стратегій гравців:
а) будується два трикутники (*відповідь*)
б) будується один трикутник.
в) трикутники не будуються зовсім.
66. Графік нижньої огинаючої для графічного методу вирішення ігор 2*m представляє у загальному випадку функцію:
а) монотонно спадаючу.
б) монотонно зростаючу.
в) немотонний.
67. Якщо в антагоністичній грі на відрізку функція виграшу 1-го гравця F(x,y) дорівнює 2*x+C, то залежно від C:
а) сідлових точок немає ніколи.
б) сідлові точки є завжди (* відповідь *)
в) інший варіант
68.Чим можна задати завдання ухвалення рішення в умовах невизначеності на кінцевих множинах:
а) двома матрицями.
б) виграшами.
в) чимось ще (* відповідь *)
69. В антагоністичній грі довільної розмірності виграш першого гравця - це:
а) число.
б) безліч.
в) вектор, чи впорядковане безліч.
г) функція (*відповідь*)
70. У матричній грі 3*3 дві компоненти змішаної стратегії гравця:
а) визначають третю (* відповідь *)
б) не визначають.
71. Біматрична гра може бути визначена:
а) двома матрицями однакової розмірності з довільними елементами,
б) двома матрицями не обов'язково однакової розмірності,
в) однією матрицею.
72. У матричній грі елемент aij є:
а) програш 2-го гравця при використанні ним j-ї стратегії, а 2-м - i-ї стратегії(*відповідь*)
б) оптимальну стратегію 2-го гравця при використанні супротивником i-йабо j-ї стратегії,
в) виграш 1-го гравця при використанні ним j-ї стратегії, а 2-м - i-ї стратегії,
73. Елемент матриці aij відповідає сідловій точці. Можливі такі ситуації:
а) оптимальних.
б) чисті.
в) немає однозначної відповіді (*відповідь*)
84. Якщо в матриці всі стовпці однакові і мають вигляд (4 3 0 2), то яка стратегія є оптимальною для 2-го гравця?
a) перша. б) третя. в) будь-яка (* відповідь *)
85. Яка максимальна кількість сідлових точок може бути у грі розмірності 3*3 (матриця може містити будь-які числа):
а)3.
б)9.
в) 27 (* відповідь *)
86.Нехай в антагоністичній грі X = (1; 5) - безліч стратегій 1-го
гравця, Y = (2; 8) - безліч стратегій 2-го гравця. Чи є пара (1,2)
бути сідловою точкою у цій грі:
а) завжди.
б) іноді (*відповідь*)
в) ніколи.
87. Чи буває в біматричній грі розмірності 3 * 3 рівно 2 ситуації рівноваги?
а) Завжди.
б) іноді (*відповідь*)
в) ніколи.
88. Нехай у матричній грі розмірності 2*3 одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.3, x, x). Чому дорівнює число x?
а)0.7 б)0.4 в)чомусь ще (*відповідь*)
89. Матрична гра – це окремий випадокбіматричний, при якому завжди справедливо:
а) матриця А дорівнює матриці, взятої зі зворотним знаком.
б) матриця A дорівнює матриці.
в) Добуток матриць А і В -поодинока матриця.
90. У біматричній грі елемент by є:
а) виграш 2-го гравця при використанні ним i-ї стратегії, а 1-м - j-ї стратегії,
б) оптимальну стратегію 2-го гравця при використанні противником i-ї або j-ї стратегії/
в) щось інше (* відповідь *)
91. У біматричній грі елемент ац відповідає ситуації рівноваги. Можливі такі ситуації:
а) у стовпці є елементи, що дорівнюють цьому елементу (*відповідь*)
б) цей елемент менший за деякі в стовпці.
в) цей елемент найменший у стовпці.
92. У матричній грі, знаючи стратегії кожного гравця та функцію виграшу,
ціну гри в чистих стратегіях можна знайти:
а) завжди.
б) іноді (*відповідь*)
в) питання некоректне.
В іграх з ненульовою сумоюу виграші або програші можуть опинитися всі учасники гри. Біматрична гра– це кінцева гра двох гравців із ненульовою сумою. У цьому випадку для кожної ігрової ситуації A i B j кожен із гравців має свій виграш a ij для першого гравця та b ij – для другого гравця. До біматричної гри зводиться, наприклад, поведінка виробників на ринках недосконалої конкуренції. За допомогою онлайн-калькулятора можна знайти рішення біматричної гри, а також ситуації оптимальні за Парето та ситуації стійкі за Нешем.
Розглянемо конфліктну ситуацію, у якій кожен із двох учасників має такі можливості для вибору своєї лінії поведінки:
- гравець А – може вибрати будь-яку із стратегій А 1 ,…,А m ,
- гравець В - будь-яку зі стратегій В 1, ..., В n.
При цьому їх спільний вибір оцінюється цілком виразно: якщо гравець А вибрав i-ю стратегію А i , а гравець В – k -ю стратегію В k , то в результаті виграш гравця А дорівнюватиме деякому числу a ik , а виграш гравця В деякому, взагалі кажучи, іншому числу b ik .
Послідовно перебираючи усі стратегії гравця А та всі стратегії гравця В, ми зможемо заповнити їх виграшами дві таблиці.
Перша таблиця описує виграш гравця А, а друга – виграш гравця У. Зазвичай ці таблиці записують як матриці.
Тут А – платіжна матриця гравця А, У – платіжна матриця гравця У.
Таким чином, у випадку, коли інтереси гравців різні (але не обов'язково протилежні) виходять дві платіжні матриці: одна – матриця виплат гравцеві А, інша – матриця виплат гравцеві В. Тому цілком природно звучить назва, яка зазвичай присвоюється подібній грі. біматрична.
Рівновага Неша– рівновага, коли кожен учасник гри вибирає стратегію, яка є для нього оптимальною за умови, що решта учасників гри дотримується певної стратегії.
Рівновага Неша не завжди є найбільш оптимальною для учасників. У цьому випадку кажуть, що рівновага не є Парето-оптимальним.
Чиста стратегія- Певна реакція гравця на можливі варіантиповедінки інших гравців
Змішана стратегія- Імовірнісна (не визначена точно) реакція гравця на поведінку інших гравців.
Приклад №1. Боротьба ринки збуту.
Фірма а має намір збути партію товару одному з двох ринків, контрольованих більшою фірмою b . З цією метою вона проводить підготовчу роботу, Пов'язану з певними витратами. Якщо фірма b розгадає, на якому з ринків фірма а продаватиме свій товар, вона прийме контрзаходи і перешкодить "захопленню" ринку (цей варіант означає поразку фірми а); якщо ні, то фірма отримує перемогу. Припустимо, що з фірми а проникнення першому ринку вигідніше, ніж проникнення другий, а й боротьба першому ринку вимагає від неї великих коштів. Наприклад, перемога фірми але в першому ринку приносить їй удвічі більший прибуток, ніж перемога другою, зате поразка першому ринку повністю її руйнує.
Складемо математичну модель цього конфлікту, вважаючи фірму гравцем 1 і фірму b гравцем 2. Стратегії гравця 1: А 1 – проникнення ринку 1, А 2 – проникнення ринку 2; стратегії гравця 2: У 1 - контрзаходи на ринку 1, У 2 – контрзаходи над ринком 2. Нехай фірми та її перемога на 1-му ринку оцінюється в 2 одиниці, а перемога на 2-му ринку – на 1 одиницю; поразка фірми але в 1-му ринку оцінюється -10, але в 2-му -1. Для фірми b її перемога становить відповідно 5 та 1 одиницю, а поразка -2 та -1. Отримуємо в результаті біматричну гру Г з матрицями виграшів
.
По теоремі ця гра може мати чи чисті, чи цілком змішані ситуації рівноваги. Ситуацій рівноваги у чистих стратегіях тут немає. Переконаємося тепер, що гра має цілком змішану ситуацію рівноваги. Знаходимо 
, .
Отже, розглянута гра має єдину ситуацію рівноваги (x 0; y 0), де , . Вона може бути реалізована при багаторазовому повторенні гри (тобто при багаторазовому відтворенні описаної ситуації) таким чином: фірма а повинна використовувати чисті стратегії 1 та 2 із частотами 2/9 та 7/9, а фірма b – чисті стратегії 1 та 2 з частотами 3/14 та 11/14. Будь-яка з фірм, відхилившись від зазначеної змішаної стратегії, зменшує очікуваний виграш.
Приклад №2. Знайти ситуації оптимальні за Парето та ситуації стійкі за Нешем для біматричної гри.
Приклад №3. Є 2 фірми: перша може зробити один із двох виробів А 1 і А 2 , друга – одне з двох виробів B 1 , B 2 . Якщо перша фірма виробить продукцію A i (i = 1, 2), а друга - B j (j = 1, 2), то прибуток цих фірм (що залежить від того, чи ці вироби взаємодоповнюють або конкурують), визначається таблицею №1 :
| В 1 | В 2 | |
| А 1 | (5, 6) | (3, 2) |
| А 2 | (2, 1) | (5, 3) |
Тести для підсумкового контролю
1. Антагоністична гра може бути задана:
а) безліччю стратегій обох гравців та сідловою точкою.
б) безліччю стратегій обох гравців та функцією виграшу першого гравця.
2. Ціна гри існує для матричних ігор у змішаних стратегіях завжди.
а) так.
3. Якщо в матриці виграшів усі стовпці однакові і мають вигляд (4 5 0 1), то яка стратегія оптимальна для одного гравця?
а) перша.
б) друга.
в) будь-яка з чотирьох.
4.Нехай у матричній грі одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.4, 0, 0.6). Яка розмірність цієї матриці?
а) 2*3.
в) інша розмірність.
5. Принцип домінування дозволяє видаляти із матриці за один крок:
а) повністю рядки.
б) окремі числа.
6.У графічному методі вирішення ігор 2*m безпосередньо з графіка знаходять:
а) оптимальні стратегії обох гравців.
б) ціну гри та оптимальні стратегії 2-го гравця.
в) ціну гри та оптимальні стратегії 1-го гравця.
7.Графік нижньої огинаючої для графічного методу вирішення ігор 2*m є в загальному випадку:
а) ламану.
б) пряму.
в) параболу.
8. У матричній грі 2*2 дві компоненти змішаної стратегії гравця:
а) визначають значення один одного.
б) незалежні.
9. У матричній грі елемент aij є:
а) виграш 1-го гравця при використанні ним i-ї стратегії, а 2-м - j-ї стратегії.
б) оптимальну стратегію одного гравця при використанні противником i-ї або j-ї стратегії.
в) програш 1-го гравця при використанні ним j-ї стратегії, а 2-м - i-ї стратегії.
10. Елемент матриці aij відповідає сідловій точці. Можливі такі ситуації:
а) цей елемент суворо найменше у рядку.
б) цей елемент другий по порядку у рядку.
11. У методі Брауна-Робінсон кожен гравець під час вибору стратегії на наступному кроці керується:
а) стратегіями супротивника на попередніх кроках.
б) своїми стратегіями попередніх кроках.
в) ще чимось.
12. За критерієм математичного очікування кожен гравець виходить із того, що:
а) станеться найгірша йому ситуація.
в) всі або деякі ситуації можливі з деякими ймовірностями.
13. Нехай матрична гра задана матрицею, де всі елементи негативні. Ціна гри позитивна:
б) ні.
в) немає однозначної відповіді.
14. Ціна гри – це:
а) число.
б) вектор.
в) матриця.
15. Яка максимальна кількість сідлових точок може бути в грі розмірності 5 * 5 (матриця може містити будь-які числа):
16. Нехай у матричній грі розмірності 2*3 одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.3, x, 0.5). Чому дорівнює число x?
в) іншому числу.
17. Для якої розмірності ігрової матриці критерій Вальда звертається до критерію Лапласа?
в) тільки в інших випадках.
18. Верхня ціна гри завжди менша від нижньої ціни гри.
б) ні.
б) питання некоректне.
19. Які стратегії бувають у матричній грі:
а) чисті.
б) змішані.
в) і ті, і ті.
20. Чи можуть у якійсь антагоністичній грі значення функції виграшу обох гравців для деяких змінних значень дорівнювати 1?
а) завжди.
б) інколи.
в) ніколи.
21.Нехай у матричній грі одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.4, 0.1,0.1,0.4). Яка розмірність цієї матриці?
в) інша розмірність.
22. Принцип домінування дозволяє видаляти із матриці за один крок:
а) цілком стовпці,
б) окремі числа.
в) підматриці менших розмірів.
23. У матричній грі 3*3 дві компоненти змішаної стратегії гравця:
а) визначають третю.
б) не визначають.
24. У матричній грі елемент aij є:
а) програш 2-го гравця при використанні ним j-ї стратегії, а 2-м – i-ї стратегії.
б) оптимальну стратегію 2-го гравця при використанні противником i-ї або j-ї стратегії,
в) виграш 1-го гравця при використанні ним j-ї стратегії, а 2-м – i-ї стратегії,
25. Елемент матриці aij відповідає сідловій точці. Можливі такі ситуації:
а) цей елемент найбільше у стовпці.
б) цей елемент строго найбільше по порядку в рядку.
в) у рядку є елементи і більше, і менше, ніж елемент.
26. За критерієм Вальда кожен гравець виходить із того, що:
а) станеться найгірша для нього ситуація.
б) усі ситуації рівноможливі.
в) усі ситуації можливі з деякими заданими ймовірностями.
27. Нижня ціна менша від верхньої ціни гри:
б) який завжди.
в) ніколи.
28. Сума компонентів змішаної стратегії для матричної гри завжди:
а) дорівнює 1.
б) невід'ємна.
в) позитивна.
г) який завжди.
29. Нехай у матричній грі розмірності 2*3 одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.2, x, x). Чому дорівнює число x?
