> Теорема 1.
) Для того, щоб мала седловую точку на, необхідно і достатньо, щоб було виконано рівність
) Нехай виконано попереднє рівність. Пара є сідловою тоді і тільки тоді, коли - Максиміна, а - мінімаксна стратегії гравців.
Теорема.
) Якщо - Максиміна стратегія першого гравця, - мінімаксна стратегія другого гравця гра Г має рішення, - ціна гри, - ситуація рівноваги.
) Якщо Г має рішення - Максиміна стратегія першого гравця, - мінімаксна стратегія другого гравця.
. 3 Змішане розширення ігри
Так само теорія ігор пропонує використовувати гравцям змішані стратегії. Розглянемо, як вони визначаються.
Визначення 6. Змішаної стратегією першого гравця в грі Г називається імовірнісний розподіл на безлічі стратегій.
Для першого гравця застосувати змішану стратегію - це вибрати стратегію як реалізацію випадкової величини, що має закон розподілу.
Розглянемо вид змішаної стратегії, характерний для матричної гри.
Нехай. Тоді замість для позначення змішаної стратегії будемо використовувати імовірнісний вектор задовольняє обмеженням Якщо застосовується, то стратегія вибирається з імовірністю.
Безліч будемо називати безліччю чистих стратегій.
Позначимо безлічі імовірнісних векторів для першого і другого гравців відповідно. Тоді функція виграшу -, а відповідна антагоністична гра.
Визначення 7. Антагоністична гра називається змішаним розширенням гри Г. - безлічі стратегій.
Для гри можна також ввести поняття максиминной і мінімаксної стратегій, седловой точки функції, рішення гри. З точністю до позначень вони будуть аналогічні відповідним поняттям для гри Г. Всі властивості ігри Г справедливі і для гри
Теорема 2. (основна теорема теорії матричних ігор).
Всяка гра має рішення.
Останнє твердження еквівалентно тому, що будь матрична гра Г має рішення в змішаних стратегіях.
Теорема 3.
) - рішення
) - ситуація рівноваги в, при чому виконуються нерівності (1) - рішення.
2. Позиційні ігри
. 1 Поняття позиційної гри, дерева гри та інформаційного безлічі
Визначення 1. позиційний грою називається безкоаліційна гра, що моделює процеси послідовного прийняття рішень гравцями в умовах мінливої ??в часі інформації.
Найпростіші приклади позиційних ігор: шахи, шашки, хрестики-нулики, доміно та ін.
Визначення 2. Стани гри називають позиціями, а можливі вибори в кожній позиції - альтернативами.
Визначення 3. Деревоподібне впорядкована множина, за допомогою якого можна представити графічно безліч позицій в такій грі, називається деревом гри.
Для визначеності будемо розглядати в цьому параграфі, §3 і §4 позиційні ігри, в кожній позиції яких рівно дві альтернативи - 1 і 2.
Визначення 4. Ланцюг, що зв'язує початкову вершину з остаточною називається партією.
Число різних партій дорівнює числу остаточних вершин (позицій).
Розрізняють позиційні гри з повною інформацією і позиційні гри з неповною інформацією.
У позиційних іграх з повною інформацією кожен гравець, роблячи свій хід, знає, в якій позиції дерева гри він знаходиться в даний момент.
У позиційних іграх з неповною інформацією гравець, що робить хід, не знає точно в якій саме позиції дерева гри він фактично знаходиться.
Визначення 5. Інформаційним безліччю називається деяка безліч позицій, відоме гравцеві і що включає його фактичну позицію.
Таким чином, у грі з неповною інформацією гравець при своєму ході знає, в якому інформаційному безлічі він знаходиться, а в який конкретно позиції цієї множини - йому невідомо.
. 2 Приклади
Приклад 1. Дерево позиційної гри (жирним виділено одну з партій).
Рис. 1.
3. Позиційні антагоністичні гри з повною інформацією
. 1 Поняття позиційної гри з повною інформацією
Визначення 1.
Позиційна гра називається грою з повною інформацією, якщо в кожній позиції будь-який її партії гравець, що робить хід, знає, які альтернативи були обрані на попере...
