Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето icon

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




Скачати 229.73 Kb.
НазваІнформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето
Дата20.09.2012
Розмір229.73 Kb.
ТипІнформація
<4>



3. ПОЗИЦІЙНІ ІГРИ

3.1. Загальні зведення

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

Приклад. Вибори з правом вето.

Нехай три гравці (ТЧ==3) вибирають одного з чотирьох (0=4) кандидатів у президенти. Правило вибору таке:

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

U1=||5,4,3,7|

U2=\\6,7,5,4\\;

U3=|3,8,5,4||.

У розгорнутій формі дана гра може бути представлена у виді наступного дерева гри (мал. З.1), де біля галузей поставлені номери кандидатів, що відводяться, а в кінцевих вершин - номера перемігших кандидатів. Якщо переміг, наприклад, кандидат під номером 4, то виграш першого гравця буде дорівнює 7, а для другого і третього гравців - 4.

Позиційні ігри повинні включати наступні елементи опису:

• послідовність особистих і випадкових ходів гравців;

• вибори, що можуть робити гравці при кожнім особистому ході;

© Кшвський шститут швестншйного менеджменту






Рис.3.1

розподіл

исходы випадкових ходів імовірностей цих исходов;

• інформацію, доступну гравцям при виконанні особистий чи випадковий ходи;

• правила закінчення гри і підрахунки виграшу

гравців.

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

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

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

'© КиТкськин шепнуть швестищйного менеджменту

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

© Ки'1'вський шстнтут швестищнного менеджменту




Т_2. Завдання'_позиційної гри у виді дерева

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

-7 +12-11 -9 8 +12-11 -9 8



мал.з.2

Основними властивостями дерева ігри є:

•дерево містить одну єдину початкову вершину ("корінь" дерева), у которую не входить жодна галузь;

•дерево має не менш однієї вершини, з якої не виходить жодна галузь. Ці вершини називаються кінцевими вершинами;

•з кореня дерева мається єдиний шлях до кожної з інших вершин дерева.

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

Вершини, що відповідають випадковим ходам, позначають номером 0. Галузі, що виходять з вершини, зображують вибори, що можуть бути зроблені гравцем лри даному ході. Імовірності виконання випадкового ходу

Кшвський 1нстит\ 'т швестищйного менеджменту

записують у відповідних галузей. Біля кінцевих вершин дерева вказуються исходы гри - значення виграшу гравців (а в антагоністичних іграх - виграш першого гравця).

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

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

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

У розглянутому прикладі (мал.3.2) випадковий іспит Н може мати наступні исходы:

Н=|(Г,3),(Г,2),(Р,3),(Р,2)!, з імовірностями

п Г1 1 1 Ц

\а''л''а ''7'м де " означає випадання "герба", Р -

"решки", а цифри 2, 3 відповідають випадковому вибору на четвертому ході.

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

КиУвський щститут швестишйного менеджменту



Інформація, доступна гравцям задається інформаційною розбивкою вершин на безлічі ^„

називані класами

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

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

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

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

Класи інформації (інформаційні безлічі) повинні задовольняти наступним умовам:

1. містити вершини тільки одного гравця;

2. кожна вершина може належати тільки одному класу інформації;

3. вершини класу інформації відповідають тільки одному тимчасовому ходу;

4. з усіх вершин, що складають клас інформації, може виходити тільки однакова кількість галузей.

Дерево, зображене на мал.3.2., відповідає ^едующей грі:

Перший гравець вибирає один із двох напрямків

КиТвський жститут жвестицшного .менеджменту

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

Другий гравець вибирає один із двох напрямків ("ліворуч" чи "праворуч"). Хід "ліворуч" оцінюється п'ятьма балами, а "праворуч" - двома. Четвертий хід є знову випадковим і складається у виборі з рівними імовірностями одного з напрямків: "ліворуч", "праворуч", що оцінюються трьома і двома балами відповідно. Оскільки імовірності вибору напрямку при випадковому

ході однакові (рівні —), те їх можна на графічному

зображенні дерева гри і не вказувати.

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

Простору Ф, і Ф^ усіх можливих стратегій гравців 1 і 2 у розглянутому прикладі наступні:

Ф.-КЗ), (4)[;

Ф^(3,П5),(3,Г,2),(3,Р,5),(3,Р,2),(4,Г,5),(4,Г,2), (4,Р,5),(4,Р,2);,

де перше число кожної стратегії в просторі Ф, відповідає вибору першого гравця, друге число -випаданню чи герба решки ("Г" - випав "герб"; "Р" -випала "решка"). Третя - вибору другого гравця чи п'ятірки двійки.

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

Опис позиційної гри у виді дерева дозволяє

89

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

3.3. Рішення позиційної гри з повною інформацією

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

Для того, щоб це продемонструвати, розглянемо описану вище гру «Вибори з правом вето». Оскільки з усіх вершин, що передують кінцевим, ходить гравець 3, те інші гравці, знаючи його функцію виграшу Цз, можуть легко передбачати його рішення. Це дозволяє привести гру, зображену на мал.3.1 до наступного:



Рис.3.3

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

91



Рис.3.4

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

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

^ський шститут щвестишйного .менеджменту

3.4. Нормалізація позиційної гри

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




© Кжвський шститут 1нвестищ' іншого менеджменту



Рис. 3.5

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

У даній грі в першого гравця (гравця А) мається дві чистих стратегії: Ф^/А;, Ау, де стратегія А, - завжди вибирати ліву галузь; стратегія А^ - завжди вибирати праву галузь. Другий гравець (гравець У) має більше стратегій:

Ф^/У,,„„В,/, де стратегія В, - завжди вибирати ліву галузь;

стратегія В;, - завжди вибирати праву галузь;

стратегія Вз - вибирати галузь, що вибрав гравець А;

стратегія В4 - вибирати галузь, протилежну тієї. яку вибрав гравець А.


а праворуч", №4' 2000 93

Матриця гри в цьому випадку має вид:

У

А,- У, У, У,

А, -2 -2

-2

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

Дійсно, тому що

і = тахтшд, -2,

р = тттахй,, = -2.

/ '

і, отже, а = ? .

Тому 5^ ,'1,0; чи 8д=Н(и||, а 8у=|{0,0,0,1 Ціна гри в=-2.

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



Рис. 3.6

Кишський шститут йвестишйного менеджмент)'

Кількість чистих стратегій другого гравця в порівнянні з першим випадком скоротиться до двох-

Фз=/В„В2/,

де В; - завжди вибирати ліву галузь;

У^ - завжди вибирати праву галузь. Процес нормалізації приводить до наступного платіжній матриці:

У,

А,. У, У,

А, -2

-2

У новій грі сс^р, тобто седловая крапка отсутствует. Рішення гри в змішаних стратегіях має вид:


^ 8.


Зменшення гравця на момент


11.

1ПГ інформації, прийняття


V =


11


5_ _6 1 М И


наявної в другого рішення, привело до





11

зменшенню його виграшу з 2 до -

Отже для нормалізації позиційної гри необхідно:

•перелічити всі можливі стратегії кожного з гравців (у таких іграх, як шахи, це поки нерозв'язна задача);

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

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

© КиТвський шсти-л-т швестишиного менеджменту

95

ТЕСТИ (У - Вірно, Н - Невірно)

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

2. Позиційні ігри не можуть включати випадкові ходи.

3. Дерево позиційної гри має не більш одного кореня і не менш однієї вершини.

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

5. Якщо всі класи інформації позиційної гри містять тільки по одній вершині, то така гра є грою з неповною інформацією.

6. Класи інформації повинні містити вершини тільки одного гравця.

7. Вершини класу інформації можуть відповідати різним тимчасовим ходам.

8. З усіх вершин, що складають клас інформації, може виходити тільки однакова кількість галузей.

9. Будь-яка позиційна гра може бути зведена до гри в нормальній формі.

10. Гри з повною інформацією мають седловую крапку і зважуються в чистих стратегіях.

11. Теорема Куна затверджує, що позиційна гра з повною інформацією розв'язна по домінуванню.

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

"вський шститут щвестицшного менеджменту

ЗАДАЧІ

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

Варіанти:

Кшвський шститут швестицшного менеджменту

^аша праворуч", №4'2000 97

4.



2. Намалювати дерево наступної позиційної гри «Вибір із правом вето», у якої N гравців вибирають

одного кандидата з безлічі З= {з,,^,...,^}, до N.

Правило голосування таке: починаючи з гравця 1, кожен гравець послідовно накладає вето на вибір кандидатури одного з не відведених кандидатів. Єдиний кандидат, що залишився, вважається обраним. Задані також функції виграшу и" і^, ..., і^ на безлічі З, тобто виграш кожного гравця в залежності від того, який кандидат переміг. Знайти рішення, використовуючи теорему Куна.

Варіанти:

1.М=2; С-{з,,Сз,Сз} і={2,-5,4};і^{-2,5,-4}

2. N =2; З= {з^з^з^,з^ ]

и-{2,5,-4,-3,1};і2={-2-3,4,3,-1} Зм^З-Г^-Ьссс}

^.1^ ^^ ^— ДО^ ,З^ ,1^,

і,={1,2,-3,4}; і2={3,2,1,-5}; з={-2,-3,-1,8}. 4.М=4; З== {с„с,_,з^,з,}

і,={1,2,-2,-ЗД}; і2={3,5,1,-7,6}; з={2,4,-5,-1,1};

^{2,3,4,1,6}.

^ 4. НЕСКІНЧЕННІ АНТАГОНІСТИЧНІ ІГРИ

4.1. Загальні зведення

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

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

Принцип "максимина" може бути реалізований тоді і тільки тоді, коли існують і рівні змішані экстремумы:

тах 1пГ Н(х,у) і ппп §ир Н(х,у).

хеХ;уеУ уеУ;хеХ

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

Нехай, наприклад, Х и У належать (ПРО, 1), а функція виграшу Н(х,у) = х + у. Очевидно, що якби 1 і Про входили в число можливих стратегій гравців, то ситуація (1, 0) відповідала б седловой крапці. Оскільки цю

© КиТвський шститут швестишйного менеджменту

99

ситуацію реалізувати не можна, те в описуваній грі можна говорити про оптимальність стратегії гравців «з точністю до довільного е > 0 ».

Визначення 1. Ситуація (^»-ДО) у нескінченної

антагоністичній грі називається ситуацією е рівноваги, якщо для будь-яких стратегій х, у відповідно гравців 1 і 2 має місце нерівність:

Я(х,^)-е ^ Я(^^)^Я(х,,>')+е.

Крапка (х^,^), для якої виконується це

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

ситуацію е - рівноваги в нескінченній антагоністичній грі, називаються 8 - оптимальними стратегіями.

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

Теорема 1. Якщо при всякому е > 0, функція Н(х, у) має е - седловые крапки, то

5ир шГ Н(х, у) = тГ зир Н(х, у).

х В Ух

Экстремумы 8иртГЯ(х,^) і ш15ирЯ(х,^)

х В Ух

називаються відповідно нижнім і верхнім значеннями нескінченної антагоністичної гри.

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

Змішаними стратегіями в нескінченної ^тагонистической грі є вероятностные

Кшвський 1НСТИТУТ жвестищйного менеджменту

——"^у

розподілу 8(х) і8(у) на безлічах їхніх чистих стратегій Х и У. Пари таких вероятностных розподілів є статистично незалежними.

Якщо ^(.х) і ^ 8у(у) - змішані стратегії гравців 1

і 2, то виграші Н(Х, у), Н(х,У) і Н(Х,У) є по визначенню математичними чеканнями:

Н{Х,у) = ]//(л-,у)йЙ,(х), Н(х,У) = ^Н(х,у)^,(у),

Х у

Н(Х,У)= ]я(^У)^(х)= ]//(А^)й^,(у)= ^Н(х,у)^\(х^8,(у}.

Х У ХГ

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

© КиУвський шсттгп-т швестишйного менеджменту


^ 4^2. Рішення опуклих ігор на одиничному ^вадиате

Визначення 3. Клас антагоністичних ігор, у яких х,в е [0,1] називаються іграми на одиничному квадраті.

В іграх на одиничному квадраті будь-яка ситуація (х,у) розуміється як крапка одиничного квадрата.

Визначення 4. Нескінченна антагоністична гра на одиничному квадраті називається строго опуклої, якщо її функція виграшу ^ Н(х,у) строго опукла по в при будь-якому х.

Рішення опуклих ігор на одиничному квадраті базується на наступних основних теоремах [2].

Теорема 2. У строго опуклій грі гравець 2 має єдину оптимальну стратегію в*, що є чистої і є рішенням рівняння

v = тахН(х,у*), де v - ціна гри.

Х

Теорема 3. Нехай в опуклій нескінченній антагоністичній грі на одиничному квадраті з функцією Щх,у) дифференцируемой по в при будь-якому х, у* -оптимальна чиста стратегія гравця 2, а v - ціна гри. Тоді:

1) якщо в* == 1, то серед оптимальних стратегій гравця 1 мається чиста стратегія х , для якої Н'у(х' ,у) < 0;

2) якщо в* = 0, то серед оптимальних стратегій гравця 1 мається чиста стратегія х", для якої Н' /х" ,у) >:

0;

3) якщо 0<у*<1, то серед оптимальних стратегій гравця 1 знайдеться така, що є сумішшю стратегій х и х". Для цих стратегій Н'/х',у*) ^ ПРО, Н' у(х" ,у*) > 0. При цьому стратегії х и х" уживаються з імовірностями Р и 1-р, де/? знаходиться з рівняння

рН\(х,у^+{1-р)Н',(х"^)=0.

Кщвський шститут швестищиного менеджменту

4.3. Приклади рішення нескінченних антаг вони стичес кик ігор

Гра «Боротьба за ринки»

Нехай одна з фірм (гравець I) намагається витиснути іншу фірму (гравець 2), що має два ринки збуту, з одного з цих ринків. Загальна сума засобів, виділюваних гравцем 1 на цю мету, дорівнює одиниці {X е [0,1]). Стратегії гравця 1 складаються в розподілі цих засобів між двома ринками. Якщо на перший ринок направляється сума х, то на другий " (1-х). Нехай гравець 2 для утримання ринків також має у своєму розпорядженні одиничну суму засобів, і його стратегія буде складатися у виділенні суми в на перший ринок і (1 -у) - на другий.

Вважається, що гравець 1, домігшись "" ^/.. , засобів на одному з ринків, витісняє їс-це ринку й одержує выигр засобів, що бепе-7

Рішення.

Графік залежності Щх^у) від у для деякого х==Ху представлений на мал. 4.1.

КиУвський {нститут швестишпного менеджменту



Рис.4.1

Очевидно, що при будь-яких Хц функція Н (Хд, у) є опуклою функцією від у. Маємо

тахН(х,у) = тах^ тах/м, (х -у),тах/^(у -х)[= тах{^(1 - у),^у}-

х х [ хгу х-^у ^ м

Тому ціна гри

v = т'т тах Н(х, у) = тт тах ^ (1 - у), Н^ (у)}.

ух ух

Графік функції тах^(1-у),^(у)} виділений на

мал.4.2. жирної ламаний. н



Рис.4.2

Кювський тстрплтшвестищйногоменеджменп

104 "Наша праворуч", №4'20ор

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

^1 (1- V*) = ^гУ *. т\е- лри ^

Г (4.1)

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

Значення ціни гри

[ ( ъ \ ^ъ 1 ^

V=п^п1тах^^)=пн?^^.у,у+)=^^№^^ 1-7—— [———[=—. (4.2) 1 х х [\ ^+у^+^ ^

Далі треба найтг"? оптимальну стратегію гравця 1. Випадки х>у* і х<у* будемо розглядати порізно.

Теорема 3 затверджує, що якщо Н(х,у) - опукла і 0^у*<1, то серед оптимальних стратегій гравця 1 знайдеться така, що є сумішшю двох активних стратегій х и х": Для цих стратегій

дЩх\у*) дН(х'\у^) ————>0 і —-———^0. (4.3)

ду ду


' ? * ^'/ у

р^^^-р)8"^^.

ду ду
При цьому стратегії х' і х" уживаються з імовірностями р і (1-р), де;;» знаходиться з рівняння

(4.4)

Для випадку х>у* рівняння (4.2) приймає вид

/ ^ 1 Ъ- ]м

7 1 '•• 2'Ч

Ч- у — ____'" ' Л.) Л —

1 7 7 » >

^+^) ^ +

відкіля х'=-1.



Для випадку х<у* рівняння (4.2) має вже інший вид:

- вус) КчК}

^1 +^2

відкіля х" =0.

Таким чином, активними стратегіями гравця 1 виявляються: х'=0; і х"^\. Тому гравець 1 повинний застосовувати змішану стратегію, що є сумішшю цих двох активних стратегій. Для перебування імовірності р, використовуємо рівняння (4.4).

Частки похідні


У=У

У=У


ду
ду дЩ\,у)


ду
-^-У) ду

Тоді рівняння (4.4) для даної гри здобуває

вид


(4.5)

р^ + (1 - р)(-^) = 0, відкіля ^_ ^

К-1 + Кч

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


^ Гра з вибором моменту часу (гра типу дуелі)

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

\^(х,у),прих<у;}

ф\прих=у; ^ (4.6) ф(х,^),прих>у,]

де кожна з функцій \^/ і (р

а) безупинна по обох перемінним;

б) монотонно зростає по х при будь-яких значеннях у;

в) монотонно убуває по в при будь-якім значенні х-,

г) задовольняє умові (р(х,х)<^(х)^(х,х).

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

Ми обмежимося розглядом одного приклада даної гри, теорія якого, хоча і розроблена, але досить складна [2].

Нехай гравці 1 і 2 вибирають відповідно числа х и у з інтервалу [0,1]. Ці числа будемо розуміти як моменти часу виконання ними необхідних дій. Нехай I - час появи деякого об'єкта, що дістається гравцю, що перший після I зробив зебуемое дію. Гравець, що володіє .об'єктом,

© КиУвський 1ЯСТИПТ швестишйного менеджменту

"Наша праворуч", №4' 2000 107

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

Передбачається, що час появи об'єкта є випадковою величиною, розподіленої на інтервалі [0,1 ] по рівномірному законі. Цю гру називають також боротьбою за зустріч випадково з'являється об'єкта.

Запишемо математичне вираження функції виграшу. Розглянемо ситуацію (х,у), у якій х<у. У цьому випадку гравець 1 виграє одиницю, якщо

^х; . (4.7) програє одиницю, якщо

х<Ку; (4.8) і не одержує нічого, якщо

у<1. (4.9)

Імовірність подій (4.7), (4.8) і (4.9) рівні відповідно х, (у-х) і (1-у). Таким чином, при х<у маємо

Щх,у)=\-х+(-\)(у-х)=2х~у. (4.10)

Аналогічним способом знаходимо, що при х>у

Щх,у)=\-(х-у)+{-\)у=х-2у. (4.11)

Природно, що при х=у, Н(х,у)=0.

Схематичний опис Н(х,у) приведене на мал.4.3.

Рішення. Помітимо, що гра є симетричної.

Дійсно, при х<у

Щх,у)=2х-у=-Щу,х)=-{у-2х).

Аналогічно, при х>у

Щх,у}=у-2х=-Н(у,х)={2у-ху

Нарешті, при х^у

Щх,у)=0=-Щу,х).

КиГвський шститут швестишйного менеджменту

108 Наша праворуч", №4 '2000



Рис.4.3

Для антагоністичних симетричних ігор існує теорема, що затверджує для цих ігор ціна гри в = 0, а оптимальні стратегії гравців 1 і 2 збігаються.

Тому для рішення даної задачі досить знайти оптимальну стратегію гравця 1.

Нехай оптимальна стратегія гравців має щільність розподілу/:

8Лх)=/{х);

^(>0=/00.

Якщо гравець 2 застосовує цю стратегію, то

I •

Я(х,/)=|я(х,у) Лу^у.

З урахуванням формул (4.10) і (4.11.). перепишемо останній інтеграл

х 1

Я(х,/) = |(х - 2у^/{у)з1у + |(2х - у) /(у^у . (4.12)

ПРО х

Тому що Я(^,/)=у=0 і постійна, те всі

похідні по х функції Н(х,/) також повинні звертатися в нуль.

109

Диференціюючи тотожність (4.12) по х, маємо

.1 1

^^ = (^ - 2х)/(х) + [ /Ъ^У - (2х - х)/(х) + 2 (/00^ = дх про

1 I 1

= -2х/(х) + |/(^у + |/(^ = -2х/(х) +1 + |/(^. (4.13)

о.<• х

Друга частинна похідна має вид


д~Н(х,^} ^, /-, . /,/-?/ \ п \ л 7 ^х) \ '• ' / = -2/(х) - 2х/'(х) - /(х) = 0, тобто ———

-) — —./ \"/ —-V \-*/ ^ \—/ 5 "-. „

Інтегруючи це диференціальне рівняння, одержуємо

3

1п/(х)

відкіля

/{х}=з• х~)/^. (4.14) Отримана щільність розподілу /(х) позитивна і дифференцируема. Однак інтеграл

1

[х^йьс розходиться. Отже, щільність/не може про бути дифференцируемой і більше нуля на всьому сегменті

[0,1].

Можна довести, що щільність розподілу може звертатися в нуль лише між нулем і деяким а>0, Таким чином, маємо:

[Про прих<а;

)={ л

\сх '2 прих^а.

Для визначення невідомих параметрів а і зі скористаємося наступними розуміннями. По-перше, ^(х) повинна задовольняти умові нормировки:


(4.15)

1 1

|/(х)^=|/(х)^=1


По-друге, Я(/,1) = v = 0. (41 ^ З рівнянь (4.15) і (4.16) можна опредс -ь

значення а і с. З цією метою перепишемо ці уравнен. у

явному виді.


(4.17)


с х
г у ^ х "-з1х = 1, тобто

1

с-^х^ =2з[

Ч'а

Далі на підставі симетричності гри

Я(/,1) = -Я(1,/) = -с|(1 - 2у)у -учу = 0.

а

Оскільки з^ПРО, це нам дає

1

\{у~У1 - 2у~з//2)^у = {-2у~У2 - 4у ^ \ =0.

і «

Відкіля одержуємо . 2а - Зл/а +1=0. Це квадратне рівняння має два корені: 1 і —. Корінь а=1

суперечить рівності (4.17), а підстановка а = — у це

1 рівність дає з == —.

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

і прих<—;

4

1 -У, 1 /2 прих^—.

2 '4

Графік/^) зображений на мал.4.4.

Кшвський {нститут 1нвестищйного менеджменту



Рис.4.4.

Залишається перевірити, що знайдені стратегії гравців дійсно є оптимальними. Для цього досить переконатися в тім, що для будь-якого х я(х,/)<у=о.

1 1 1. V \( -V У\ 1\ Ъс \ При Х<- Н(х,Л-^2х-у)у^у=- (-2)2х^-2/2 / =———<0,

' ^- | •"V •// - — —

/ 4 4

1 1 оскільки в розглянутому випадку ^ < —. При — < х ^ 1,

формула (4.13) дає

Щх,^)^ \_ ^^ Гу^.+1.,у/2+1(-2)^Х +1=_^ Я^-Х_1+1=о. дх 1 1У 2

х х

Тим самим оптимальність стратегії з щільністю / установлена.


(В - Вірно, Н - Невірно)

1. Ігри називаються нескінченними, якщо у всіх гравців безліч чистих стратегій нескінченно.

2. Нескінченні антагоністичні ігри вирішувати сутужніше, ніж кінцеві.

3. У нескінченній антагоністичній грі принципом оптимальності є принцип максимина.

4. Нескінченні антагоністичні ігри зважуються тільки в чистих стратегіях.

5. Іграми на одиничному квадраті називаються такі нескінченні антагоністичні ігри, для яких можливі стратегії двох гравців^і У е [0,1].

6. Для антагоністичних симетричних ігор оптимальні стратегії гравців 1 і 2 збігаються.

7. Для антагоністичних симетричних ігор ціна гри в>0.

8. У строго опуклій грі гравець 2 має єдино оптимальну стратегію, що є чистої.

Кшвський шститут швестицшного менедж-ченп-

"Наша праворуч", №4'200 ПРО 113

ЗАДАЧІ Знайти хоча б одне рішення нескінченної

антагоністичної гри на одиничному квадраті з наступною функцією виграшу:

1. Я(х,>')=16/-3^+^2;

X, Х ^ -т;

2. Н(х,у)= ^у-х, у^х^у,

Х - V, у ^ X.


3. Щх,у)=\

X, Х^у;

у - х, у < х < у;

х-у, у<х<^+-^;


\-х,


^-+-[-<х

2 ' 1 - л'




4. Я(х,^)=мп

{1х-у, х>у;

5. Н(х,у)=^0, х=у;

^ [х - 2у, х< у.

1-х}

6. Н{х,у)=тах\———>. [у \-у

© Кшвський шспттут 1нвестищйного менеджмент}-



Схожі:

Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconB токсико-інфекційний психоз
Не може знайти собі місця, скаржиться на болі в усьому тілі, "кожна клітинка болить". Bідмічаються спазми шлунка І кишок, проноси....
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconПлан І. Опитування студентів
Опанувати тактичними прийомами обшуку та процесуальним оформленням ходу та результатів цієї слідчої дії
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconІнформаційна картка про інноваційну розробку
Використання довідкових даних, забезпечена можливість включення фото – та відео матеріалів по ходу занять, можливість проведення...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconVI. хвильова оптика. 21. Інтерференція світла Основні формули
Оптична різниця ходу двох променів, що поширюються у різних середовищах відповідно з показнивами заломлення n1 І n2
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconМетодичні вказівки до виконання лабораторної роботи
...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconІі: Векторна алгебра
Вони називаються скалярними величинами або просто скаляром. Поряд зі скалярами існують величини, для характеристики яких необхідно...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconІі: Векторна алгебра §1 Основні поняття
Вони називаються скалярними величинами або просто скаляром. Поряд зі скалярами існують величини, для характеристики яких необхідно...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconЖировая дистрофия
Гистологически отмечено в клубочках и по ходу канальцев отложение гомогенных эозинофильных масс, которые избирательно окрашиваются...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconТема 11 асинхронні електричні машини
Ерс асинхронного дви­гуна (АД), електрична рівновага кола статора (ротора), схема заміщення ад, повна векторна діаграма ад, характеристика...
Інформація про минулий може мінятися від ходу до ходу. Такі ігри називаються позиційними чи іграми в розгорнутій формі. Приклад. Вибори з правом вето iconКрок-1 (1-й семестр)
Гістологічно відзначено відкладення у клубочках і по ходу канальців гомогенних еозинофільних мас, які ви­бірково забарвлюються Конго-рот...
Додайте кнопку на своєму сайті:
Документи


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