5. безкоаліційні ігри загальні зведення icon

5. безкоаліційні ігри загальні зведення




Скачати 144.43 Kb.
Назва5. безкоаліційні ігри загальні зведення
Дата20.09.2012
Розмір144.43 Kb.
ТипДокументи

5.БЕЗКОАЛІЦІЙНІ ІГРИ
Загальні зведення


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

Зокрема, антагоністичні ігри не торкають конфлікти з числом гравців більше двох. Більш того, навіть у конфліктах із двома гравцями інтереси сторін не завжди протилежні. У багатьох конфліктах одна із ситуацій може переважати для обох гравців.
Безкоаліційні ігри є іграми більш загальної природи. Безкоаліційність розуміється в тому змісті, що групам гравців ("коаліціям") не приписується ніяких інтересів, за винятком тих, що випливають з інтересів окремих гравців. Ціллю кожного гравця в такій грі є тільки одержання по можливості найбільшого індивідуального виграшу.
Визначення 1. Безкоаліційною грою називається гра N гравців (N>2), кожний із який має множину стратегій Х¡, із функцією виграшу Н¡(х),¡=1,N, де х Є Х - ситуація, що задається на множину Х декартового множення стратегій X¡.
Визначення 2. Безкоаліційна гра називається грою з постійною сумою, якщо існує таке постійне С, що ΣH¡(x)=C,

Клас антагоністичних ігор є класом ігор двох осіб із нульовою сумою.

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

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

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

Визначення 4. Ситуація х у грі називається
прийнятною для гравця ¡, якщо для будь-якої його стратегії х¡.

Н(х/х¡)≤Н(х), (5.1)

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

Визначення 5. Ситуація в грі, прийнятна для всіх
гравців, називається ситуацією рівноваги по Нэшу
(рівноважною ситуацією).

Іншими словами, ситуація х називається рівноважною,
якщо для будь-якого гравця ¡Є N виконується умова (5.1).

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

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

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

^ Приклад 1. Гра "Сімейна суперечка"

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

і

де стратегії гравця 1: А1 - вибираю футбол; А2 – йду на балет; гравця 2: В1- йду на футбол, В2 - на балет.

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

із ціною гри для обох гравців v=2/3.

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

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

Дійсно, якщо гравці не спілкуються до гри й обидва мають тверді характери, тобто перший гравець вибирає стратегію А1, а другий – В2, то в результаті вони обидва програють. Аналогічна ситуація утвориться й у тому випадку, коли кожний із гравців має м'який характер
і вирішує поступитися. Так сполучення стійкості зі справедливістю вступає в протиріччя зі сполученням стійкості і вигідності.

Кращим для гравців в аналізованій грі є договірний варіант (А11) або (А22), причому справедливим рішенням буде їхній вибір одного з цих варіантів шляхом кидання монети. Випадання герба буде означати, наприклад, що сімейство йде на матч по футболу, а решки - на балет. Зауважимо, що в антогоністичній грі на відміну від біматричної немає рації вести переговори до гри й домовлятися про спільний план дій. У аналізованій грі, ясно, що якщо гравці домовилися б грати обидва, скажемо першу чисту стратегію, причому гравець 1 за одержання більшого виграшу, ніж гравець 2, заплатив би йому 1/2, то рішення було б вигідним і справедливим для обох гравців. Проте в рамках безкоаліційнных ігор такого роду розподілення не передбачаються.


5.2. Ситуації , оптимальні по Парето


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

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

Визначення 6. Ситуація х у безкоаліційній грі
називається оптимальною по Парето, якщо не існує ситуації х Є Х для якої має місце векторна нерівність
Н¡(х)≤Н¡(х), для всіх ¡ Є І.

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

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

Питання про оптимальні по Парето ситуації вирішуються в принципі простіше, ніж аналогічні питання про ситуації рівноваги (оптимальних по Нешу).

Проілюструємо графічний метод визначення ситуацій оптимальних по Парето. На рис 5.1 зображена множина можливих стратегій х,х двох гравців. Кожній точці х Є Х відповідає точка на множині Н значень функцій виграшів H(x) і Н(х) (рис. 5.2).


На рис. 5.2 дуга АСВ відповідає множені ситуацій оптимальних по Парето, тому що ніякими спільними зусиллями гравців, не можна збільшити виграш одного з них, не зменшивши при цьому виграш іншого.

Визначення 7. Гра G' називається аффінно
еквівалентній грі G, якщо число гравців N'=N,
стратегії однієї гри Х¡ = Х¡, ¡Є N (звідси випливає, що ігри G і G' мають ту саму множину ситуацій), а функції виграшу

Н¡(х)=к¡Н¡(х)+с¡, ¡ЄN,
де k¡>0, ¡ЄN.

Розходження між двома аффінно еквівалентними
іграми по істоті складається в розходженні початкових
капіталів гравців і в співвідношеннях одиниць виміру
виграшів, обумовлених відповідно розмірами С¡ и k¡.

Для однорідно аффінно еквівалентних ігор k¡=k, iЄN.

Очевидно, що для антогоністичних ігор поняття
аффінної еквівалентності й однорідної аффінної
эквівалентності збігаються.

Теорема 1. Всяка безкоаліційна гра з
постійною сумою аффінно еквівалентна деякій грі з нульовою сумою.

Теорема 2. Аффінно еквівалентні ігри мають ті
самі оптимальні по Парето ситуації.

Роздивимося приклад для знаходження ситуації
оптимальної по Парето.

^ Приклад 2. Гра "Дилема ув’язненого"

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



Для обох гравців агресивні стратегії А2 і В2
домінують мирні стратегії А1 і В1. Таким чином, єдина рівновага в домінуючих стратегіях має вигляд (А22), тобто постулюється, що результатом некооперативного поводження є війна. У той же час вихід (A1,B1) (мир) дає більший виграш для обох гравців. Таким чином, некооперативне егоїстичне поводження вступає в протиріччя з колективнимиінтересами. Колективні інтереси диктують вибір мирних стратегій. У той же час, якщо гравці не обмінюються інформацією, війна є найбільш ймовірним виходом.

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

Як бачимо, на відміну від приклада 1 (гра "сімейна суперечка"), де кооперація гравців була їм вигідна, у цьому прикладі кооперація не вигідна для гравців.


5^ .3.СТАН РІВНОВАГИ ПО НЕШУ


Визначення 8. Стратегії х¡,i=1,N у грі N осіб із
ненульовою сумою називаються оптимальними по Нешу
(рішенням по Нешу або точкою рівноваги по Нешу), якщо для кожного ¡=1,N

Н¡(х)=mахН¡(х) (5.3)
тобто кожний гравець у ситуації х* отримує свій
найбільший виграш (у тій мірі, у якій це від його
самого залежить).

У розглянутій грі ''сімейна суперечка" ситуації
(A1,B1) і (A2, B2) є рішенням по Нешу, а в грі
"дилема ув’язненого'' такою є ситуація (А2, В2)
У випадку антогоністичної гри рівноважні
стратегії гравців збігаються з їхніми оптимальними
стратегіями. Для неантогоністичниих ігор поняття
оптимальної стратегії гравця нерідко взагалі не має
змісту: у таких іграх оптимальними є не
стратегії окремих гравців, а їхнє сполучення (ситуації) і
притім для всіх гравців відразу. Тому в загальних
безкоаліційних іграх оптимальними варто розуміти
сукупність дії всіх гравців (ситуацію в грі).
котра і є рішенням гри.
Як і в іграх двох осіб із нульовою сумою, гра N осіб із
ненульовою сумою може не мати рішення по Нешу у
чистих стратегіях. Приведене вище визначення 7
рішення по Нешу в чистих стратегіях легко узагальнюється на
випадок змішаних стратегій шляхом підстановки змішаних стратегій, що представляє собою ймовірностний розподіл на множині чистих стратегій.
У такий спосіб ми приходимо до ймовірного
розподілу Х на множині всіх ситуацій. Іншими словами, ситуація гри в змішаних стратегіях реалізує різноманітні ситуації в чистих стратегіях із деякими можливостями. Значення функції виграшу кожного з
гравців є випадковим розміром.У якості значення функції виграшу приймається математичне чекання цього випадкового розміру.
Дж. Нешем було доведене існування ситуації
рівноваги для будь-якої кінцевої безкоаліційної гри.
Теорема Неша. У кожній безкоаліційній грі
існує хоча б одна ситуація рівноваги в класі
змішаних стратегій.
Якщо, крім того, функції Н(х) опуклі нагору, то
рішення по Нешу досягається в класі чистих стратегій.
Зауважимо, що принципова важливість теореми
Неша обмежується існуванням ситуації
рівноваги. Безпосередньо застосовувати її для знаходження
таких ситуацій не вдається.
Дж. Нешем була доведена також така теорема.
Теорема 2. Кінцева безкоалційна гра має
симетричні ситуації рівноваги, у яких гравці.,
що рівноправно входять в гру відповідно до її умов, фактично знаходяться в однаковому положенні.
Її застосування дозволяє уникнути окремих помилок
при рішенні кінцевих безкоаліційних ігор.
Одним із простих класів безкоаліційних ігор хід
рішення яких піддається елементарному опису
є бімятричні ігри.,що представляють собою безкоаліційну гру двох гравців із ненульовою сумою.


5.4. Опис біматричних ігор
Нехай у биматричной грі гравець 1 має m чистык А, i = 1 ,m,а гравець 2 має n чистих стратегій В= 1 ,n і в кожній ситуації (А, В) гравець 1 отримує виграш а, а гравець 2 - виграш . Значення обох функцій виграшу гравців природно уявити у вигляді пари матриць


Тому такі ігри і називаються біматричними. Використовують також запис платіжних матриць А и В у такому вигляді:



……….



…………

……….

……….



……….




де "північно-західне" число в кожній клітині означає виграш першого гравця, а "південно-східне" - виграш другого гравця
Змішані стратегії Х и Y, природно, розуміються як вектори, причому,

хi=1 і yj=1.

Виграш гравців 1 і 2 при застосуванні змішаних стратегій рівні:


де Т - означає транспонування, тобто вектор- рядок записується як вектор- стовпчик;

- змішані стратегії гравців 1 і 2 відповідно.
Визначення ситуації рівноваги для випадку біматричної гри набуває слідуюче формулювання. Ситуація (Х,Y) у біматричній грі з матрицями виграшів А і В є рівноважною, якщо

(5.4)

(5.5)

Очевидно, що пpu B=-A біматричная гра перетворюється в матричну.

ЯК приклад роздивимося біматричну гру «Торг»
Приклад. Гра “Торг”
Гравець 1 продає неподільний товар гравцю 2. Гравець 1
повинен вирішити, яку призначити ціну: високу або низьку. Для покупця в принципі прийнятні обидві ціни. Покупець не може сперечатися про ціну, він може або зробити покупку, або відмовитися від неї.

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

Гравець 2
B1 - покупка В2 - відмова












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


5.5. Рішення біматричних ігор
Розглянемо спочатку біматричну гру 2х2 з матрицями виграшів


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

Опишемо порізно множину прийнятних ситуацій для кожного з гравців і зобразимо ці множини на одиничному квадраті р, q, де рє [0,1] і qє[0,l].
Почнемо з опису ситуацій, прийнятних у грі для гравця 1.
Прийнятність ситуації (X, Y) для гравця 1 у біматричній грі означає, що
(5.6)
(5.7)
де А1 і А2 - вектори рядка, що відповідають першому і другому рядку матриці А, відповідно.
Підкреслимо, що ці умови прийнятності ніяк не пов'язані з матрицею В виграшів гравця 2. Тому вони будуть збігатися з аналогічними умовами матричної гри з платіжною матрицею А.
Приємливість ситуації (X, Y) для гравця 2 означає, що
(5.8)
, (5.9)
де В1 і В2 - вектори-стовпчики, що відповідають першому і другому стовпчику матриці В, відповідно.
У загальному випадку, Х=Iр, 1 - рI. Роздивимося три випадки:

а) р =1,(X=I1,0l). Тоді вираження (5.6) перетворюється в тотожну рівність, а умовою прийнятності даної ситуації для гравця 1 є нерівність (5.7). Для аналізованого випадку його можна записати як
; (5.10)
б) р = 0 (X=l1, 0|). У цьому випадку вираз (5.7) перетворюється в тотожну рівність, а умовою прийнятності даної ситуації для гравця 2 є
нерівність (5.6). Для аналізованого випадку воно має вигляд:
(5.11)
в) 0< р <1 (Х=Iр, 1 - pI). У цьому випадку обидві нерівності (5.6) і (5.7) перетворюються в рівність, і умовою прийнятності стає:
(5.12)
Опишемо ситуації прийнятності (5.10), (5.11) і (5.12) у розгорнутому вигляді. Так як



то співвідношення (5.10), (5.11) і (5.12) можна відповідно записати як
(5. 14)
(5.15 )
(5.16)
Таким чином, прийнятні для гравця 1 ситуації (X, Y) можуть бути одного з трьох типів:

(1,q), де (5.17 )

(0,q), де (5.18)

(p,q), де 0<р<1. (5.19)
Нерівності (5.17) і (5.18) вірні у випадку, якщо а112212-21>0.Якщо а11+ а22 – а12 – а21< 0, то знак нерівності в співвідношеннях (5.17) і (5.18) необхідно поміняти на протилежний.
Якщо величина а11+ а22- а12 –а21 = 0, а а22- а12, то (5.19) не має місце, тому буде виконуватися або (5.17) і (5.18), і притім із знаком суворої нерівності.
Якщо ж а11+ а2212 – а21= 0 і а22 – а12= 0, то всі умови (5.17), (5.18) і (5.19) виконуються тотожно, і прийнятними для гравця 1 будуть узагалі всі ситуації.
Опис ситуацій прийнятності в розгорнутому вигляді для гравця 2 одержуємо аналогічно з нерівностей (5.8) і (5.9).
У загальному випадку Y=|q, 1-q|. Для трьох випадків одержуємо:
а) q=1(Y=I1,0|). У цьому випадку прийнятність ситуації (X,Y) рівноправна нерівності

(5.20 )

або в розгорнутому вигляді

Ip, 1-pl

(5.21 )

б) q=0 (Y=I0,1|). У цьому випадку прийнятність ситуації (X, Y) визначається нерівністю

(5.22 )
або в розгорнутому вигляді

(b11+b22-b12-b21)*p b21-b12. (5.23)
в) 0 ХВ1=ХВ2, (5.24)

у розгорнутому вигляді
(5.25)
Таким чином, прийнятні для гравця 2 ситуації (X, Y) можуть бути одного з трьох типів:
(p,1), де (5.26 )
(p,0), де (5.27)
(p,q ), де (5.28)

Знову підкреслимо, що нерівності (5.26) і (5.27) справедливі, якщо їхній знаменник більше нуля. Якщо <0, то знак нерівності у виразах (5.26) і (5.27) необхідно поміняти на протилежний.
Для визначення ситуацій, прийнятних одночасно як для першого, так і для другого гравців, зручно всі знайдені прийнятні ситуації уявити
на одиничному квадраті (рис. 5.3).


Рис.5.3.

Для випадків, коли і прийнятні ситуації гравців 1 і 2 складають зигзаги. Причому, ситуації рівноваги в цілком змішаних сгратегіях гравця 2 збігаються з
поводженням гравця 2 у матричній грі з матрицею виграшу А, а поводження гравця 1 - із поводженням гравця 1 у матричній грі з матрицею виграшів В.
Таким чином, описане рівноважне поводження гравців надається орієнтованим не стільки на максималізацію власне виграшу, скільки на
мінімізацію виграшу супротивника. Так, "антагонізм поводження" може виникнути і при відсутності "антогонізму інтересів".
У приведеному на рис. 5.3 рішенні гри три ситуації рівноваги, відповідають точкам R1, R2,R3.
Якби зигзаги прийнятних ситуацій були однакової орієнтації, як показано на рис. 5.4, то перетинання прийнятних ситуацій гравця 1 і гравця 2 складалося б з однієї точки R.


Рис 5.4

При рішенні біматричних ігор більшої розмірності необхідно вирішувати велику систему лінійних нерівностей, обумовлених виразами (5.6). (5.7) і (5.8), (5.9 ), а потім таким же кінцево-раціональним шляхом
знаходити точки перетинання прийнятних ситуацій гравця 1 і гравця 2. Причому, будь-яка кінцева безкоаліційна гра має кінцеве і непарне число ситуацій рівноваги (рішень гри). Пошук ситуацій рівноваги в цьому випадку
потрібно здійснювати з застосуванням ПЕВМ.

Схожі:

5. безкоаліційні ігри загальні зведення iconВ. Д. Жван, М. Д. Помазан, В. В. Жван методичні вказівки щодо виконання практичних занять, самостійної роботи та розрахунково-графічних робіт з дисципліни «Зведення будівель І споруд»
«Зведення будівель І споруд» (для студентів усіх форм навчання напряму підготовки 060101 (0921) «Будівництво»
5. безкоаліційні ігри загальні зведення icon1. Загальні зведення
Проходка широким вибоєм дозволяє залишити породу у виробленому просторі І тим самим звільнити від додаткового навантаження підземний...
5. безкоаліційні ігри загальні зведення iconЗ дисципліни «зведення І монтаж будівель І споруд»
Конспект лекцій з дисципліни «Зведення І монтаж будівель І споруд» (для студентів усіх форм навчання напряму підготовки 060101 (0601)...
5. безкоаліційні ігри загальні зведення iconЗ дисципліни «технологія зведення, ремонту І реконструкції спеціальних споруд»
«Технологія зведення, ремонту І реконструкції спеціальних споруд» (для студентів 5 курсу денної І заочної форми навчання напряму...
5. безкоаліційні ігри загальні зведення iconЗ дисципліни «технологія зведення, ремонту, реконструкції спеціальних споруд»
«Технологія зведення, ремонту, реконструкції спеціальних споруд» (для студентів заочної форми навчання та другої вищої освіти напряму...
5. безкоаліційні ігри загальні зведення iconЗ дисципліни «технологія зведення, ремонту І реконструкції спеціальних споруд»
«Технологія зведення, ремонту І реконструкції спеціальних споруд» (для студентів заочної форми навчання та слухачів другої вищої...
5. безкоаліційні ігри загальні зведення iconЗ дисципліни «технологія зведення будівель та споруд І технологія реконструкції»
Програма І робоча програма навчальної дисципліни «Технологія зведення будівель та споруд І технологія реконструкції» (для слухачів...
5. безкоаліційні ігри загальні зведення icon6 Структура комплексного процесу зведення монолітних залізобетонних конструкцій
Рис 1 – Схема комплексного процесу зведення монолітних залізобетонних конструкцій
5. безкоаліційні ігри загальні зведення iconРозділ І. Теоретична Механіка
Момент сили. Теорія пар сил. Момент пари сил. Система сил, що довільно розташовані в просторі. Основна лема. Зведення системи сил...
5. безкоаліційні ігри загальні зведення iconПрограма І робоча програма навчальної дисципліни технологія зведення будівель І споруд І технологія реконструкції
«Технологія зведення будівель І споруд І технологія реконструкції» (для студентів 5 курсу денної форми навчання освітньо кваліфікаційного...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи