Конспект лекцій з дисципліни «Дослідження операцій»



Сторінка9/12
Дата конвертації11.05.2017
Розмір2.27 Mb.
ТипКонспект
1   ...   4   5   6   7   8   9   10   11   12

ЛЕКЦІЯ 8 «Позиційні ігри та ігри декількох осіб»


Анотація

Поняття про позиційні ігри. Кооперативні ігри та методи їх дослідження.Некооперативна гра двох осіб. Кооперативна гра двох осіб. Переговорна множина. Схема алгоритму переговорної множини.
8.1 Поняття про позиійні ігри

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

Розглянемо наступний приклад. Дві корпорації мають бажання встановити між собою ділові зв’язки і вирішити питання про побудову на території другої корпорації виробництва. Гра складається з трьох ходів. Перша корпорація обирає число з множини {1, 2}. Після цього друга корпорація обирає з множини двох можливих {1, 2}, знаючи, який вибір здійснила перша корпорація на першому ході. Третій хід робить перша корпорація: знаючи, який хід зробила друга корпорація, та пам’ятаючи про свій вибір на першому кроці, обирає число з множини {1, 2}. На цьому гра завершується і розподіляються виграші: перший гравець виплачує другому певну суму, визначену функцією М(x,y, z) яка визначена наступним чином в залежності від вибору гравцями 1-го – 3-го ходів x,yтаz відповідно:

М(1, 1, 1) = -2; М(1, 1, 2) = -1; М(1, 2, 1) = 3; М(1, 2, 2) = -4;

М(2, 1, 1) = 5; М(2, 1, 2) = 2; М(2, 2, 1) = 2; М(2, 2, 2) = 6.

Змістова інтерпретація цієї гри є наступною:



Хід 1. 1-а корпорація здійснює вибір з двох альтернатив: х =1 – запропонувати 2-й побудувати на її теорії складальне виробництво комп’ютерів, х = 2 – побудувати виробництво мікропроцесорів.

Хід 2. 2-а корпорація, знаючи, яку альтернативу обрала 1-а на першому ході, здійснює вибір з двох альтернатив: y = 1– будувати складальне виробництво та запропонувати це 1-й корпорації; y = 2 – будувати виробництво мікропроцесорів та запропонувати це 1-й.

Хід 3. 1-а корпорація, знаючи вибір 2-ї на другому ході та пам’ятаючи свій вибір на першому ході, здійснює вибір з двох альтернатив: z = 1– погодитися з пропозицією 2-ї,z = 2 – не погодитися з пропозицією 2-ї.

Після того, як зроблені ходи, партія зіграна, і 1-а корпорація отримує суму М(x,y, z).

Для нормалізації цієї гри необхідно відтворити стратегіях 1-го та 2-го гравця.

Стратегії 2-го гравця:



В1– обрати y = 1 не зважаючи на вибір 1-го гравця на першому ході;

В2– обрати y = 2не зважаючи на вибір 1-го гравця на першому ході;

В3– погодитися з вибором 1-го гравця на першому ході, тобто обрати y = 1, якщо х =1, і y = 2, якщох = 2;

В4– не погодитися з вибором 1-го гравця на першому ході, тобто обрати y = 2, якщо х =1, і y = 1, якщох = 2.

Таким чином 2-й гравець має 4 стратегії.

Стратегії першого гравця будуються аналогічно з врахуванням раніше зроблених виборів; вибір на першому кроці дає дві можливості, після вибору другого гравця з’являється чотири варіанти, і реалізація на третьому ході – 8 стратегій дії для 1-го гравця Таким чином, стратегію першого гравця зображатимемо за допомогою трійки (і, і1, і2) – де і – вибір 1-го гравця на 1-му ході; і1–вибір 1-го гравця на 3-му ході за умови вибору на 2-му ході 2-м гравцемy = 1; і2–вибір 1-го гравця на 3-му ході за умови вибору на 2-му ході 2-м гравцемy = 2.

Враховуючи відтворені стратегії, будуємо матрицю цієї гри:






В1

В2

В3

В4

А1(1, 1, 1)

М(1, 1, 1) =-2

М(1, 2, 1) =3

М(1, 1, 1) =-2

М(1, 2, 1) =3

А2(1, 1, 2)

М(1, 1, 1) =-2

М(1, 2, 2) =-4

М(1, 1, 1) =-2

М(1, 2, 2) =-4

А3(1, 2, 1)

М(1, 1, 2) =-1

М(1, 2, 1) =3

М(1, 1, 2) =-1

М(1, 2, 1) =3

А4(1, 2, 2)

М(1, 1, 2) =-1

М(1, 2, 2) =-4

М(1, 1, 2) =-1

М(1, 2, 2) =-4

А5(2, 1, 1)

М(2, 1, 1) =5

М(2, 2, 1) =2

М(2, 2, 1) =2

М(2, 1, 1) =5

А6(2, 1, 2)

М(2, 1, 1) =5

М(2, 2, 2) =6

М(2, 2, 2) =6

М(2, 1, 1) =5

А7(2, 2, 1)

М(2, 1, 2) =2

М(2, 2, 1) =2

М(2, 2, 1) =2

М(2, 1, 2) =2

А8(2, 2, 2)

М(2, 1, 2) =2

М(2, 2, 2) =6

М(2, 2, 1) =6

М(2, 1, 2) =2

Розв’язком гри є дві сідлові точки, ціна гри – 5 .

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

Для відображення необхідних даних про зроблені вибори при певних ходах гравців за умов їх різної інформованості на різних ходах на дереві позиційної гри пунктиром позначатимемо інформаційні множини вузлів.

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

2

2



1

2

1



1

1

1



1

1

2



2

-2

-1



3

-4

5



2

2

6



1

1

1



1

2

2



2

2

Рисунок8.1 – Інформаційні множини вузлів при знанні всіх ходів


Приклад 2. Порівняно з попереднім прикладом третій хід робить 1-й гравець, але вже не пам’ятаючи про те, який хід він зробив першим та не знаючи, який другий хід зробив другий гравець (1-го гравця можна уявити, як 2 особи, що знаходяться в окремих кімнатах та які не мають змоги обмінюватися інформацією). Відповідне дерево гри з інформаційними множинами наведене на рис.8.2.

1

2



2

1

2



1

1

1



1

1

1



2

2

-2



-1

3

-4



5

2

2



6

1

1



1

1

2



2

2

2


Рисунок8.2 – Інформаційні множини при частковому знанні


Проведемо гру до нормальної форми. У 2-го гравця є 4 таких же стратегії, як і в попередньому випадку. У 1-го гравця можливості зменшуються за рахунок браку інформації: оскільки він на 3-му ході не знає попередніх виборів, то його стратегія складається з пари чисел (x, z), тобто обрати 1 або 2 на 1-му ході та 1 або 2 на 3-му ході. Відповідна матриця гри буде мати наступний вигляд:





В1

В2

В3

В4

А1(1, 1)

М(1, 1, 1) =-2

М(1, 2, 1) =3

М(1, 1, 1) =-2

М(1, 2, 1) =3

А2(1, 2)

М(1, 1, 2) =-1

М(1, 2, 2) =-4

М(1, 1, 2) =-1

М(1, 2, 2) =-4

А3(2, 1)

М(2, 1, 1) =5

М(2, 2, 1) =2

М(2, 2, 1) =2

М(2, 1, 1) =5

А4(2, 2)

М(2, 1, 2) =2

М(2, 2, 2) =6

М(2, 2, 2) =6

М(2, 1, 2) =2

Отримана гра не має сідловок точки. Розв’язуючи гру в мішаних стратегіях, отримаємо мішані стратегії 1-го гравця – (0, 0, 4/7, 3/7), 2-го гравця – (4/7, 3/7, 0, 0), та ціна гри становитиме v = 26/7. Таким чином, в загальному випадку втрата інформації зменшує ціну гри.


8.2 Кооперативні ігри та методи їх дослідження

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

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

Ігри двох осіб посідають центральне місце у всій теорії ігор. Серед таких ігор виділяються біматричні ігри. Причини цього наступні. Біматричні ігри адекватніше відображають реальні конфлікти двох осіб порівняно з матричними, що використовуються для описання конфліктів з повною суперечністю і несумісністю інтересів, з відсутністю можливості компромісів; в таких конфліктах зростання прибутку одного гравця завжди означає збільшення втрат іншого. В житті такі конфлікти зустрічаються порівняно не частою Можна було б піддатися спокусі розглядати війну як крайній приклад зіткнення інтересів, але, взагалі кажучи, війна не є строгим суперництвом, оскільки обидві сторони вважають нічию кращим результатом, аніж взаємне знищення. Хоча локальне зіткнення або повітряний бій, очевидно, доцільно розглядати як гру зі строгим суперництвом. Але взагалі для описання військових конфліктів оперативно-тактичного плану, для яких приманна наявність не менш ніж двох ієрархічно пов’язаних ланок «напад – оборона», звичайно як адекватні використовуються біматричні ігри.

Біматричні ігри – це скінченні ігри двох осіб з довільною сумою, тобто такі, для яких не обов’язково виконується умова aij = -bij (тобто виграш одного з гравців – це програш іншого. Ці ігри описуються або за допомогою двох матриць А та В – виграшів кожного гравця, або ж за допомогою складної матриці, елементами якої є пари (aij, bij).
(8.1)
Біматрична гра – це найпростіша ігрова модель, що припускає можливість співробітництва.

Гра з нестрогим суперництвом, є грою, в якій не має однозначного суперника, тому що існує принаймні одна пара ситуацій х та х*, така, що один гравець віддає перевагу ситуації х*перед ситуацією х. Для таких ігор неможливо обрати функції корисності гравців так, щоб сума їх дорівнювала нулю; тому терміни «ігри з нестрогим суперництвом» та «ігри з ненульовою сумою» є еквівалентними. Більшість економічних, політичних і військових конфліктів інтересів можна представити у формі ігор лише в тому випадку, якщо визнати властиве їх нестроге суперництво.

В іграх зі строгим суперництвом гравці не можуть досягати обопільної вигоди посередництвом якого-небудь співробітництва; в іграх з нестрогим суперництвом, навпаки, такий обопільний виграш завжди можливий.

Існують дві різновидності бінарних ігор – безкоаліційні, що забороняють будь-яку співробітництво, та кооперативні, що дозволяють співробітництво.

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

Значення середніх виграшів гравців А та В в біматричній грі рівні відповідно:


та . (8.2)
Ситуація рівноваги для бінарної гри – це така пара (x, y)для якої виконується співвідношення
(8.3)
та природні обмеження:
(8.4)
Такі ситуації рівноваги в бінарній грі існують завжди – відповідна теорема про існування ситуації рівноваги в мішаних стратегіях для скінчених неантагоністичних ігор двох осіб доведена Нешем (NashJ.F.).

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



(8.5)
Розглянемо тепер основні ідеї ігор двох осіб з ненульовою сумою.
8.3 Некооперативна гра двох осіб

Нехай задана гра двох осіб з матрицею (8.1).

В теорії розглядаються в основному дві стратегії поведінки гравців – це максимінна стратегія і так звана стратегія загрози.

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

Якщо один з гравців застосовує свою оптимальну стратегію х* = (х1*, …, хm*), то інший не може покращити своє становище, тобто для оптимальної стратегії справедливі співвідношення


.
Перетворимо цю задачу здійснивши підстановку , і отримаємо:
.
Здійснивши підстановку та враховуючи, що гравець А прагне максимізувати свій середній виграш, отримаємо задачу лінійного програмування, розв’язання якої дозволить визначити оптимальну стратегію гравця А:
, (8.6)
Друга можлива стратегія – це стратегія загрози, за якої гравець ставить за мету не виграти самому, а дати можливість виграти другому гравцеві якнайменше (при цьому в бінарній грі він і сам може виграти найменше!).

Станемо знову на позицію першого гравця. Хай він знову застосовує мішану мінімаксну стратегію (прагне мінімізувати виграш 2-го гравця) х* = (х1*, …, хm*). Таким чином, застосовуючи її, він рахує не свій виграш, а виграш другого гравця. Якщо другий гравець робить хід jто його середній виграш становитиме . Перший гравець діє за принципом , тобто він мінімізує максимальний виграш другого гравця. Якщо позначити виграш другого гравця через w, то ми маємо:


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

, (8.7)
Розглянемо докладніше випадок n = m = 2. Тоді матриця виплат гри має вигляд:

B1 B2

(8.8)

y1 y2

Відобразимо геометричну максимінну стратегію і стратегію загрози першого гравця. Почнемо з максимінної стратегії. Нехай перший гравець обирає стратегію А1 з ймовірністю х1, х2 = 1-х1. За умови вибору гравцем В стратегії В1 середній виграш першого гравця становитиме a11x1 + a21(1 - x1).

За умови вибору гравцем В стратегії В2 середній виграш першого гравця становитиме a12x1 + a21(1 - x1) = a12x1 + a22(1 - x1) = v, отримаємо оптимальне значення середнього виграшу гравцяА у випадку застосування ним своєї максимінної стратегії. Аналогічні рівняння можна виписати також і для випадку стратегії загрози.

Рисунок 8.3 – Геометрична ілюстрація максимінної стратегії та стратегії загрози


У випадку максимінної стратегії гравець А гарантує собі виграш, не менший за v (рис. 8.3а), але при цьому згоджується з тим, що припускає і більший виграш гравця В порівняно з застосуванням стратегії загрози (значення w'на рис. 8.3б).

І навпаки, діючи з позиції стратегії загрози, гравець А гарантує для гравця В отримання мінімального виграшу, але разом з тим і зменшує свій середній виграш порівняно з максимінною стратегією (відомий підхід з точки зору «нехай мені буде гірше, але щоб у сусіда було найгірше»).


8.4 Кооперативна гра двох осіб. Переговорна множина

Розглянемо гру з наступною матрицею виплат:



y1-y


Нехай гравець А використовує мішану стратегію (х; 1–х), В – стратегію (y; 1-y). Тоді середні виграші гравців становитимуть:
,


Таким чином, ми побудували відображення x, yв v, w. 0≤x≤ 1, 0 ≤y ≤ 1. Відображаючи всі можливі варіанти x, yв простірv, w, отримаємо наступну фігуру (рис. 8.4), обмежену прямими, що проходять через пари точок (-1; -1), (1, 2) і (-1, -1), (2, 1), а також шматком параболи 5(v-w)2 = 2(v+w)-1. В ній є «провал», обмежений саме цією параболою.

Рисунок 8.4 – Відображення прикладу кооперативної гри за умови повного суперництва


Повернемося до загального випадку гри двох осіб з матрицею виплат (8.1) і припустимо, що гравці мають нагоду домовлятися про сумісні дії. В чому полягають ці сумісні дії?

Раніше стратегія Аі першого гравця обиралася з вірогідністю хі, стратегія Bjз вірогідністюyj, і стратегії обох гравців були незалежні, так що комбінація і, Вj)з’являлася з вірогідністю. хіyj. Зараз ходи обираються спільно і тому комбінація стратегій і, Вj)з’являється з деякою сумісною вірогідністю рij Сумісна гра зводиться таким чином, до вибору сумісної мішаної стратегії рij При цьому очевидно:



. (8.9)
При такій сумісній мішаній стратегії середні виграші першого і другого гравців рівні відповідно:
. (8.10)
Представимо собі множину (v, w).Яку область заповнять значення, що отримані з наведених формул? Виявляється,що ця область є опуклою оболонкою образів точок з координатами (aij, bij).

Так для наведеного вище прикладу гри область Rє опукла оболонка точок (-1, -1), (2, 1) і (1, 2) (див. рис. 8.5)


Рисунок 8.5 – відображення прикладу кооперативної гри за умови співробітництва


Порівнявши цю область з тією, яка зображена на рис. 8.4. бачимо, що застосування сумісних стратегій дозволило заповнити ту «западину», яка була при некооперативній грі.

Про що ж тепер можуть домовитися гравці? Нехай v*іw*-максимінні виграші першого і другого гравців відповідно (рис. 8.6). Нанесемо на нашу множину R точку з координатами точкою (v*,w*). Ця точка називається точкою statusquo. Очевидно, що жоден з гравців не погодиться одержувати в результаті сумісної гри менше ніж дає йому максимінна стратегія – навіщо йому така домовленість, якщо він може гарантувати собі без жодних домовленостей v*абоw*.


Рисунок 8.6 – Множина Парето-опримальних розв’язків гри


Тому з нашої множини розв’язків відразу зникає область , де v<v*та w<w*.

Розглянемо область, що тепер залишилася і визначається сумісною дією обмежень (vv*) (ww*). Задачу можна розглядати як двокритерійну з критеріями (v*,w*).Як нескладно визначити, множину Парето-оптимальних (недомінованих) розв’язків утворюють всі точки, що знаходяться на ламаній А – В – С.

Очевидно, що якщо точка (v,w) домінується точкою (v',w'), то в процесі торгівлі гравці безболісно відмовляться від точки (v,w) на користь точки (v',w'),оскільки при такому переході хоча б одному стає краще, а іншому – не гірше. Очевидно, що точки, які домінують точку (v,w), знаходяться правіше і вище на множині R. Тому множина Парето-оптимальних розв’язків називається також переговорною множиною для гравців А та В. Переговорна множина на рис. 8.5 – це відрізок прямої, що сполучає точки (1, 2) і (2, 1).

До чого гравці домовляться – наперед сказати не можна, оскільки на цій множині інтереси гравців прямо протилежні. Результат залежить від уміння вести переговори і лежить за межами математичного дослідження.

Отже, в певному значенні, вирішити біматричну кооперативну гру двох осіб означає побудувати переговорну множину.
8.5 Схема алгоритму побудови переговорної множини

Крок 1. Побудова образу всіх можливих мішаних стратегій x, y,



в просторі (v,w).

Крок 2. Побудова опуклої оболонки образу припустимих стратегій і просторі (v,w).

Крок 3. Знаходження максимінних виграшів кожного з гравців – точки statusquo.

Крок 4.Побудова множини Парето-оптимальних розв’язків як «північно-східної границі» оптимального образу в просторі (v,w), для якої виконуються умови (vv*) (ww*).

Слід відзначити, що конкретні реалізації алгоритмів для біматричної гри з числом стратегій, що більше 2, є достатньо складними.





Поділіться з Вашими друзьями:
1   ...   4   5   6   7   8   9   10   11   12


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал