чікуваний виграш гравця 1 (програш гравця 2) дорівнює
Основна теорема теорії ігор (теорема Джона фон Неймана) стверджує, що будь матрична гра з нульовою сумою завжди має сідлову точку, тобто існують вектори P і Q такі, що
(V - ціна гри).
. Матричні ігри та лінійне програмування
Очевидно, що якщо гравець 1 відступить від оптимальної політики, а гравець 2 діятиме оптимально, то виграш гравця 1 буде менше ціни гри, і якщо гравець 2 відступить від оптимальної політики при збереженні оптимального поведінки гравцем 1, то його програш перевищить ціну гри:
Міркування гравця 1: мені хотілося б максимізувати ціну гри, тобто мій гарантований виграш, і я повинен підібрати систему значень Pi так, щоб при будь-якому виборі супротивника мій очікуваний виграш був більше ціни гри.
Міркування гравця 2: мені хочеться зменшити мій гарантований програш, тобто ціну гри, і мені треба підібрати значення Qj так, щоб при будь-якому виборі супротивника мій програш був менше ціни гри.
Звідси виникають два завдання:
Легко показати, що ці завдання утворюють пару двоїстих задач лінійного програмування.
Т.а. рішення матричної гри зводиться до вирішення пари двоїстих лінійних програм.
Звернемо увагу на те, що при збільшенні елементів матриці R на будь-яку константу С ціна гри збільшиться на С і ця зміна не матиме впливу на шукані ймовірності виборів. Таким чином, можна домогтися, наприклад, позитивності елементів матриці і, отже, ціни гри. Тому можна припустити, що ціна гри V позитивна.
У припущенні V gt; 0 проведемо заміну змінних
Хi=Pi/V, Yj=Qj/V.
Звідси видно, що
Відповідно, поставлені завдання можна перетворити до задачам з меншим числом змінних:
Наприклад, для гри з матрицею
виникають завдання:
максимізувати мінімізувати
+ Y2 + Y3 X1 + X2 + X3
при
+ 2 Y2 + 3 Y3 Ј 1 X1 + 4 X2 + 2 X3 и 1
Y1 + Y3 Ј 1 +2 X1 + 3 X3 и 1
Y1 + 3 Y2 Ј 1 3 X1 + X2 и 1, Y2, Y3 і 0 X1, X2, X3 і 0
Вирішення цих завдань симплексним методом дає оптимальні значення
={11/37, 4/37, 5/37}, Y={8/37, 7/37, 5/37}
і екстремуми цільових функцій, рівні 20/37.
Звідси V=37/20, P={11/20, 4/20, 5/20}, Q={8/20, 7/20, 5/20}.
. Ітеративний метод вирішення матричних ігор
Як ми показали вище, ігри можуть вирішуватися методами лінійного програмування. Тут ми розглянемо ітеративний метод Брауна-Робінсон, звичайно використовуваний при вирішенні ігр великої розмірності.
Використовується багаторазова реалізація гри на основі знання передісторії з послідовним вдосконаленням стратегій.
Для прикладу візьмемо задачу, яку ми тільки що вирішили.
Нехай гравець 1 зробив вибір 1 з очікуваними виграшами 1, 2, 3. Противник, прагнучи мінімізувати свій програш, вдасться до вибору 1 з очікуванням програшу 1, 4, 2. Гравець 1 в прагненні максимізувати свій виграш вдасться до вибору 2, що дасть йому надію на сумарний виграш (1 + 4, 2 + 0, 3 + 1). Але тоді його противник знайде серед цих значень менше і вдасться до вибору 2 з очікуваним сумарним програшем (1 + 2, 4 + 0, 2 + 3) і т.д.
Цей процес реалізується досить багато раз з подальшим пошуком частоти використання виборів і усередненням значень виграшів-програшів.
У результаті 10 виборів для 1-го гравця частоти склали 0.6, 0.2, 0.2; для гравця 2 - 0.4, 0.3, 0.3; оцінка ціни гри в діапазоні від 1.7 до 1.9.
. Багатокрокові гри. Ігри на виживання
Попереднє розгляд ігр проводилося в припущенні, що реалізація гри може здійснюватися будь-яке число разів. Наприклад, для гри орел-решка raquo ;, де в разі збігу пред'являються сторін монети виграє гравець 1 і при розбіжності - гравець 2, оптимальна політика гравців полягає в равновероятностних виборі орла і решки і ціна гри дорівнює 0.
Однак в реальній грі з обмеженими ресурсами політика гравців залежить від результату попередніх дій і від тривалості гри.
Відповідно для матричної гри
де Fk (A, B) - очік...
