Якщо є кілька конфліктуючих сторін (осіб), кожна з яких приймає деяке рішення, що визначається заданим набором правил, і кожному з осіб відомий кінцевий стан конфліктної ситуації із заздалегідь визначеними для кожної із сторін платежами, то кажуть, що має місце гра.
Завдання теорії ігор полягає у виборі такої лінії поведінки даного гравця, відхилення від якої може лише зменшити його виграш.
Деякі визначення гри
Кількісна оцінка результатів гри називається платежем.
Парна гра (Дві особи) називається грою з нульовою сумою, якщо сума платежів дорівнює нулю, тобто. якщо програш одного гравця дорівнює виграшу іншого.
Однозначний опис вибору гравця в кожній із можливої ситуацій, при якій він повинен зробити особистий хід, називається стратегією гравця .
Стратегія гравця називається оптимальною, якщо при багаторазовому повторенні гри вона забезпечує гравцю максимально можливий середній виграш(або, що - те саме, мінімально можливий середній виграш).
Гра, що визначається матрицею А, що має mрядків та nстовпців, називається кінцевою парною грою розмірності m* n;
де i=
- стратегія першого гравця, що має стратегій;
j=
- стратегія другого гравця, що має стратегій;
ij- Виграш першого гравця по i-ї стратегії при використанні другим j-ї стратегії (або, що те саме, програш другого за своєю j-ї стратегії, при використанні першим i-й);
А = ij– платіжна матриця гри.
1.1 Гра із чистими стратегіями
Нижня ціна гри (для першого гравця)
= max (min ij). (1.2)
i j
Верхня ціна гри (для другого гравця):
= min
(max
ij)
. (1.3)
J i
Якщо = гра називається з сідловою точкою (1.4), або гра з чистими стратегіями. При цьому V = = називають цінної гри ( V- Ціна гри).
приклад.Дано платіжну матрицю гри 2 осіб А. Визначити оптимальні стратегіїдля кожного з гравців та ціну гри:
(1.4)
max 10 9 12 6
i
min 6
j
- Стратегія першого гравця (рядки).
Стратегія другого гравця (стовпці).
- Ціна гри.
Таким чином, гра має сідлову точку. Стратегія j = 4 – оптимальна для другого гравця, стратегія i=2 – для першого. Маємо гру із чистими стратегіями.
1.2 Ігри зі змішаними стратегіями
Якщо платіжна матриця немає сідлової точки, тобто. 
, і жоден з учасників гри не може вибрати один план як свою оптимальну стратегію, гравці переходять на «змішані стратегії». При цьому кожен із гравців використовує в процесі гри кілька разів кожну зі своїх стратегій.
Вектор, кожен з компонентів якого показує відносну частоту використання гравцем відповідної чистої стратегії, називається змішаною стратегією даного гравця.
Х= (х 1 …х i …х m) - Змішана стратегія першого гравця.
У= (у 1 …у j …у n) - Змішана стратегія другого гравця.
xi , у j- Відносні частоти (ймовірності) використання гравцями своїх стратегій.
Умови використання змішаних стратегій
.
(1.5)
Якщо Х* = (х 1 * ….х i * … х m*) - оптимальна стратегія, обрана першим гравцем; Y* = (у 1 * …у j * … у n*) – оптимальна стратегія, обрана другим гравцем, число є ціною гри.
(1.6)
Для того, щоб число Vбуло ціною гри, а х* і у* - оптимальними стратегіями, необхідно і достатньо виконання нерівностей
(1.7)
Якщо один із гравців застосовує оптимальну змішану стратегію, то його виграш дорівнює ціні гри. Vнезалежно від того, з якими частотами буде застосовувати другий гравець стратегії, що увійшли до оптимальної, у тому числі чистих стратегій.
Відомості задач теорії ігор до задач лінійного програмування.
приклад. Знайти рішення гри, яка визначається платіжною матрицею А.
А = 
(1.8)
y 1 y 2 y 3
Рішення:
Складемо подвійну пару завдань лінійного програмування.
Для першого гравця
(1.9)
у 1 +у 2 +у 3 = 1 (1.10)
Звільняючись від змінної V(ціна гри), розділимо ліву та праву частину виразів (1.9), (1.10) на V. Прийнявши у j /Vза нову змінну z i, отримаємо нову системуобмежень (1.11) та цільову функцію (1.12)
(1.11)
.
(1.12)
Аналогічно отримаємо модель гри для другого гравця:
(1.13)
х 1 +х 2 +х 3 = 1 . (1.14)
Привівши модель (1.13), (1.14) до форми без змінної V, отримаємо
(1.15)
,
(1.16)
де 
.
Якщо необхідно визначити стратегію поведінки першого гравця, тобто. відносну частоту використання його стратегій ( х 1 ….х i …х m), ми використовуватимемо модель другого гравця, т.к. ці змінні перебувають у його моделі виграшу (1.13), (1.14).
Наведемо (1.15), (1.16) до канонічної форми
(1.17)
Завдання:
Матрична гра задана наступною платіжною матрицею:
| Стратегії "B" | ||||||||
| Стратегії "A" | B 1 | B 2 | ||||||
| A 1 | 3 | 5 | ||||||
| A 2 | 6 |
|
||||||
Знайти рішення матричної гри, а саме:
- Виявити верхню ціну гри;
- нижню цінуігри;
- Чисту ціну гри;
- Вказати оптимальні стратегії гравців;
- навести графічне рішення(геометричну інтерпретацію), за потреби.
Крок 1
Визначимо нижню ціну гри - α
Нижня ціна гриα - це максимальний виграш, який ми можемо гарантувати собі, у грі проти розумного супротивника, якщо протягом усієї гри будемо використовувати одну і лише одну стратегію (така стратегія називається "чистою").Знайдемо у кожному рядку платіжної матриці мінімальнийелемент і запишемо його в додатковий стовпець (Виділено жовтим кольоромдив. табл.1).
Потім знайдемо максимальнийелемент додаткового стовпця (відзначений зірочкою), це буде нижня ціна гри.
Таблиця 1
| Стратегії "B" | |||||||||||||||
| Стратегії "A" | B 1 | B 2 | Мінімуми рядків | ||||||||||||
| A 1 | 3 | 5 | 3 * | ||||||||||||
| A 2 | 6 |
|
|
||||||||||||
У нашому випадку нижня ціна гри дорівнює: α = 3, і для того щоб гарантувати собі виграш не гірше ніж 3, ми повинні дотримуватися стратегії A 1
Крок:2
Визначимо верхню ціну гри – β
Верхня ціна гриβ - це мінімальний програш, який може гарантувати собі гравець "В", у грі проти розумного супротивника, якщо протягом усієї гри він використовуватиме одну і лише одну стратегію.Знайдемо у кожному стовпці платіжної матриці максимальнийелемент і запишемо його в додатковий рядок знизу (Виділений жовтим кольором див. Табл.2).
Потім знайдемо мінімальнийелемент додаткового рядка (відзначений плюсом), це буде верхня ціна гри.
Таблиця 2
| Стратегії "B" | ||||||||||||
| Стратегії "A" | B 1 | B 2 | Мінімуми рядків | |||||||||
| A 1 | 3 | 5 | 3 * | |||||||||
| A 2 | 6 |
| У нашому випадку верхня ціна гри дорівнює: β = 5, і для того щоб гарантувати собі програш не гірше ніж 5 супротивник (гравець "B") повинен дотримуватися стратегії B 2 Крок:3 Змішана стратегія, це чергуються випадково чисті стратегії, з певними ймовірностями (частотами). Змішану стратегію гравця "А" позначатимемо
|
|||||||||
де B 1 , B 2 - стратегії гравця "B", а q 1 , q 2 - відповідно до ймовірності, з якими ці стратегії застосовуються, причому q 1 + q 2 = 1.
Оптимальна змішана стратегія для гравця "А" та, що забезпечує йому максимальний виграш. Відповідно для "B" – мінімальний програш. Позначаються ці стратегії S A* і S B * відповідно. Пара оптимальних стратегій утворює рішення гри.
У загальному випадкув оптимальну стратегію гравця можуть входити в повному обсязі вихідні стратегії, лише деякі з них. Такі стратегії називаються активними стратегіями.
Крок:4
де: p 1 , p 2 - ймовірності (частоти) з якими застосовуються відповідно до стратегії A 1 і A 2
З теорії ігор відомо, що якщо гравець "А" використовує свою оптимальну стратегію, а гравець "B" залишається в рамках своїх активних стратегій, то середній виграш залишається незмінним та рівним ціні гри vнезалежно від того, як гравець "В" використовує свої активні стратегії. А в нашому випадку обидві стратегії активні, інакше гра мала б рішення в чистих стратегіях. Тому якщо припустити, що гравець "В" користуватиметься чистою стратегією B1, то середній виграш vскладе:
k 11 p 1 + k 21 p 2 = v (1)
де: k ij – елементи платіжної матриці.
З іншого боку, якщо припустити, що гравець "В" користуватиметься чистою стратегією B 2 , то середній виграш становитиме:
k 12 p 1 + k 22 p 2 = v (2)
Прирівнявши ліві частини рівнянь (1) та (2) отримаємо:
k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2
А з урахуванням того, що p 1 + p 2 = 1 маємо:
k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )
Звідки нескладно знайти оптимальну частоту стратегії A 1 :
| p 1 = |
| (3) |
У цій задачі:
| p 1 = |
| = |
|
Ймовірність р 2 знайдемо відніманням р 1 з одиниці:
| p 2 = 1 - p 1 = | 1 | - |
| = | + | 6 | · |
де: q 1 , q 2 - ймовірності (частоти) з якими застосовуються відповідно до стратегії B 1 і B 2
З теорії ігор відомо, що якщо гравець "B" використовує свою оптимальну стратегію, а гравець "A" залишається в рамках своїх активних стратегій, то середній виграш залишається незмінним та рівним ціні гри vнезалежно від того, як гравець "А" використовує свої активні стратегії. Тому якщо припустити, що гравець "A" користуватиметься чистою стратегією A1, то середній виграш vскладе:
k 11 q 1 + k 12 q 2 = v (4)
Оскільки ціна гри v нам уже відома та враховуючи, що q 1 + q 2 = 1 , То оптимальна частота стратегії B 1 може бути знайдена як:
| q 1 = |
| (5) |
У цій задачі:
| q 1 = |
| = |
|
Ймовірність q 2 знайдемо відніманням q 1 з одиниці:
| q 2 = 1 - q 1 = | 1 | - |
| = |
|
Відповідь:
| Нижня ціна гри: | α = | 3 | |||
| Верхня ціна гри: | β = | 5 | |||
| Ціна гри: | v = |
|
| Оптимальна стратегія гравця "А": |
|
|||||||||||||||
| Оптимальна стратегія гравця "B": |
|
Геометрична інтерпретація (графічне рішення):
Дамо геометричну інтерпретацію розглянутої гри. Візьмемо ділянку осі абсцис одиничної довжини і проведемо через його кінці вертикальні прямі a 1 і a 2 відповідні нашим стратегіям A1 та A2. Припустимо тепер, що гравець "B" користуватиметься стратегією B 1 в чистому вигляді. Тоді, якщо ми (гравець "A") будемо використовувати чисту стратегію A 1 , то наш виграш становитиме 3. Відзначимо відповідну точку на осі a 1 .Якщо ж ми будемо використовувати чисту стратегію A 2 , то наш виграш становитиме 6. Зазначимо відповідну точку на осі a 2
(див. рис. 1). Очевидно, якщо ми будемо застосовувати, змішуючи в різних пропорціях стратегії A 1 і A 2 , наш виграш буде змінюватися по прямій через точки з координатами (0 , 3) і (1 , 6), що проходить через точки, назвемо її лінією стратегії B 1 (на Рис. .1 показана червоним кольором). Абсцис будь-якої точки на даній прямій дорівнює ймовірності p 2 (частоті), з якою ми застосовуємо стратегію A 2 , а ордината - виграшу, що отримується при цьому k (див. рис.1).
Малюнок 1.
Графік залежності виграшу k
від частоти р 2
, при використанні противником стратегії B 1.
Припустимо тепер, що гравець "B" користуватиметься стратегією B 2 у чистому вигляді. Тоді, якщо ми (гравець "A") використовуватимемо чисту стратегію A 1 , то наш виграш становитиме 5. Якщо ж ми будемо використовувати чисту стратегію A 2 , то наш виграш становитиме 3/2 (див. рис. 2). Аналогічно, якщо ми змішуватимемо в різних пропорціях стратегії A 1 і A 2 , наш виграш буде змінюватися по прямій через точки з координатами (0 , 5) і (1 , 3/2), назвемо її лінією стратегії B 2 . Як і в попередньому випадку, абсцис будь-якої точки на цій прямій дорівнює ймовірності, з якою ми застосовуємо стратегію A 2 , а ордината - виграшу, що отримується при цьому, але тільки для стратегії B 2 (див. Рис. 2).
Малюнок 2.
v
та оптимальної частоти р 2
для гравця "А".
У реальній грі, коли розумний гравець "В" користується всіма своїми стратегіями, наш виграш буде змінюватися по ламаній лінії, показаній на мал.2 червоним кольором. Ця лінія визначає так звану нижній кордон виграшу. Очевидно, що сама висока точкацією ламаною відповідає нашій оптимальній стратегії. У даному випадкуце точка перетину ліній стратегій B 1 і B 2 . Зверніть увагу, що якщо вибрати частоту p 2 рівної її абсцисі, то наш виграш залишатиметься незмінним і рівним v при будь-якій стратегії гравця "B", крім того він буде максимальним, який ми можемо собі гарантувати. Частота (імовірність) p 2 У цьому випадку є відповідна частота нашої оптимальної змішаної стратегії. До речі з малюнка 2 видно і частоту p 1 , нашої оптимальної змішаної стратегії, це довжина відрізка [ p 2 ; 1] на осі абсцис. (Це тому що p 1 + p 2 = 1 )
Цілком аналогічно міркуючи, можна знайти і частоти оптимальної стратегії для гравця "В", що ілюструється на малюнку 3.
Малюнок 3.
Графічне визначення ціни гри v
та оптимальної частоти q 2
для гравця "В".
Тільки для нього слід збудувати так звану верхній кордонпрограшу(червона ламана лінія) і шукати у ньому найнижчу точку, т.к. для гравця "В" ціль, це мінімізація програшу. Аналогічно значення частоти q 1 , Це довжина відрізка [ q 2 ; 1] на осі абсцис.
Зміст 1 Загальні відомості 2 1.1 Ігри. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Ходи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Стратегії. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Матрична гра. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Слідова точка. Чисті стратегії 7 2.1 Приклади. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Приклад 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Приклад 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Змішані стратегії 9 3.1 Гра 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Приклади. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Приклад 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Приклад 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Геометрична інтерпретація. . . . . . . . . . . . . . . . . . . . 12 3.2 Ігри 2×n та m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Приклад 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Загальні відомості з теорії ігор 1.1. Теорія ігор - це математична теорія конфліктних ситуацій, тобто. таких ситуацій, у яких стикаються інтереси двох або більше сторін, що мають різні цілі. Гра - це конфліктна ситуація, регламентована певними правилами, в яких мають бути зазначені: можливі варіанти дій учасників кількісний результат гри або платіж (виграш, програш), до якого приводить дана сукупність ходів обсяг інформації кожної сторони про поведінку іншої. Парна гра - гра в якій беруть участь лише дві сторони (два гравці). Парна гра з нульової сумою - парна гра, у якій сума платежів дорівнює нулю, тобто. програш одного гравця дорівнює виграшу другого. Залежно від ставлення кожного з гравців до значення функції виграшу парні ігри поділяються: Парна гра з нульовою сумою (антагоністична) - парна гра, у якій сума платежів дорівнює нулю, тобто. програш одного гравця дорівнює виграшу другого. Неантагоністична гра - парна гра, в якій гравці мають різні, але не прямо протилежні цілі. 2 1.2. Ходи Хід - вибір одного з передбачених правил гри дій здійснення цього вибору Ходи бувають двох типів: Особистий хід - + свідомий вибір одного з передбачених правил гри дій + здійснення цього вибору Випадковий хід - Випадковим ходом називається вибір з ряду можливостей, що здійснюється не рішенням гравця, а якимось механізмом випадкового вибору. Нижче розглядаються парні ігри з нульовою сумою, що містять лише особисті ходи. Кожна сторона не має інформації про поведінку іншої. 3 1.3. Стратегії Стратегія гравця - сукупність правил, що визначають вибір дій при кожному особистому ході цього гравця в залежності від ситуації, що склалася в процесі гри. Залежно від кількості можливих стратегій гри діляться на кінцеві та нескінченні. Нескінченна гра - гра, в якій хоча б у одного з гравців є нескінченне числостратегії. Кінцева гра - гра, у якій кожен гравець має лише кінцеве число- стратегій. Число послідовних ходів у будь-якого з гравців визначає підрозділ ігор на одноходові та багатоходові, або позиційні. + В одноходовій грі кожен гравець робить лише один вибір із можливих варіантів і після цього встановлює результат гри. + Багатоходова, або позиційна, гра розвивається в часі, являючи собою ряд послідовних етапів, кожен з яких настає після перебігу одного з гравців та відповідної зміни обстановки. В одноходовій грі кожен гравець робить тільки один вибір з можливих варіантіві після цього встановлює результат гри. Оптимальна стратегія гравця - стратегія, яка за багаторазового повторення гри забезпечує даному гравцеві максимально можливий середній виграш (або, що те саме, мінімально можливий середній програш). Теоретично ігор всі рекомендації виробляються з припущення про розумному поведінці гравців. Прорахунки та помилки гравців, неминучі в кожній конфліктній ситуації, а також елементи азарту та ризику в теорії ігор не враховуються. 4 1.4. Матрічна гра Матрична гра - одноходова кінцева гра з нульовою сумою. можливих способівдій. Відповідно до обраних способів дій (стратегіями) визначається досягається результат. Розглянемо з прикладу. Нехай є два гравці A та B, один з яких може вибрати i-ю стратегію з m своїх можливих стратегій A1, A2, ... Am, а другий вибирає j-ю стратегію зі своїх можливих стратегій B1, B2, ... Bm. В результаті перший гравець виграє величину aij, а другий програє цю величину. З чисел aij , складемо матрицю a11 a11 ··· a1n a21 a22 ··· a2n A = (aij) = .. .. .. .. . . . . am1 am2 · · · amn Матриця A = (aij), i = 1, m, j = 1, n називається платіжною матрицею або матрицею гри m × n. У цій матриці рядки завжди для стратегій гравця, що виграє (максимізує), тобто гравця, який прагне максимізації свого виграшу. Стовпці відводяться для стратегій гравця B, що програє, тобто гравця, який прагне мінімізації критерію ефективності. Нагадаємо, що позиційна багатоходова гра є теоретико-ігровою моделлю конфліктної ситуації, в якій противники для досягнення своїх цілей послідовно роблять за одним вибором (ходом) з кінцевого числа можливих способів дій на кожному етапі розвитку цієї ситуації. Рішення гри - знаходження оптимальних стратегій обох гравців та визначення ціни гри Ціна гри - очікуваний виграш (програш) гравців. Рішення гри може бути знайдено або в чистих стратегіях - коли гравець повинен дотримуватися однієї єдиної стратегії, або в змішаних, коли гравець повинен з певними ймовірностями застосовувати дві чисті стратегії або більше. Останні у разі називаються активними. 5 Змішана стратегія одного гравця - вектор, кожен з компонентів якого показує частоту використання гравцем відповідної чистої стратегії. Максимін або нижня ціна гри - число α = max min aij i j Максиминна стратегія (рядок) - стратегія, яку вибрав гравець, щоб максимізувати свій мінімальний виграш. Очевидно, що при виборі найбільш обережної максимінної стратегії гравець A забезпечує собі (незалежно від поведінки супротивника) гарантований виграш не менше ніж α. Максимін або верхня ціна гри - число β = min max aij j i Мінімаксна стратегія (стовпець) - стратегія, яку вибрав гравець, щоб мінімізувати свій максимальний програш. Очевидно, що при виборі найбільш обережної мінімаксної стратегії гравець B не дає можливості за жодних обставин гравцеві A виграти більше, ніж β. Нижня ціна гри завжди не перевищує верхню ціну гри α = max min aij 6 min max aij = β i j j i Теорема 1 (основна теорема теорії матричних ігор). Кожна кінцева гра має принаймні одне рішення, можливо, у сфері змішаних стратегій. 6 2. Ігри з сідловою точкою. Розв'язання в чистих стратегіях Гра з сідловою точкою - гра, для якої α = max min aij = min max aij = β i j j i Для ігор з сідловою точкою знаходження рішення полягає у виборі максимінної та міні-макcної стратегій, які є оптимальними. Чиста ціна гри - загальне значеннянижньої та верхньої ціни гри α=β=ν 2.1. Приклади Приклад 1 Знайти рішення у чистих стратегіях гри, заданої матрицею 8 4 7 A= 6 5 9 7 7 8 Рішення: визначимо верхню та нижню ціну гри. Для цього знайдемо мінімальне чисел aij в i-му рядку αi = min aij j і максимальне з чисел aij у j-му стовпці βj = max aij i Числа αi (мінімуми рядків) випишемо поряд із платіжною матрицею праворуч у вигляді додаткового стовпця. Числа βi (максимуми стовпців) випишемо під матрицею у вигляді додаткового рядка: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Знаходимо максимальне з чисел αi α = max αi = 7 i та мінімальне з чи βj β = min βj = 7 j α = β - гра має сідлову точку. Оптимальною стратегією для гравця є стратегія A3 , а для гравця B - стратегія B2 , чиста ціна гри ν = 7 Приклад 2 Задано платіжну матрицю: 2 2 1 1 2 0 1 1 1 1 A= 1 1 2 1 2 1 1 2 Знайти рішення гри у чистих стратегіях. Рішення: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Гра має шість сідлових точок. Оптимальними стратегіями будуть: A1 і B3 або B4 A3 і B3 або B4 A4 і B3 або B4 8 3. Рішення гри у змішаних стратегіях При α = β. у випадку, коли при виборі своїх стратегій обидва гравці не мають інформації про вибір іншого, гра має рішення у змішаних стратегіях. SA = (p1, p2, ..., pm) - змішана стратегія гравця A, в якій стратегії A1, A2, ..., Am застосовуються про ймовірності ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, mi = 1 SB = (q1 , q2 , ..., qn) - змішана стратегія гравця B , в якій стратегії B1 , B2 , ..., Bm застосовуються про ймовірності ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Якщо: SA∗ - оптимальна стратегія гравця A , SB∗ - - оптимальна стратегія гравця B , то ціна гри - ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Наступна теорема дає відповідь на питання, як знайти рішення для ігор 2×2, 2×n, m×2 Теоремма 2 (як знайти рішення для ігор 2×2, 2×n, m×2). Якщо один із гравців застосовує оптимальну змішану стратегію, то його виграш дорівнює ціні гри ν незалежно від того, з якими ймовірностями буде застосовувати другий гравець стратегії, що увійшли до оптимальної (в тому числі й чистої стратегії). 9 3.1. Гра 2×2 Розглянемо гру 2×2 про матрицю: () a11 a21 a21 a22 Нехай гра не має рішення у чистих стратегіях. Знайдемо оптимальні стратегії SA∗ та SB∗. Спочатку визначимо стратегію SA∗ = (p∗1, p∗2). Відповідно до теореми, якщо сторона A дотримуватиметься стратегії ν, то незалежно від способу дій сторони B виграш залишатиметься рівним ціні гри ν. Отже, якщо сторона A дотримується оптимальної стратегії SA∗ = (p∗1 , p∗2), то сторона B може, не змінюючи виграшу, застосовувати будь-яку зі своїх стратегій. Тоді при застосуванні гравцем B чистої стратегії B1 або B2 гравці отримає середній виграш рівний ціні гри: a11 p∗1 + a21 p∗2 = ν ← при стратегії B1 a12 p∗1 + a22 p∗2 = ν ← при стратегії B2 Приймаючи у увага, що p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Ціна гри: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Аналогічно знаходиться оптимальна стратегія гравця B: SB∗ = (q1∗ , q2∗). Зважаючи на те, що q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Приклади Приклад 3 Знайти рішення гри з матрицею () −1 1 A= 1 −1 10 Рішення: гра не має сідлової точки, оскільки α= -1, β = 1, α ̸= β. Шукаємо рішення у змішаних стратегіях. За формулами для p∗ та q ∗ отримуємо p∗1 = p∗2 = 0.5 і q1∗ = q2∗ = 0.5, ν = 0 Таким чином, SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5) Приклад 4 Знайти рішення гри з матрицею () 2 5 A= 6 4 Рішення: гра не має сідлової точки, оскільки α= 4, β = 5, α ̸= β. Шукаємо рішення у змішаних стратегіях. За формулами для p∗ та q ∗ отримуємо p∗1 = 0.4, p∗2 = 0.6 та q1∗ = 0.2 q2∗ = 0.8, ν = 4.4 Таким чином, SA∗ = (0.4, 0.6) SB∗ = (0.2, 0.8) 11 3.1.2. Геометрична інтерпретація Ігри 2×2 можна дати просту геометричну інтерпретацію. Візьмемо одиничну ділянку осі абсцис, кожній точці якого поставимо у відповідність деяку змішану стратегію S = (p1 , p2) = (p1 , 1 − p1) причому ймовірність p1 стратегії A1 дорівнюватиме відстані від точки SA до правого кінця ділянки, а ймовірність p2, стратегії A2 - відстані до лівого кінця. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ Зокрема, лівий кінець ділянки (крапка з абсцисою = 0) відповідає стратегії A1 , правий кінець ділянки (x = 1) - стратегії A2 На кінцях ділянки відновлюються два перпендикуляри до осі абсцис: вісь I - I - відкладається виграш при стратегії A1 вісь II - II - відкладається виграш за стратегії A2 Нехай гравець B застосовує стратегію B1; вона дає на осях I - I і II - II відповідно точки з ординатами a11 і a21. Проводимо через ці точки пряму B1−B1′. За будь-якої змішаної стратегії SA = (p1 , p2) виграш гравця визначається точкою N на прямій B1 −B1′ , що відповідає точці SA на осі абсцис, що ділить відрізок щодо p2: p1 . Очевидно, таким же способом може бути побудована і пряма B2 − B2′ , що визначає виграш при стратегії B2 . 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Необхідно знайти оптимальну стратегію SA∗ , тобто. таку, за якої мінімальний виграш гравця A (за найгіршої для нього поведінки гравця B) звертався б у максимум. І тому будуватися нижня межа виграшу гравця A при стратегіях B1 , B2 , тобто. ламана B1 N B2′;. На цьому кордоні лежатиме мінімальний виграш гравця A за будь-якої його змішаної стратегії, точка N , в якій цей виграш досягає максимуму та визначає рішення та ціну гри. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ордината точки N є нічим іншим, як ціна гри ν, її абсцис дорівнює ∗2 , а відстань до правого кінця відрізка дорівнює ∗1 , тобто. відстань від точки SA∗ до кінців відрізка дорівнюють ймовірностям ∗2 і ∗1 стратегій A2 та A1 оптимальної змішаної стратегії гравця A. в даному випадку рішення гри визначалося точкою перетину стратегій B1 та B2. Нижче наведено випадок, коли оптимальною стратегією гравця є чиста стратегія A2 . Тут стратегія A2 (при будь-якій стратегії противника) вигідніша за стратегію A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I.I. .x.I. .x. 2∗ P . A∗ S = A2. 2∗ P . A∗ S = A2 Правіше показаний випадок, коли явно невигідна стратегія є у гравця B. Геометрична інтерпретація дає можливість наочно зобразити також нижню ціну гри α і верхню β .y .I .I .I I .B2 .B1′ .N .B1 . B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P На тому ж графіку можна дати і геометричну інтерпретацію оптимальних стратегій гравця B . Неважко переконатися, що частка q1∗ стратегії B1 оптимальної змішаної стратегії SB∗ = (q1∗ , q2∗) дорівнює відношенню довжини, відрізка KB2 до суми довжин відрізків KB1 і KB2 на осі I −I: .y .I .I . B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 або LB2′ q1∗ = LB2′ + LB1′ Оптимальну стратегію SB∗ = (q1∗ , q2∗) можна знайти й іншим способом, якщо поміняти місцями гравців B та B, а замість максимуму нижньої межі виграшу розглянути мінімум верхньої межі. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Ігри 2×n та m×2 Розв'язання ігор 2×n та m×2 ґрунтується на наступній теоремі. Теоремма 3. Будь-яка кінцева гра m × n має рішення, в якому число активних стратегій кожної сторони не перевищує найменшого з чисел m і n. Відповідно до цієї теореми у гри 2 × n завжди є рішення, в якому кожен гравець має не більше двох активних стратегій. Варто тільки знайти ці стратегії, і гра 2×n перетворюється на гру 2×2, яка вирішується елементарно. Знаходження активних стратегій може виконуватись графічним способом: 1) будується графічна інтерпретація; 2) визначається нижня межа виграшу; 3) виділяються на нижній межі виграшу дві стратегії другого гравця, яким відповідають дві прямі, що перетинаються в точці з максимальною ординатою (якщо в ній перетинаються більше двох прямих, береться будь-яка пара) - ці стратегії є активними стратегіями гравця B. Таким чином , гра 2 × n зведена до гри 2 × 2. Також може бути вирішена гра m × 2 з тією різницею, що будується не нижня, а верхня межа виграшу і на ній шукається не максимум, а мінімум. Приклад 5 Знайти рішення гри () 7 9 8 A= 10 6 9 Рішення: використовуючи геометричний метод, виділяємо активні стратегії. Прямі B1 − B1′, B2 − B2′ та B3 − B3′ відповідають стратегіям B1, B2, B3. Ламана B1 N B2 – нижня межа виграшу гравця. Гра має рішення S∗A = (23, 31); S∗B = (0.5; 0.5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .x. 2∗ P . A∗ S . 1∗ P 17 Предметний покажчик гра, 2 хід, 3 2 × 2, 10 особистий, 3 2 × 2, 9 випадковий, 3 геометрія, 12 чиста ціна гри, 7 приклади, 10 2 × n, 9, 16 m × 2, 9, 16 нескінченна, 4 у нормальній формі, 5 кінцева, 4 багатоходова, 4 одноходова, 4 матрична, 5 парна, 2 c нульовою сумою, 2 антагоністична, 2 неантагоністична, 2 рішення, 5 у змішаних стратегіях, 5, 9 у чистих стратегіях , 5 з сідловою точкою, 7 ціна, 5 верхня, 6 нижня, 6 чиста, 7 максимін, 6 матриця гри, 5 платіжна, 5 мінімакс, 6 нормалізація гри, 5 стратегія, 4 максимінна, 6 мінімаксна, 6 оптимальна, 4 змішана 5 теорія ігор, 2 18
Із популярного американського блогу Cracked.
Теорія ігор займається тим, що вивчає способи зробити найкращий хід і в результаті отримати якомога більший шматок виграшного пирога, відчепивши частину його в інших гравців. Вона вчить аналізувати безліч факторів і робити логічно зважені висновки. Я вважаю, що її потрібно вивчати після цифр і до алфавіту. Просто тому, що надто багато людей приймають важливі рішення, ґрунтуючись на інтуїції, таємних пророцтвах, розташуванні зірок та інших подібних. Я ретельно вивчив теорію ігор, і тепер хочу розповісти вам про її засади. Можливо, це додасть здорового глузду у ваше життя.
1. Дилема ув'язненого
Берто і Роберт заарештували за пограбування банку, не зумівши правильно використовувати для втечі викрадений автомобіль. Поліція не може довести, що саме вони пограбували банк, але спіймала їх на місці злочину в вкраденому автомобілі. Їх розвели по різних кімнатах і кожному запропонували угоду: здати спільника та відправити його за ґрати на 10 років, а самому вийти на волю. Але якщо вони обидва здадуть один одного, то кожен отримає по 7 років. Якщо ж ніхто нічого не скаже, то обидва сядуть на 2 роки тільки за викрадення автомобіля.
Виходить, що коли Берто мовчить, але Роберт здає його, Берто сідає у в'язницю на 10 років, а Роберт виходить на волю. Кожен ув'язнений - гравець, і вигода кожного може бути представлена у вигляді "формули" (що отримають вони обидва, що отримає інший). Наприклад, якщо я вдарю тебе, моя виграшна схема буде виглядати так (я отримую грубу перемогу, ти страждаєш від сильного болю). Оскільки кожен в'язень має два варіанти, ми можемо представити результати в таблиці.
Практичне застосування: Виявлення соціопатів
Тут ми бачимо основне застосування теорії ігор: виявлення соціопатів, які думають лише себе.Справжня теорія ігор - це потужний аналітичний інструмент, а дилетантство часто служить червоним прапором, що з головою видає людину, позбавлену поняття честі. Люди, які роблять розрахунки інтуїтивно, вважають, що краще вчинити некрасиво, тому що це призведе до більш короткого терміну в'язниці незалежно від того, як надійде інший гравець. Технічно це правильно, але тільки якщо ви недалекоглядна людина, яка ставить цифри вище людських життів. Саме тому теорія гра така популярна у сфері фінансів.
Справжня проблема дилеми ув'язненого у цьому, що вона ігнорує дані.Наприклад, у ній не розглядається можливість вашої зустрічі з друзями, родичами, або навіть кредиторами людини, яку ви ув'язнили на 10 років.
Найгірше те, що всі учасники дилеми ув'язненого діють так, ніби ніколи не чули її.
А найкращий хід - зберігати мовчання, і за два роки разом із добрим другом користуватися спільними грошима.
2. Домінуюча стратегія
Це ситуація, за якої ваші дії дають найбільший виграшнезалежно від дій опонента.Що б не відбувалося – ви все зробили правильно. Ось чому багато людей при «дилемі ув'язненого» вважають: зрада призводить до «найкращого» результату незалежно від того, що робить інша людина, а ігнорування дійсності, властиве цьому методу, змушує виглядати супер-просто.
Більшість ігор, в які ми граємо, не мають строго домінуючих стратегій, бо інакше вони були б просто жахливими. Уявіть, що ви завжди робили б те саме. У грі «камінь-ножиці-папір» немає домінуючої стратегії. Але якби ви грали з людиною, у якої на руках одягнені прихватки, і вона могла показати тільки камінь або папір, у вас була б домінуюча стратегія: папір. Ваш папір оберне його камінь або приведе до нічиєї, і ви не зможете програти, тому що суперник не може показати ножиці. Тепер, коли у вас є домінуюча стратегія, потрібно бути дурнем, щоб спробувати щось інше.
3. Битва статей
Ігри цікавіші, коли у них немає строго домінуючої стратегії. Наприклад, битва статей. Анджалі та Борислав йдуть на побачення, але не можуть вибрати між балетом та боксом. Анджалі любить бокс, тому що їй подобається, коли ллється кров на радість глядачів, які кричать натовпу, які вважають себе цивілізованими тільки тому, що вони заплатили за чиїсь розбиті голови.
Борислав хоче дивитися балет, тому що він розуміє, що балерини проходять через велика кількістьтравм і найскладніших тренувань, знаючи, що одна травма може покласти край усьому. Артисти балету - найбільші спортсменина землі. Балерина може вдарити вас ногою в голову, але ніколи цього не зробить, тому що її нога коштує набагато дорожче за ваше обличчя.
Кожен з них хоче піти на свій улюблений захід, але вони не хочуть насолоджуватися ним наодинці, таким чином отримуємо схему їхнього виграшу: найбільше значення- робити те, що їм подобається, найменше значення- просто бути з іншою людиною, і нуль – бути на самоті.
Деякі люди пропонують вперто балансувати на межі війни: якщо ви, незважаючи ні на що, робите те, що хочете, інша людина має підлаштуватися на вибір або втратити все. Як я вже казав, спрощена теорія ігор добре виявляє дурнів.
Практичне застосування: Уникайте гострих кутів
Звичайно, і ця стратегія має свої значні недоліки. Насамперед, якщо ви ставитеся до ваших побачень як до «битви підлог», вона не спрацює. Розлучіться, щоб кожен з вас міг знайти людину, яка їй сподобається. А друга проблема полягає в тому, що у цій ситуації учасники настільки не впевнені у собі, що не можуть цього зробити.
По-справжньому виграшна стратегія для кожного – робити те, що вони хочуть,а потім, або наступного дня, коли вони будуть вільні, піти разом до кафе. Або чергувати бокс і балет, поки у світі розваг не відбудеться революція і не буде винайдено боксерський балет.
4. Рівновага Неша
Рівновага Неша - це набір ходів, де ніхто не хоче зробити щось по-іншому після доконаного факту.І якщо ми зможемо змусити це працювати, теорія ігор замінить усю філософську, релігійну та фінансову систему на планеті, тому що «бажання не прогоріти» стало для людства потужнішим. рушійною силоюніж вогонь.
Давайте швидко поділимо 100 $. Ви і я вирішуємо, скільки з сотні ми вимагаємо та одночасно озвучуємо суми. Якщо наша Загальна сумаменше ста, кожен одержує те, що хотів. Якщо Загальна кількістьбільше ста, той, хто попросив найменшу кількість, отримує бажану суму, а жадібніша людина отримує те, що залишилося. Якщо ми просимо однакову суму, кожен отримує 50$. Скільки ви попросите? Як ви поділите гроші? Існує єдиний виграшний перебіг.
Вимога 51$ дасть вам максимальну сумунезалежно від того, що вибере ваш супротивник. Якщо він попросить більше, ви отримаєте 51$. Якщо він попросить 50$ або 51$, ви отримаєте 50$. І якщо він попросить менше 50$, ви отримаєте 51$. У будь-якому випадку немає жодного іншого варіанту, який принесе вам більше грошей, ніж цей. Рівновага Неша - ситуація, в якій ми обидва вибираємо 51$.
Практичне застосування: спочатку думайте
У цьому суть теорії ігор. Не обов'язково виграти і тим більше нашкодити іншим гравцям, але обов'язково зробити найкращий для себе хід незалежно від того, що підготують для вас оточуючі. І навіть краще, якщо цей хід буде вигідним і для інших гравців. Це свого роду математика, яка б змінити суспільство.
Цікавий варіант цієї ідеї – розпиття спиртного, яке можна назвати Рівновагою Неша з тимчасовою залежністю. Коли ви досить багато п'єте, то не дбаєте про вчинки інших людей незалежно від того, що вони роблять, але наступного дня ви дуже шкодуєте, що не вчинили інакше.
5. Гра в орлянку
В орлянці беруть участь Гравець 1 та Гравець 2. Кожен гравець одночасно вибирає орла чи решку. Якщо вони вгадують, Гравець 1 отримує пенс Гравця 2. Якщо ж ні – Гравець 2 отримує монету Гравця 1.
Виграшна матриця проста…
…оптимальна стратегія: грайте повністю навмання.Це складніше, ніж ви думаєте, тому що вибір має бути абсолютно випадковим. Якщо у вас є переваги орла або решки, противник може використовувати його, щоб забрати гроші.
Звичайно, справжня проблема тут полягає в тому, що було б набагато краще, якби вони просто кидали один пенс один одному. В результаті їх прибуток був би таким самим, а отримана травма могла б допомогти цим нещасним людям відчути щось, крім жахливої нудьги. Адже це найгірша граз існуючих будь-коли. І це ідеальна модель для пенальті серії.
Практичне застосування: Пенальті
У футболі, хокеї та багатьох інших іграх, додатковий час – це серія пенальті. І вони були б цікавішими, якби будувалися на тому, скільки разів гравці в повній формізможуть зробити «колесо», бо це принаймні було б показником їхніх фізичних здібностей і на це було б смішно подивитися. Воротарі не можуть чітко визначити рух м'яча або шайби на самому початку їхнього руху, тому що, на превеликий жаль, у наших спортивних змаганнях роботи все ще не беруть участі. Воротар повинен вибрати лівий або правий напрямок і сподіватися, що його вибір збігається з вибором супротивника, який б'є по воротах. У цьому є щось спільне із грою в монетку.
Однак зверніть увагу, що це не ідеальний приклад подібності з грою в орла і решку, тому що навіть при правильному виборінапрямки воротар може не зловити м'яч, а нападник може не влучити у ворота.
Отже, який наш висновок відповідно до теорії ігор? Ігри з м'ячем повинні закінчуватися способом «мультим'ячу», де кожну хвилину гравцям віч-на-віч виводиться додатковий м'яч/шайба, до отримання однієї зі сторін певного результату, який був показником справжньої майстерності гравців, а не ефектним випадковим збігом.
Зрештою, теорія ігор повинна використовуватися для того, щоб зробити гру розумнішою. Отже краще.
Теорія ігоряк розділ дослідження операцій – це теорія математичних моделей прийняття оптимальних рішень за умов невизначеності чи конфлікту кількох сторін, мають різні інтереси. Теорія ігор досліджує оптимальні стратегії ситуаціях ігрового характеру. До них належать ситуації, пов'язані з вибором найвигідніших виробничих рішень системи наукових та господарських експериментів, організацією. статистичного контролю, господарських взаємин між підприємствами промисловості та інших галузей Формалізуючи конфліктні ситуаціїматематично, їх можна як гру двох, трьох тощо. гравців, кожен із яких має на меті максимізації своєї вигоди, свого виграшу за рахунок іншого.Розділ "Теорія ігор" представлений трьома онлайн-калькуляторами:
- Оптимальні стратегії гравців. У таких завданнях задана платіжна матриця. Потрібно знайти чисті чи змішані стратегії гравців та, ціну гри. Для вирішення необхідно вказати розмірність матриці та метод рішення. У сервісі реалізовано наступні методирішення гри двох гравців:
- Мінімакс. Якщо потрібно знайти чисту стратегію гравців або відповісти на питання про сідлову точку гри, виберіть цей метод рішення.
- Симплекс-метод. Використовується на вирішення гри у змішаних стратегіях методами лінійного програмування.
- Графічний метод. Використовується для вирішення гри у змішаних стратегіях. Якщо є сідлова точка, рішення припиняється. Приклад: За заданою платіжною матрицею знайти оптимальні змішані стратегії гравців та ціну гри, використовуючи графічний методрішення гри.
- Ітераційний метод Брауна-Робінсона. Ітеративний метод застосовується тоді, коли не застосовується графічний метод і коли практично не застосовуються алгебраїчний і матричний методи. Цей метод дає наближене значення ціни гри, причому справжнє значення можна отримати з будь-яким потрібним ступенем точності. Цей метод недостатній для знаходження оптимальних стратегій, але дозволяє відслідковувати динаміку покрокової гри і визначити ціну гри для кожного з гравців на кожному кроці.
У всіх методах застосовується перевірка на домінуючі рядки та стовпці. - Біматрична гра. Зазвичай у такій грі задають дві матриці однакового розміру виграшів першого та другого гравців. Рядки цих матриць відповідають стратегіям першого гравця, а стовпці матриць – стратегіям другого гравця. При цьому у першій матриці представлені виграші першого гравця, а у другій матриці – виграші другого.
- Ігри з природою. Використовується, коли потрібно вибрати управлінське рішенняза критеріями Максимакса, Байєса, Лапласа, Вальда, Севіджа, Гурвіца.
Для критерію Байєса необхідно також запровадити ймовірність настання подій. Якщо вони не задані, залиште значення за промовчанням (будуть рівнозначні події).
Для критерію Гурвіца вкажіть рівень оптимізму λ. Якщо в умовах цього параметра не заданий можна використовувати значення 0, 0.5 і 1 .
Багато завданнях потрібно шукати рішення засобами ЕОМ. Одним з інструментів є вищенаведені послуги та функції
