дніх ходах.
Розглянемо інше уявлення позиційної гри з повною інформацією. Визначимо її наступним чином. Гра відбувається протягом кроків з номерами На кожному кроці гравці по черзі вибирають альтернативи - значення змінних.
Крок 1. Перший гравець вибирає альтернативу, потім другий гравець, знаючи вибір першого, вибирає альтернативу.
Нехай гравці протягом кроків вибирали альтернативи відповідно. Позначимо
Крок t. Перший гравець, знаючи попередні значення, вибирає альтернативу. Далі другий гравець вибирає альтернативу, знаючи.
Після останнього кроку виникає пара - партія гри. Для будь-якої партії задається виграш першого гравця.
. 2 Нормалізація позиційної гри з повною інформацією
Далі визначимо гру в нормальній формі. На кроці перший гравець може вибрати альтернативу як значення функції, яка повинна бути визначена при всіляких значеннях аргументів. Позначимо множину всіх таких функцій через.
Зауважимо, що, так як на першому кроці перший гравець ніякої інформацією не володіє.
Стратегія першого гравця являє собою набір функцій
Аналогічно, на кроці другий гравець може вибирати альтернативу як значення функції, яка повинна бути визначена при всіляких значеннях аргументів. Позначимо множину всіх таких функцій через. Стратегія другого гравця являє собою набір функцій
Будь парі стратегій однозначно відповідає партія гри: і т.д.
Далі, де - партія, відповідна стратегіям. Багатокрокова гра з повною інформацією визначена в нормальній формі.
Іншими словами, нормалізація - процес відомості позиційної гри до матричної.
. 3 Теорема Цермело
Нехай - гра, в якій безлічі кінцеві.
Визначимо величину
Теорема 1 (Цермело).
Всяка багатокрокова антагоністична гра з повною інформацією має рішення в чистих стратегіях.
Доказ.
Покажемо, що функція має сідлову точку на. Для того достатньо довести, що
1) ;
2) .
Доведемо нерівність 1). Маємо
Нерівність 2) доводиться аналогічно.
. 4 Приклади
Приклад 2. Розглянемо гру з повною інформацією. Починає гравець А. Він вибирає одну з двох можливих альтернатив - число, рівне або 1, або 2 (перша і друга альтернатива відповідно). На хід гравця А гравець В відповідає своїм ходом, також вибираючи одну з двох альтернатив - число, рівне або 1, або 2. У результаті гравець А чи виграє, чи програє.
- й хід. Гравець А вибирає
- й хід. Гравець В вибирає, знаючи вибір числа гравцем А.
Функція виграшу для гравця А задається наступним чином
На малюнку 2 показані дерево гри та інформаційні множини.
Рис. 2, 3
Приклад 2 (продовження). Нормалізація гри.
У позначеннях, наведених вище,,,,,,,.
Опишемо стратегії гравців.
У гравця A два чистих стратеги, тобто.У Гравця О четвертій чистих стратегії:
Покажемо, як задається виграш гравця А.
Якщо, наприклад, гравець А вибрав стратегію, а гравець B - -СТРАТЕГИ. Тоді. Решта виграші розраховуються аналогічно. Запишемо їх у вигляді матриці гри:
де рядки відповідають стратегіям гравця A, а стовпці - стратегіям гравця В.
Отримана матриця має сідлову точку. Оптимальна стратегія першого гравця - вибрати, другого гравця -. Ціна гри.
Приклад 4. Переговори .
У переговорах беруть участь дві сторони A і B. Спочатку сторона A висловлює одне з декількох пропозицій, здатних зацікавити іншу сторону. Потім сторона В, ознайомившись з пропозицією сторони А, висловлює одне з декількох зустрічних пропозицій, здатних, на її думку, зацікавити сторону А. У свою чергу, сторона А, ознайомившись з реакцією боку В на зроблені пропозиції, висловлює їй нову пропозицію, внісши одну з декількох можливих коригувань у свою початкову пропозицію з урахуванням думки боку В і т. д.
Змоделюймо короткий переговорний процес триходовий позиційної грою з повною інформацією.
