Ігри двох осіб з довільною сумою, страница 3

Природно, що така рівновага гравця А не задовольнить, бо дуже привабливим для нього є а21=1000. Тому гравець А всіма «правдами та не правдами» буде домагатись домовленості з гравцем В грати (А21), щоб вкінці гри зі свого виграшу компенсувати шляхом доплати гравцеві В його згоду грати цей профіль стратегій (одержимо гру з побічними платежами).

? Приклад 3.4. Знайти РН в грі

К

Л

М

А

2,3

-4,-1

-5,4

Б

-1,-3

0,-2

1,-4

В

3,2

-2,-1

-3,1

В цій  грі, за описаним вище алгоритмом, маємо 2 сукупності стратегій, які задають рівновагу Неша – це подвійно-відмічені стратегії (Б, Л) та (В,К). Очевидно, що ситуація (В,К) вигідніша ніж (Б, Л) для обох гравців. Та навіть в такій очевидній на перший погляд грі в плані вибору РН все ж попередня домовленість не буде зайвою.

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

SA(p1,p2,…pm), SB (q1,q2,…qn). Тоді середні виграші гравців А і В знаходимо відповідно (математичні сподівання): (3.3)

Означення 3.4. Стратегії  S*A(p*1,p*2,…p*m),  S*B (q*1,q*2,…q*n) визначають рівноважну ситуацію, якщо одночасно виконуються нерівності

EA(A,S*A,S*B) ≥ EA(A,SA,S*B); EB(B,S*A,S*B) ≥ EB(B,S*A,SB)         (3.4)

          Маємо математичну модель для пошуку РН в змішаних стратегіях гри двох осіб з довільною сумою, що складається з матриці гри (3.1), співвідношень (3.3) та нерівностей (3.4). Проблема пошуку РН тісно пов’язана з аналізом найкращих відповідей Ri(s-i) гравця і на профіль стратегій s-i на профіль стратегій інших гравців.

          Складемо профіль найкращих відповідей всіх гравців

R(s) = (Ri(s-i), iÎN). Зрозуміло, що s* є РН тоді і тільки тоді, коли

s*Î R(s*). Таким чином існування РН тісно пов’язане з існуванням нерухомих точок відображення найкращих відповідей .

Оскільки середні виграші гравців задані функціями, що представляють полілінійні форми (3.3), то якщо зафіксувати змішані стратегії одного з гравців, середній виграш іншого стає лінійною функцією відносно його змішаних стратегій, а отже максимум цієї функції досягається в крайніх точках, тобто на чистих стратегіях. Тому, потрібно взяти всі найкращі відповіді в чистих стратегіях, та взяти всі змішані стратегії, котрі приписують ненульові ймовірності тільки оптимальним відповідям в чистих стратегіях.

          Алгоритм пошуку РН в змішаних стратегіях.

Ø Для кожного гравця виділяється деяка підмножина S0i ÍSi чистих стратегій і складається система рівнянь

Ei(si,m-i) = ci, " siÎ S0i, iÎN. В цій системі змінними є числа ci та ймовірності mj(sj) при sjÎ S0jІнші mj(sj) приймаються рівними 0, враховуючи умову . Якщо гравців тільки двоє, то система є лінійною, що обговорювалось раніше. Якщо гравців більше, то рішення такої нелінійної системи ускладнюється.

Ø Після знаходження рішення потрібно перевірити ймовірності на невід’ємність та уову найкращої відповіді

Ei(si,m-i) ≤ ci . Якщо всі умови виконані, то РН в змішаних стратегіях знайдено, якщо ні, то переходимо до іншої підмножини S0i .

          Одним з відомих алгоритмів, що працює за цією схемою, є алгоритм Лемке - Хаусона, що представлений нижче. Але, якщо досліджується біматрична гра, у кожного з гравців якої маємо по дві стратегії, то пошук РН значно спрощується і навіть має зручну графічну ілюстрацію.

? Приклад 3.4. Знайти РН в змішаних стратегіях гри «сімейна суперечка», матриця якої представлена вище (прикл. 3.2).

          Ввівши змішані стратегії гравців SA(p1,p2),  SB(p1,q2,), за матрицею гри та співвідношеннями p2=1- p1 =1-р, q2 =1- q1=1-q складемо функції їх середніх виграшів