го гравця при стратегії х 1 . Аналогічно можна визначити гарантовані виграші для будь-якої стратегії 1-го гравця - А (х). Передбачається, що гравці уникають необгрунтованого ризику і вибирають ту стратегію, яка дає максимальний з усіх гарантованих виграшів.
Число називається нижньою ціною гри або Максиміна .
А відповідна стратегія - максиминной.
Також можна міркувати і щодо 2-го гравця. Тільки в А зазначені його програші, які він прагне мінімізувати. Наприклад, стратегія y 1 може принести 2-му гравцю програш 7, 2 або 3. Але вже більше 7 він не програє. Отже, число 7, що є максимальним елементом стратегії y 1 , є гарантований програш 2-го гравця при y 1 . Визначимо всі гарантовані програші - В (y). Яким же програшем може обмежитися 2-й гравець?
Число називається верхньою ціною гри або МініМакс.
А відповідна стратегія - мінімаксної.
. Теореми теорії ігор
Теорема 1. (основна теорема теорії ігор).
Всякая кінцева гра має ціну і у кожного гравця існує щонайменше одна оптимальна стратегія.
Тереми 2. Нижня ціна гри завжди вбирається верхньої ціни гри,.
Розглянемо два випадки.
. Нехай. p> Гра, для якої, , називається грою з сідловою. Якщо, то С є ціною гри, а стратегії гравців, забезпечують їм виграш чи програш, рівний С, є оптимальними. Якщо гра з сідловою має С = 0, то вона є справедливою, якщо С0, - несправедливою. p>. Нехай. У цьому випадку важко визначити ціну гри та оптимальні стратегії гравців. Повернемося до розглянутого прикладу. = 3, а = 5. Значить, перший гравець може гарантувати собі виграш, рівний 3, а другий - обмежити свій програш 5. Область між і є як би нічийною, і кожен гравець може спробувати поліпшити свій результат за рахунок цієї області. Які в цьому випадку оптимальні стратегії гравців? Якщо кожен гравець буде застосовувати стратегію, відповідну його максимальному гарантованого виграшу або програшу, противник може здогадатися про його наміри і поліпшити свій результат. Наприклад, перший гравець використовує х3, а другий - y2. Другий гравець помітив, що перший весь час застосовує x3, і вирішив застосувати y1, звівши свій програш до меншого числа. Таким чином, щоб мати успіх, кожен гравець повинен зберігати свій вибір в секреті. Це важко зробити, якщо гра повторюється багато разів. p> Секретність можна зберегти, якщо кожен раз вибирати стратегію випадковим чином (кидаючи монету, кістка і т.п.). При цьому виграш і програш будуть випадковими величинами. Результат можна оцінити середньою величиною програшу або виграшу. Так, у нашому випадку, якщо другий гравець використовує свої стратегії y1, y2, y3 випадковим чином, наприклад, з імовірностями 1/3; 1/3; 1/3, відповідно, то середнє значення його програшу може бути:
якщо перший використовує х1:
Сср = 1/3 а11 + 1/3 а12 + 1/3 а13 = 7/3 + 2/3 + 5/3 = 14/3;
якщо перший використовує х2:
Сср = +1/3 а21 + 1/3 а22 + 1/3 А23 = 2/3 + 2/3 + 3/3 = 7/3,
якщо перший використовує х3:
Сср = 1/3 а31 + 1/3 А32 + 1/3 А33 = 3/3 + 5/3 + 4/3 = 4. Таким чином, другий гравець може обмежити свій програш вже не 5, а 14/3, нез авісимий від стратегії першого гравця. Отже, у ряді випадків виявляється доцільне не намічати заздалегідь стратегії, а вибирати ту чи іншу випадковим чином. Стратегія, заснована на випадковому виборі, називається змішаною стратегією. p> Вектор, кожна компонента якого показує відносну частоту (імовірність) використання гравцем відповідних чистих стратегій, називається змішаною стратегією.
Нехай u = (u1, ..., um) і z = (z1, ..., zn), відповідно, ймовірності окремих фіналів механізму випадкового вибору 1-го і 2-го гравців.
З теорії ймовірностей має бути відомо, що
1) ui 0, i =; zj. 0, j =; (тому 0 р 1);
) і (тому р (U) = 1, U-достовірна подія). Якщо u * - оптимальна стратегія 1-го гравця, z * - оптимальна стратегія 2-го гравця, то число є ціною гри.
Визначення оптимальних стратегій і ціни гри складає процес вирішення гри.
Теорема 3 (про ціну гри).
Всякая матрична гра з нульовою сумою має рішення в змішаних стратегіях. Для того, щоб число С було ціною гри, а u * і z * - оптимальними стратегіями гравців, необхідно і достатньо виконання нерівностей:
і.
Теорема дає відповідь на питання про існування рішення гри і визначає шлях вирішення.
В окремому випадку, коли принаймні в одного з гравців є тільки 2 стратегії, справедлива...
