Розв’язування біматричних ігор 2Х2

Під вирішенням розуміється пара оптимальних стратегій (чистих або змішаних) і середній виграш кожного з гравців.

Платіжні матриці гравців мають наступний вигляд:

 

Імовірності використання стратегій для А: p1 = p и p2 =1-p і для В: q1= q и q2=1-q.

Середні виграші обчислюються за формулами:

 

 

HA (p,q) = a11 pq + a12 p(1 – q) + a 21(1 – p)q + a22 (1 - p)(1- q)

HВ (p,q) = b11 pq + b12 p(1 – q) + b21(1 – p)q + b22(1 – p)(1 – q),

де 0 < = p < = 1 і 0 < = q < = 1.

 

Пара чисел (p *, q *), де 0 <= p * <= 1 і 0 <= q * <= 1 визначає рівноважну ситуацію, якщо для будь-яких p і q, підпорядкованих умовами 0 <= p <= 1 і 0 <= q <= 1, одночасно виконані наступні нерівності:

HA (p, q*) <= HA (p*, q*)

HB (p*, q) <= HB (p*, q*) (1) (1)

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

Нa (0, q *) <= HA (p *, q *), HB (p *, 0) <= HB (p *, q *),
HA(1, q *) <= HA (p *, q *), HB (p *, 1) <= HB (p *, q *).

тобто, щоб переконатися в обгрунтованості претензій пари (p *, q *) на те, щоб визначати рівноважну ситуацію, треба перевірити справедливість нерівності HA (p, q *) <= HA (p *, q *) для двох чистих стратегій гравця А (p = 0, p = 1), та нерівності HB (p *, q) <= HB (p *, q *) для двох чистих стратегій гравця B (q = 0, q = 1). Таким чином, треба, щоб різниці між середніми виграшами обох гравців у змішаній стратегії і середніми виграшами обох гравців у чистих стратегіях були невід'ємними, тобто

Нa (p, q)-HA (1, q),
HA (p, q)-HA (0, q),
HB (p, q)-HB (p, 1),
HB (p, q)-HB (p, 0) повинні бути > = 0

З урахуванням позначень:

 

С = a11 - a12 - a21 + a22, α = a22 - a12,

D =b11 - b12 - b21 + b22 β = b22 - b21

отримуємо наступні необхідні і достатні умови для того, щоб пара (p, q) визначала рівноважну ситуацію:

(р - 1) (Cq - α)> = 0
p (Cq - α)> = 0 при 0 <= p <= 1 (2)

(q - 1) (Dp - β)> = 0
q (Dp - β)> = 0 при 0 <= q <= 1

 

 

Розглянемо приклад. «Дилема в'язнів»
Гравцями є два в'язня, що знаходяться в попередньому ув'язненні за підозрою у скоєнні злочину. При відсутності прямих доказів можливість їх засудження більшою мірою залежить від того, заговорять вони або будуть мовчати. Якщо обидва будуть мовчати, то терміном покарання буде лише термін попереднього ув'язнення (втрати кожного гравця складуть –1). Якщо обидва зізнаються, то отримають термін, що враховує визнання як пом'якшувальну обставину (втрати кожного складуть –6). Якщо заговорить один з в'язнів, а інший буде мовчати, то заговорившого відпустять на волю (його втрати рівні 0), а зберігшого мовчання засудять на максимальний термін (його втрати складуть –9).
Цю гру можна представити у вигляді біматрічной гри, в якій у кожного з гравців по дві стратегії - мовчати (М) і говорити (Г).
Виграші гравців:

А B

	(М)	(Г)
(М)	-1
(Г)	-9	-6

	(М)	(Г)
(М)	-1	-9
(Г)		-6

 

Відповідні матриці:

 

Найдемо С, D, α, β:

С = a11 - a12 - a21 + a22, α = a22 - a12,

С = -1 - (-9) - 0 + (-6) = 2 α = - 6 - (-9) = 3

 

D =b11 - b12 - b21 + b22 β = b22 - b21

D = - 1- 0 - (-9) + (-6) = 2 β = - 6 - (- 9) = 3.

 

Підставимо С, D, α, β в нерівності (2):

(р - 1) (Cq - α)> = 0 p (Cq - α)> = 0

(p – 1) (2q – 3)>=0 і p(2q – 3)>= 0 – ліва пара нерівностей

 

(q - 1) (Dp - β)> = 0 q (Dp - β)> = 0
(q – 1) (2p - 3)>= 0 і q(2p - 3) >= 0 – права пара нерівностей

 

Для лівої пари нерівностей розглянемо три можливі випадки:

1) p = 0, 2) p = 1, 3) 0 <= p <= 1

Отримуємо:

1. p=0: (р - 1) (Cq - α)=(0-1)(2q - 3)= - 2q + 3 >= 0, звідки q <= 3/2,

p(Cq - α)=0*(2q – 3)= 0

2. p=1: (р - 1) (Cq - α)=0*(2q - 3) = 0,

p(Cq - α)=1* (2q - 3)= 2q - 3 >= 0, звідки q >= 3/2

3. 0<=p<=1: Розв ’ язується для p=0 і p=1 і беруться до уваги результати адекватні для обох варіантів. З п.1 для p = 0: q <= 3/2, з п.2 для p=1: q >= 3/2, тобто для двох варіантів одночасно виконується тільки умова рівності, звідки звідки q = 3/2

 

Для правої пари нерівностей є також три випадки:

1) q = 0, 2) q = 1, 3) 0 <= q <= 1

Відповідно отримуємо:

1. q = 0: (q - 1) (Dp - β)=(0-1)(2p - 3)= - 2p + 3 >= 0, звідки p <= 3/2;

q (Dp - β)>= 0*(2q – 3)= 0

2. q = 1: (q - 1) (Dp - β)= 0*(2p – 3)= 0

q (Dp - β)>= 1*(2p – 3)= 2p – 3 >= 0, звідки p >= 3/2

3. 0 <= q <= 1: Розв ’ язується для q =0 і q =1 і беруться до уваги результати адекватні для обох варіантів. З п.1 для q = 0: p <= 3/2, з п.2 для q =1: p >= 3/2, тобто для двох варіантів одночасно виконується тільки умова рівності, звідки p = 3/2

 

Нанесемо отримані результати на площину прямокутної системи координат (p, q) з виділеним на ній одиничним квадратом, відповідним нерівностям:0<=p<=1 і 0<=q<=1.

Зигзаги, що складаються з трьох прямих, відповідних 3-м розглянутим випадкам для кожної нерівності перетинаються в точці з координатами (0,0). Це і є точка рівноваги. Вона задовольняє всім вимогам.

Цій точці відповідають змішані стратегії P = (0,1) і Q = (0,1), тобто насправді точці відповідають другі чисті стратегії обох гравців - «говорити».

Стратегії визначені так. Для точки (0,0) перетину зигзагів p=0 і q=0, тобто p1=p=0 і p2 =1-p=1, q1= q=0 і q2=1-q=1, тому обом гравцям потрібно застосувати другі чисті стратегії.

Виграш кожного з них складе у результаті (–6).
Це дійсно рівноважна ситуація, тому що нікому не вигідно відхилятися від неї поодинці. Однак, скооперувавшись, тобто відхилившись від ситуації рівноваги удвох, вони б могли виграти більше. Наприклад, якщо б обидва мовчали, виграш кожного був би рівним (–1). Однак в умовах розглянутої задачі, кооперація неприпустима (гри некооперативна).

 

Також можна обчислити середній виграш для p=0 і q=0.

HA (p,q) = a11 pq + a12 p(1 – q) + a 21(1 – p)q + a22 (1 - p)(1- q)

HВ (p,q) = b11 pq + b12 p(1 – q) + b21(1 – p)q + b22(1 – p)(1 – q)

 

HA (0,0) = -1*0*0 - (-9)*0*1 - 0 + (-6) *1*1 =-6

HВ (0,0) = -1*0*0 - 0 - (-9)*0*1 + (-6) *1*1 =-6

 

Визначення виграшу застосуванням обчислених чистих стратегій і за формулами дає однаковий результат.

 

Розглянемо інший приклад. «Сімейна суперечка»
Чоловік і дружина домовляються про спільне проведення вечора. Чоловік хоче сходити на футбол, а дружина в театр, але краще їм разом. Якщо вони обидвоє йдуть в театр, дружина виграє 2, чоловік виграє 1, тому що все-таки вони разом. Якщо обидвоє йдуть на футбол, чоловік виграє 2, дружина, відповідно, 1. Якщо кожен йде туди, куди хотів - в обох нульовий виграш.
Платіжні матриці будуть наступними:

 

Провівши всі обчислення і дослідження аналогічно попереднього прикладу, отримаємо:
1). p = 0, q <= 1 / 3; 2). p = 1, q> = 1 / 3; 3). 0 <= p <= 1, q = 1 / 3 для лівої нерівності,
1). q = 0, p <= 2 / 3; 2). q = 1, p> = 2 / 3; 3). 0 <= q <= 1, p = 2 / 3 для правої нерівності.

Тоді геометричне рішення виглядає так як показано на малюнку:

Гра має три точки рівноваги. Дві чистих і одна змішана. Всі вони відповідають вимогам.
Чисті рівноваги:
1) p = 1, q = 1 зі середніми виграшами: HA (1,1) = 2 HB (1,1) = 1
2) p = 0, q = 0 зі середніми виграшами HA (0,0) = 1 HB (0,0) = 2
Змішана рівновага:

p = 2/3, q = 1/3 з середніми виграшами HA (2/3, 1/3) = 2/3 і HB (1/3, 2/3) = 2/3

Висновок

Ефект фокальної точки.

Як показує гра «Сімейна суперечка» рівноваг Неша може бути кілька. Кожна з них має властивість, що самооправдовуючуюся властивістю. Що ж могло б змусити гравців обрати деяку специфічну рівновагу? Будь-яка річ, яка змушує їх фокусувати увагу саме на цій рівновазі. Шеллінг у своїй книзі «Стратегія конфлікту» назвав це ефектом фокальної точки. Це будь-яка властивість, що виділяє конкретн рівновагу серед інших. Ними можуть бути традиції, статус кво тощо.

Також фокальна точка може визначатися властивостями функції корисності. Наприклад, «ділення доларів»: є 100 доларів. Кожен з гравців називає число від 0 до 100. Якщо сума <= 100, то кожен отримує, що просив, інакше - по нулях. Серед безлічі рівноваг, таких як (91,9) або (40,60) є фокальна - (50,50). Оскільки кожен гравець розуміє, що це ефективне і справедливе рішення (проте не завжди ефективне і справедливе рішення є рівноважним).

 

 

Оптимальність за Парето

Оптимальність за Парето - це інший варіант стійкості ситуації, більшою мірою, ніж рівноважний, відображає риси її вигідності.
У 1896р. В. Парето запропонував в економіці концепцію, що отримала назву принципу Парето-оптимальності. Цей принцип стосовно до задачі переговорів стверджує що, якщо для ситуації В існує така ситуація А, що виграш кожного з учасників переговорів при реалізації ситуації А не менше, ніж при реалізації ситуації В і, принаймні, один переговорщик отримає виграш строго більший, то вони вважатимуть за краще ситуацію А а не ситуацію В.
Стан А (множина параметрів) називається Парето-оптимальним, якщо не існує іншого стану В (множина інших параметрів) домінуючого над станом А щодо цільової функції. Стан А домінує над станом В, якщо хоча б за одним параметром А краще ніж В, а за рештою не гірше.

Основні визначення:

Множина Парето:
Розглянемо на площині (U, V) множину ω. Кожна її точка володіє однією з наступних властивостей: або всі точки, найближчі до неї, належать множині ω (така точка називається внутрішньою точкою множини ω), або як завгодно близько від неї розташовані як точки множини ω, так і точки, множини ω не належні (такі точки називаються граничними точками множини ω). Гранична точка може як належати множині ω, так і не належати. Тут розглянемо тільки такі множини, яким належать всі точки границі. Множина всіх граничних точок множини називається його границею.

 

Точки множини ω можна розбити на три клаcи:

I клас – точки, які, залишаючись в множині ω, можна зсунути так, щоб одночасно збільшились обидві координати (в цей клас потрапляють всі внутрішні
точки множини ω і частина його граничих точок) (на малюнку ці точки М1, М2 і М3);

ІІ клас – точки, переміщенням яких по множині ω можна збільшити тільки одну з координат при збереженні значення другої (вертикальний відрізок АВі го­ризонтальний відрізок РQ на границі множини ω);

III клас – точки, переміщення яких по множині ω можуть лише зменшити або одну із координат, або дві (дуга BQ границі множини ω).

Множина точок третього класу називається множиною Парето або границею Парето даної множини ω.

 

 

Переглянемо один із методів, в якому використовується множина Парето – метод ідеальної точки:

Нехай ми маємо деяку множину ε, кожна точка якого описується двома функціями U=Φ(x;y) і V=Ψ(x;y)

(U і V – середні виграші іграків А і В, а x і y – ймовірність вибору стратегії для отримання цього виграшу).

Тепер в даній множині ε спробуєм знайти таку точку, в якій обидві функції U і V приймають своє максимальне значення. В загальному випадку ця точка опинеться поза множиноюі ε. Тобто, не існує стратегій, при яких два гравці отримують максимальний для кожного виграш.

Точка, в якій функції U і V досягають своїх максимальних значень, называются точкою утопії..

Тому будується множина Парето і на ній знаходиться точка, найближча до точки утопії — ідеальна точка (див. рис.).