ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Розв’язання гри у мішаних стратегіях

Загрузка...

Якщо гра не має сідлової точки, то застосування чистих стратегій не дає оптимального розв’язку гри. В такому випадку одержати оптимальний розв’язок можна випадковим чином перебираючи чисті стратегії.

Мішаною стратегією SА гравця А називається застосування чистих стратегій А1, А2,…, Аm з ймовірностями p1, p2,…, pm. При цьому очевидно, що .

Мішані стратегії гравця А записують у вигляді матриці

,

або .

Аналогічно, мішані стратегії гравця В позначаються так:

,

або .

Чисті стратегії можна вважати окремим випадком мішаних у випадку, коли чистій стратегії відповідає ймовірність 1, а ймовірність інших стратегій дорівнює 0.

На основі принципу мінімакса визначається оптимальний розв’язок (або розв’язок) гри: це пара оптимальних стратегій , які мають наступні властивості: якщо один з гравців додержується своєї оптимальної стратегії, то іншому не може бути вигідним відходити від своєї. Виграш, що відповідає оптимальній стратегії (ціна гри v), задовольняє нерівності

avb.

Введемо в розгляд функцію виграшу

.

Гравець А орієнтується на найгірше, тобто на втрати, що дорівнюють мінімуму функції виграшу F(SA,SB) по всім стратегіям гравця В, тобто грає роль ai.

Тоді найкращою стратегією для гравця А є та, на якій буде досягнуто – це грає роль a.

Аналогічно для гравця В найкращою стратегією буде та, на якій буде досягнуто – це грає роль b.

Виникає питання: чи існують оптимальні мішані стратегії гравців , на яких гравець А має найбільший виграш і відповідно гравець В – найменший програш.

На це питання дає відповідь основна теорема теорії ігор – теорема Неймана.

Будь-яка матрична гра має ціну v в мішаних стратегіях, яка досягається у процесі використанні оптимальних мішаних стратегій , тобто

.

З цієї теореми випливають наступні висновки:

Теорема 1 Стратегії оптимальні тоді і тільки тоді, коли виконується умова

.

Тобто, якщо гравець В застосовує оптимальну стратегію , то кращою відповіддю на це є застосування гравцем А стратегії . І якщо гравець А застосовує оптимальну стратегію , то кращою відповіддю на це є застосування гравцем В стратегії .

Перш ніж сформулювати другу теорему, що випливає з основної теореми, дамо наступне означення.

Стратегії, які входять до складу оптимальних мішаних стратегій з ненульовими ймовірностями, називаються активними стратегіями.

Теорема 2 Якщо гравець В застосовує оптимальну мішану стратегію , а гравець А застосовує активну стратегію Аі, то . Аналогічно,

.

Ігри 2x2

Така гра є найпростішим випадком гри. Якщо така гра має сідлову точку, то оптимальний розв’язок – це пара чистих стратегій, що відповідають цій точці.

Гра, в якій відсутня сідлова точка, відповідно до основної теореми теорії ігор, має оптимальний розв’язок, який визначається парою мішаних стратегій , .

Нехай платіжна матриця має вигляд

.

Для того, щоб знайти оптимальні мішані стратегії , скористуємося теоремою 2.

,

.

Ми одержали систему рівнянь для визначення p* і v. Аналогічним чином шукаємо стратегію :

.

Звідси вже можна знайти q* і шукати вже не потрібно.

Приклад. Розв’язати гру «вірю – не вірю».

Правила цієї гри розглянуті в 6.1 і там же знайдена платіжна матриця цієї гри

.

Розв’язання. Оптимальні мішані стратегії гравця А , гравця В , a=0, b=1. Тоді

,

.

Розв’язуючи цю систему рівнянь, знаходимо

,

.

Тоді

.

Таким чином, оптимальні мішані стратегії гравців А і В такі:

.

Ціна гри дорівнює 0,2. Це означає, що гравець А в шести випадах з 10 має казати «правду», а в решті 4 – «неправду». Гравець В у восьми випадках з 10 має «вірити», а в решті – не вірити. Середній виграш в цій грі дорівнює

0,2 грн.

5.4 Геометрична інтерпретація гри

Розв’язання гри допускає наглядну геометричну інтерпретацію. Запишемо платіжну матрицю цієї гри:

.

Мішані стратегії гравців

.

За теоремою 2 маємо:

,

.

З точки зору геометрії маємо рівняння двох прямих в системі координат (p,v):

v = a11 p + a21 (1–p),

v = a12 p + a22 (1–p).

Побудуємо графіки цих прямих.

Гравець А розраховує на min(F(SA,B1), F(SA,B1)) – жирно виділена ламана на графіку. Він гарантовано одержує виграш на цій ламаній і, очевидно, вибирає на ній найвищу точку. Координати цієї точки (p*,v) задають ціну гри v і оптимальну мішану стратегію гравця А:

.

Для гравця В за теоремою 2 маємо:

.

Так само в системі координат (q,v) побудуємо прямі

v = a11 q + a12 (1– q)

v = a21 q + a22 (1– q)

Гравець В розраховує на max(F(A1,SB), F(A2,SB)) – жирно виділена ламана на графіку. Він гарантовано одержує програш на цій ламаній і, очевидно, вибирає на ній найнижчу точку. Координати цієї точки (q*,v) задають ціну гри v і оптимальну мішану стратегію гравця B:

.

Приклад. Розв’язати геометрично гру з платіжною матрицею

,

.

Будуємо відповідні прямі

Знайдемо координати точки перетину прямих

2p–3(1–p) = –p+4(1–p),

10p = 7, p*=0,7,

v = 2·0,7–3·0,3=0,5.

– оптимальна мішана стратегія гравця А.

Для гравця В

,

3q=1,5, q*=0,5.

– оптимальна мішана стратегія гравця B.

Ціна гри v=0,5.

5.5 Розв’язання ігор та

Такі ігри мають наступні платіжні матриці:

.

Ці ігри краще за все розв’язувати геометрично.

Для визначеності розглянемо гру і застосуємо теорему 2, враховуючи, що мішана стратегія гравця А має вигляд

.

Тоді

,

,

… ,

.

Далі будуємо графіки всіх прямих і обираємо нижню ламану, тобто ламану min(F(SA,B1), F(SA,B1),…, F(SA,Bn)), а потім найвищу точку цієї ламаної. Її координати (p*,v) задають ціну гри v і оптимальну мішану стратегію гравця А. Відрізки цієї ламаної відокремлюють також і активні стратегії гравця В. Решта стратегій не грають ніякої ролі. На активних стратегіях гравця В шукаємо, знаючи ціну гри v, оптимальну мішану стратегію .

Аналогічно розв’язується і гра , але в ній обирають верхню ламану max(F(A1,SB), F(A2,SB),…, F(Am,SB)), а в ній найнижчу точку та її координати.

Приклад. Розв’язати гру з платіжною матрицею

.

Розв’язання. Перш за все зауважимо, що стратегія А2 є більш вдалою, ніж А1 і А4. Тобто зрозуміло, що А1 і А4 – неактивні стратегії, і платіжна матриця стає такою:

, .

Застосуємо теорему 2.

,

,

,

.

Будуємо відповідні прямі

Нижня точка виділеної ламаної знаходиться на перетині ліній і , тобто стратегії А2 і А3 є активними. Розв’яжемо систему відповідних рівнянь

2q+1=-5q+3, 7q=2,

.

Таким чином, оптимальна мішана стратегія гравця В має вигляд

.

Далі знайдемо оптимальну мішану стратегію гравця А. Ми вже знаємо, активними стратегіями гравця А є А2 і А2, тобто

.

Тоді

, , .

Таким чином, оптимальна мішана стратегія гравця А

.

Ціна гри .

5.6 Розв’язання ігор

Ігри можуть бути розв’язані трьома методами:

1) розв’язанням відповідних систем лінійних рівнянь;

2) методами лінійного програмування;

3) наближеними методами.

Розглянемо кожен з методів окремо.

І Метод розв’язання системи лінійних рівнянь.

Розглянемо приклад – гру «монетка під пару». Правила гри. Кожний з двох гравців має монети 5, 10, 25 коп. За командою обидва гравці показують свої монети. Якщо монети однакові, тоді вони переходять гравцю А, якщо різні – гравцю В. Розв’язати гру.

Розв’язання. Складемо матрицю платежів цієї гри. Кожен гравець має три стратегії: А1 – 5 к., А2 – 10 к., А3 – 25 к., теж саме для гравця В. Тоді

.

Мішана стратегія гравця А

.

Складаємо систему рівнянь

.

Розв’язуючи цю систему рівнянь, одержимо

,

.

Таким чином, оптимальна стратегія гравця А така:

.

Перейдемо до гравця В.

.

Складаємо систему рівнянь

.

Розв’язуючи цю систему рівнянь, одержимо

і , ціна гри .

ІІ Зведення матричної гри до задачі лінійного програмування.

Якщо в матриці платежів є від’ємні елементи, то потрібно додати до кожного елемента матриці таке число, щоб всі елементи стали додатними. Розв’язувати гру методом лінійного програмування потрібно за новою матрицею, а потім від ціни гри відняти те число, яке додавали до елементів матриці.

Гравець А застосовує стратегію , а гравець В відповідає стратегією Вj.

Тут v>0 – ціна гри за новою матрицею.

Розділимо обидві частини нерівностей на v і введемо позначки

,

де xi ≥ 0, i=0,1,…,m.

Гравець А намагається збільшити ціну гри v. Тоді одержуємо таку задачу лінійного програмування:

Аналогічними діями одержимо задачу лінійного програмування для гравця В, враховуючи те, що гравець В бажає зменшити ціну гри v.

де .

ІІІ Наближений метод розв’язання ігор .

Розглянемо наближений метод, що має назву метод Брауна–Дж.Робінсон. Він складається з наступного. Проводиться багато партій гри, причому на кож­ному n–му кроці сторона В вибирає таку свою чисту стратегію, яка найкращим чином протидіє накопиченому виграшу сторони А при перших (n–1) ходах. Аналогічним чином діє і сторона А при виборі своєї стратегії.

Приклад. Розв’яжемо гру з платіжною матрицею

.

Літерою «с» позначимо виграш. Якщо зустрінуться однакові числа «с», то будемо вибирати стратегію з меншим номером (за нижчеподаною таблицею).

N партії к Вибір Аі Сумарний виграш гравця А при стратегіях Вj Вибір Bj Сумарний виграш гравця B при стратегіях Ai
B1 B2 B3 A1 A2 A3
A3 B1 4,5
A1 1+8 7+2 3+4 B3 4+6 1+3
A1 9+8 9+2 7+4 B2 12+2 4+7
A2 16 B2 4,5
A2 21 4,2 B2 4,6
A2 26 B2
A3 30 B1
A2 34 B1 4,5
A2 38 B1
A1 45 4,5 B2 4,7 4,6

Зроблено 10 кроків задачі. Послідовність чисел в останньому стовпці збігається до ціни гри.

За 10 кроків стратегія А1 зустрілась 3 рази, А2 – 5 разів, А3 – 2 рази, В1 – 4 рази, В2 – 5 разів, В3 – 1 раз. Тоді емпіричні оптимальні мішані стратегії на 10 кроках такі:

, .

Якщо кількість партій прямує до нескінченності, то емпіричні стратегії прямують до оптимальних стратегій.

 

Питання для самоперевірки

1 Що таке матрична гра?

2 Шо таке платіжна матриця?

3 Що таке нижня та верхня ціна гри, зв'язок між ними?

4 Що таке функція виграшу?

5 Що називається ціною гри?

6 Наведіть основну теорему теорії гри.

7 Що таке мішана стратегія?

8 Що таке чиста стратегія?

9 Що таке активна стратегія?

10 Сформулюйте основну теорему теорії гри.

11 Як розв’язується гра 2x2?

12 Дати геометричну інтерпретацію гри 2x2.

13 Як застосовується геометрична інтерпретація для розв’язання ігор 2xn і mx2?

14 Які існують методи розв’язання ігор mxn?

 

Задачі для самостійної роботи

1 Побудувати платіжну матрицю для гри за наступним правилом.

Кожний з двох гравців має 3 монети номіналом 5; 10; 25 копійок. Обидва гравця одночасно показують по одній монеті. Якщо монети однакові, то вони переходять до першого гравця, якщо різні − до другого.

2 Гра полковника Блотто.

Полковник має 5 полків і захищає дві рівноцінні позиції. Його противник має 4 полки і атакує ці позиції. Кожний з противників може виділити цілу кількість полків. Полковник виграє 1 грошову одиницю, якщо на кожній з позицій зосередить не менше полків, ніж його противник. У всіх інших випадках він програє 1 грош. одиницю. Скласти матрицю гри.

 

3 Розв’язати гру при заданій платіжній матриці.

Варіант 1 Варіант 2

. .

Варіант3

.

4 Розв’язати гру при заданій платіжній матриці за допомогою системи лінійних рівнянь.

Варіант 1 Варіант 2

. .

5 Розв’язати гру при заданій платіжній матриці методом лінійного програмування.

.

6 Розв’язати гру при заданій платіжній матриці геометрично.

.


Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти