Дата конвертації02.06.2018
Розмір26.56 Kb.
Типконтрольна робота

Скачати 26.56 Kb.

Теорія ігор і статичних рішень

Контрольна робота з курсу «Теорія ігор»


1. Знайдіть рішення по домінуванню в даній грі:

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

стратегія гра рівновагу

a b
A Ф ?
? І
B ? Про
В ?

3. Двоє біжать по лижній трасі назустріч один одному. У кожного лижника 2 стратегії: «поступитися» і «не поступитися». Якщо один з гравців поступається іншому, то його втрати - Про секунд, другий - не втрачає нічого; якщо ж лижники стикаються, то обидва втрачають В секунд.

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

b) Намалюйте лінії відгуків гравців і знайдіть змішані рівноваги в цій грі.

c) Припустимо тепер, що у гравців тепер 3 стратегії: «не поступитися», «поступитися» і «поступитися пів-лижні». Якщо обидва поступилися одна одній пів-лижні, то втрати кожного І секунд, якщо ж один поступився пів-лижні, а другий - ні, то лижники зіткнуться, і втрати при зіткненні у поступився - В + І секунд, у неуступівшего - В секунд. Знайдіть всі рівноваги Неша (в чистих і в змішаних стратегіях).

4. Профспілка укладає з фірмою угоду на кілька років про рівень заробітної плати w> 0. Профспілка максимізує функцію сукупного прибутку членів профспілки (зарплата за вирахуванням витрат від роботи): u (w, L) = wL-І * L 2, фірма максимізує свій прибуток (випуск за винятком зарплати): П (w, l) = Ф * L 0.5 -wL.

a) Знайти рівноважний рівень заробітної плати і зайнятості в статичної грі.

b) Яке рівновагу в динамічної гри, якщо профспілка досить потужний, щоб нав'язати фірмі будь-який рівень заробітної плати, після чого фірма не може змінювати рівень заробітної плати протягом терміну контракту, але може наймати будь-яку кількість праці L> 0.

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

5. У цій грі з нульовою сумою знайдіть рівновагу в обережних стратегіях. Чи існує в цій грі рівновагу Неша в чистих стратегіях?

c1 c2 c3 c4 c5
s1 5 2 3 6 4
s2 4 1 1 5 0
s3 6 0 4 9 -3

6. На кораблі 50 піратів ділять 100 шматків золота за таким правилом: першим поділ пропонує капітан. Якщо хоча б половина команди (включаючи капітана) згодна, то на цьому гра і закінчується. Якщо немає, то капітана викидають за борт і розподіл пропонує наступний по старшинству і т.д. Знайдіть вчинене подигровое рівновагу в цій грі.

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

Приклад повинен бути дійсно з реальний життя, а не просто виходити з сімейного спору заміною «чоловік» на «зять» та «театр» на «рибалка» - такі приклади оцінюються в 0 балів!


1. Знайдіть рішення по домінуванню в даній грі

a b c d
A

2

5

6

2

4

1

3

0

B

1

4

4

3

1

2

2

1

C

0

1

1

1

5

1

1

5

D

3

2

1

0

2

0

4

4

Рішення:

1. У вихідній грі стратегія d строго домінує стратегію a. Більше строго або нестрого домінуючих стратегій у першого або другого гравця немає. Очевидно, що другий гравець не буде грати стратегію a і її можна виключити.

отримуємо:

b c d
A

6

2

4

1

3

0

B

4

3

1

2

2

1

C

1

1

5

1

1

5

D

1

0

2

0

4

4

2. У вийшла грі бачимо, що стратегія З першого гравця строго домінує стратегію D. А також стратегія В строго домінує стратегію А. Розглянемо обидва варіанти. У першому - викреслюємо стратегію D, в другому - стратегію А.

отримуємо:


b c d
A

6

2

4

1

3

0

B

4

3

1

2

2

1

C

1

1

5

1

1

5

b c d
B

4

3

1

2

2

1

C

1

1

5

1

1

5

D

1

0

2

0

4

4


3. В отриманій грі в обох варіантах отримуємо, що у другого гравця немає строго домінуючих стратегій. Однак в першому варіанті у другого гравця є нестрого домінуюча стратегія b (домінує стратегію d). У другому ж варіанті у другого гравця немає строго або нестрого домінуючих стратегій. Проте як і раніше є строго домінуюча стратегія C першого гравця, яка домінує стратегію D.

Продовжимо розглядати 2 варіанти гри: в першому варіанті викреслюємо стратегію d, а другому - стратегію D. Отримаємо 2 гри:


b c
A

6

2

4

1

B

4

3

1

2

C

1

1

5

1

b c d
B

4

3

1

2

2

1

C

1

1

5

1

1

5


4. У першому варіанті отриманої нової гри бачимо, що стратегія B першого гравця строго домінує і стратегію А і стратегію C. У другому ж варіанті бачимо, що стратегія b другого гравця нестрого домінує стратегію d. Виключивши в першому варіанті стратегію A отримаємо нову гру, збігається з варіантом, якщо в другому варіанті виключити стратегію d. Ще один варіант гри виходить винятком стратегії З в першому варіанті гри. Разом знову маємо 2 можливих варіанти гри.


b c
B

4

3

1

2

C

1

1

5

1

b c
A

6

2

4

1

B

4

3

1

2


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

Виключимо в першому варіанті стратегію С, у другому - з.


b c
B

4

3

1

2

b
A

6

2

B

4

3


6. У першому варіанті стратегія b другого гравця строго домінує стратегію с. У другому варіанті стратегія B першого гравця строго домінує стратегію А. Викресливши в обох варіантах строго домінованих стратегії, отримаємо однаковий варіант гри:

b
B

4

3

На підставі цього можна зробити висновок, що у вихідній грі повинен реалізуватися результат (B, b).


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

a b
A

7

?

?

4

B

?

25

9

?

Рішення:

Замінимо знаки питання на невідомі змінні наступним чином:

a b
A

7

y

x

4

B

t

25

9

z

Спробуємо заповнити пропуски в таблиці так, щоб рівноваги Неша досягалися в варіантах гри (A, a), (B, a), (B, b), а при грі (A, b) рівновага Неша не досягалось. Тоді повинна виконуватися система нерівностей (об'їдять їх парами для кожного варіанту гри):

Звідки отримуємо:

Візьмемо мінімальні цілі числа, що задовольняють системі нерівностей. Отримаємо гру:


a b
A

7

25

6

4

B

9

25

9

5

Дійсно, в даній грі варіанти (A, a), (B, a), (B, b) будуть равновесиями за Нешем, тому що тут жодному з гравців не вигідно змінити свою стратегію, а при грі (A, b) кожному з гравців вигідно змінити свою стратегію.

Знайдемо рівновагу в змішаних стратегіях. Припустимо, що перший гравець з імовірністю μ грає стратегію A, відповідно з ймовірністю (1 - μ) - стратегію B. Другий гравець з імовірністю ν грає стратегію a, а з ймовірністю (1 - ν) - стратегію b. Тоді функції виграшу гравців будуть виглядати наступним чином:

;

Тоді функції відгуку будуть наступними:

Маємо 2 рівноваги в змішаних стратегіях.Якщо другий гравець грає стратегію b, то перший гравець завжди буде грати стратегію B. Якщо перший гравець грає стратегію А, то другий гравець буде грати стратегію a.

Рішенням же в домінованих стратегіях буде (B, a).


3. Двоє біжать по лижній трасі назустріч один одному. У кожного лижника 2 стратегії: «поступитися» (У) і «не поступитися» (Н). Якщо один з гравців поступається іншому, то його втрати - 9 секунд, другий - не втрачає нічого; якщо ж лижники стикаються, то обидва втрачають 25 секунд.

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

e) Намалюйте лінії відгуків гравців і знайдіть змішані рівноваги в цій грі.

f) Припустимо тепер, що у гравців тепер 3 стратегії: «не поступитися», «поступитися» і «поступитися пів-лижні». Якщо обидва поступилися одна одній пів-лижні, то втрати кожного 4 секунд, якщо ж один поступився пів-лижні, а другий - ні, то лижники зіткнуться, і втрати при зіткненні у поступився - 29 секунд, у неуступівшего - 4 секунди. Знайдіть всі рівноваги Неша (в чистих і в змішаних стратегіях).

Рішення:

a) Складемо платіжну матрицю цієї гри:

У Н
У

-9

-9

0

-9

Н

-9

0

-25

-25

У чистих стратегіях рівноваги в даній грі немає.

b) Знайдемо рівновагу в змішаних стратегіях.

Припустимо, що перший гравець з імовірністю μ грає стратегію У, відповідно з ймовірністю (1 - μ) - стратегію Н. Другий гравець з імовірністю ν грає стратегію У, а з ймовірністю (1 - ν) - стратегію Н.

Функції виграшу гравців:


Відповідно функції відгуків:

Маємо 2 точки перетинів ліній, відповідні равновесиям в змішаних стратегіях:

2. (Н; У), тобто перший гравець завжди не поступається, а другий - поступається;

3. (У; Н), тобто перший гравець завжди поступається, а другий - не поступається;

4. Кожен з гравців з ймовірність 16/25 поступається лижню і з ймовірністю 9/25 не поступається лижню.

c) Складемо платіжну матрицю гри:

У Н УП
У

-9

-9

0

-9

-4

-9

Н

-9

0

-25

-25

-29

-25

УП

-9

-4

-25

-29

-4

-4

У чистих стратегіях рівноваги немає.

4. Профспілка укладає з фірмою угоду на кілька років про рівень заробітної плати w> 0. Профспілка максимізує функцію сукупного прибутку членів профспілки (зарплата за вирахуванням витрат від роботи): u (w, L) = wL-4 * L 2, фірма максимізує свій прибуток (випуск за винятком зарплати): П (w, l) = 7 * L 0.5 -wL.

d) Знайти рівноважний рівень заробітної плати і зайнятості в статичної грі.

e) Яке рівновагу в динамічної гри, якщо профспілка досить потужний, щоб нав'язати фірмі будь-який рівень заробітної плати, після чого фірма не може змінювати рівень заробітної плати протягом терміну контракту, але може наймати будь-яку кількість праці L> 0.

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

Рішення:

b) Профспілка встановлює рівень заробітної плати. У свою чергу виходячи з цього значення фірма визначає кількість зайнятих. Припустимо, що профспілка встановив рівень заробітної плати w *. Тоді прибуток фірми буде П (w *, l) = 7 * L 0.5 - w * L. максимізуючи прибуток по L.

П L '(w *, l) = 3.5L -0.5 - w * = 0 при L * = .

Тобто при встановленні профспілкою рівня з / п в значення w * фірма прийме рішення про наймання робочої сили в значення L * = .

Максимізували тепер функцію сукупного прибутку членів профспілки u (w, L) = wL-4 * L 2

Підставами в функцію знайдене на попередньому кроці значення L *.

u (w, L *) = wL * 4 * L * 2 =

. , звідки .

Рішення гри: .

c) В даному випадку спочатку фірма встановлює рівень з / п. Після чого профспілка приймає рішення про кількість зайнятих, максимізуючи свій прибуток. Припустимо, що фірма прийняла рішення про рівень з / п рівним w *.

Тоді прибуток членів профспілки буде визначатися: u (w *, L) = w * L-4 * L 2. Профспілка максимізує свій прибуток, варіюючи значення L.

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

П (w, L *) = 7 * L * 0.5 -wL * = . П w '(w, L *) = = 0 при .

відповідно .

Рішення гри: ( ; ).

5. У цій грі з нульовою сумою знайдіть рівновагу в обережних стратегіях. Чи існує в цій грі рівновагу Неша в чистих стратегіях?

c1 c2 c3 c4 c5
s1 5 2 3 6 4
s2 4 1 1 5 0
s3 6 0 4 9 -3

Рішення:

Гра антагоністична, значить можемо знайти MinMax і MaxMin і порівняти їх.

MaxMin = Max (2, 0, -3) = 2 і відповідає s1.

MinMax = Min (6, 2, 4, 9, 4) = 2 і відповідає c2.

Отримуємо, що MinMax = MaxMin = 2, отже в грі існує рівновага Неша в чистих стратегіях і відповідає (s1, c2).

6. На кораблі 50 піратів ділять 100 шматків золота за таким правилом: першим поділ пропонує капітан. Якщо хоча б половина команди (включаючи капітана) згодна, то на цьому гра і закінчується. Якщо немає, то капітана викидають за борт і розподіл пропонує наступний по старшинству і т.д. Знайдіть вчинене подигровое рівновагу в цій грі.

Рішення:

Будемо використовувати метод зворотного індукції. Впорядкуємо всіх піратів по старшинству.

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

2. Залишилося 2 пірата. Щоб старшому пірату роздобути все золото, йому потрібно набрати один голос. Відповідно він запропонує все золото віддати йому, погодиться і отримає все золото. Результат гри не залежить від того, згоден з цим рішенням або не згоден другий пірат.

3. Залишилося 3 пірата. Щоб отримати схвалення плану і залишитися в живих найстаршому пірату необхідно отримати 2 голоси. Другий пірат знає, що він може отримати все золото, якщо залишиться він і ще один пірат. Тому він завжди буде голосувати проти. Залишився наймолодший пірат. Він також знає, що якщо залишаться 2 пірата, то він не отримає нічого. Якщо ж в поточному розподілі йому дістанеться хоча б один шматок голосу, то він проголосує за поділ. Тому в умовах, коли залишилося 3 пірата старший пропонує наймолодшому один шматок золота, а все інше залишає собі. При такому розподілі він точно отримає 2 голоси: свій і наймолодшого пірата.

4. Залишилося 4 пірата. Для прийняття плану поділу знову необхідно отримати 1 додатковий голос, крім свого. При цьому всі пірати розуміють, що якщо залишиться 3 пірата, то розподіл буде здійснений відповідно до п.3, в якому наймолодший пірат отримує 1 шматок золота другий за старшинством не отримує нічого. Якщо другому за старшинством пірату запропонувати хоча б один шматок золота, то він проголосує за цей план, тому що його виграш більше. Необхідна кількість голосів буде набрано і іншим піратам можна не платити нічого, і від їх варіантів голосування нічого не залежить. Відповідно поділ буде таким: наймолодшому пірату не дістається нічого, другого віддається 1 шматок золота, третій нічого, а четвертий (найстарший з решти) отримує 99 шматків золота.

5. Залишилося 5 піратів. Необхідна підтримка двох додаткових голосів. На попередньому етапі нічого не отримують наймолодший і третій пірати і вони це розуміють. Тому запропонувати їм більш вигідні умови і отримати підтримку їхніх голосів. Вступаємо відповідно до п 3. - віддаємо наймолодшому і третього за старшинством пірату на 1 шматку золота. Решта 98 залишаємо собі. Вони проголосують за розподіл, тому що в іншому випадку не отримають нічого.

6. Продовжуючи індукцію, беручи до уваги, що 50 - парне число, отримуємо, що капітан повинен запропонувати наступний варіант поділу: наймолодший пірат не отримує нічого, другий за старшинством отримує 1 шматок золота, третій знову не отримує нічого, четвертий отримує 1 шматок золота і т.д. Разом 24 шматка золота. Решта 76 залишити собі. Разом він отримає 25 голосів на підтримку, включаючи свій. Нікому з піратів, які проголосували за розподіл не вигідно змінювати стратегію, тому що при зміні він не отримає нічого.

Отже, капітан пропонує описаний вище план поділу золота.

Відповідно досконалим подигровим рівновагою буде наступний набір стратегій:

пірат 1 2 3 4 ... 50 (капітан)
голосування проти за проти за ... за
виграш 0 1 0 1 ... 76

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

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

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

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

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

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

7. Кожен їде в той час, в яке йому зручно. Це можливо, але виграш кожного тут буде вже менше, тому що в дорозі нудно і нецікаво.

8. Самий неймовірний варіант, коли хлопці їдуть раніше, а я їду пізніше. Варіант незручний для всіх.

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