Динамічні ігри з повною та досконалою інформацією
Динамічною називається гра, в якій кожен гравець може зробити кілька ходів, і принаймні один із гравців, роблячи хід, знає, який хід зробив інший гравець (можливо він сам).
У динамічних іграх розрізняютьповну ідосконалу інформацію. Якщо всі гравці мають загальну інформацію про правила гри та функції виграшу, то інформацію вважають повною. Це поняття однаковою мірою відноситься як до статичних, так і до динамічних ігор. Поняття досконалої інформації стосується лише динамічних ігор, у яких гравці роблять ходи послідовно у різні моменти часу. Кажуть, що динамічна гра має досконалу інформацію, якщо всі зроблені ходи відразу ж стають відомими всім гравцям.
Іноді динамічну гру зручно уявити у вигляді дерева. Таке уявлення називаєтьсярозгорнутою формою гри. Вона має містити:
- безліч вершин дерева гри, у тому числі одну початкову вершину;
- кожної вершини, крім початкової – єдину вершину, яка безпосередньо передує; при цьому ланцюг попередніх вершин, побудований з будь-якої вершини, повинен закінчуватися в початковій вершині (це передбачає відсутність циклів);
- кожної вершини, крім кінцевих – єдиного гравця, якому належить хід у цій вершині;
- для кожної кінцевої вершини – вектор виграшів усіх гравців;
- (якщо у грі є випадкові ходи «природи», слід задати також розподіл ймовірностей на безлічі всіх можливих ходів «природи»).
Приклад. Гра «Терорист». У літак сів терорист, який вимагає летіти з МайаміГаван замість Нью-Йорка. У припущенні, що терорист не може визначити маршрут польоту, льотчик вибирає,
куди летіти. Якщо він летить до Гавани, гра закінчується, а якщо до Нью-Йорка, то хід робить терорист, який вирішує, підривати літак чи ні. На кінцевих вершинах дерева проставлені виграші гравців
(перший гравець – пілот):
Метод зворотної індукції.
У динамічних іграх з повною та досконалою інформацією зручно вирішувати гру методом зворотної індукції. Відповідно до методу зворотної індукції гра «розмотується» з кінця. При цьому розглядаються всі останні вершини гри, в яких один із гравців робить вибір, виходячи з його раціональності. Далі процес повторюється всім попередніх вершин, доки дійде до початкової вершини. Наприклад, у грі «Терорист» єдиною вершиною, з якої можна розпочати застосування методу зворотної індукції («передфінальна» позиція), є вершина, в якій хід робить терорист. Терорист із двох варіантів (вибухати чи не підривати бомбу в Нью-Йорку) вибирає
– не підривати, оскільки за заданих виграшів йому вигідніше саме не підривати.
Після цього гру можна частково згорнути (редукувати), і дерево гри спрощується:
Оскільки дії терориста в Нью-Йорку неважко передбачити, пілот вибирає летіти до Нью-Йорка, де його виграш більше.
Таким чином, зворотна індукція показує, що пілот полетить до Нью-Йорка, а терорист не підриватиме бомбу.
Зворотну індукцію можна реалізувати на основі функцій відгуку гравців.
24. Застосування методу зворотної індукції з прикладу гри «Рекет».
На першому етапі умова першого порядку для компанії дає таку функцію відгуку компанії на відбирається частку виручки:
Знаючи цю функцію,рекетири максимізують свою функцію виграшу Для цього треба підставити функцію відгуку фірми на функцію виграшу рекетирів і застосувати до отриманого виразу умову першого порядку. Це дає значення =1/2.
25. Подання динамічної гри з повною інформацією у нормальній формі (на прикладі динамічного варіанту гри «Вибір комп'ютера»).
Визначення. Стратегія (чиста) у динамічній грі – це повний план дій гравця, який показує, що він робитиме у кожній з вершин, у якій хід належить йому.
Слід зазначити, що в цьому плані гравець вказує свої дії навіть у тих вершинах, в яких він у процесі гри навряд чи опиниться.
Приклад. Динамічний варіант гри "Вибір комп'ютера", в якому 1-й гравець вибирає собі комп'ютер першим. Дерево гри має вигляд:
1-й гравець має дві стратегії, що збігаються з альтернативами у вершині 1. Гравець 2 має 4 стратегії, кожна з яких визначає його дії у двох вершинах – 2 та 3. Його стратегії такі: (2IBM,3IBM), (2IBM,3Mac) , (2Mac,3IBM), (2Mac,3Mac).