Розв’язання матричних ігор у чистих стратегіях

Матрична гра двох гравців з нульовою сумою може розглядатися як така абстрактна гра двох гравців.

Перший гравець має m стратегій i = 1,2,..., m, другий має n стратегій j = 1,2,..., n. Кожній парі стратегій (i,j) поставлено у відповідність число а_ij, що має сенс виграшу гравця 1 за рахунок гравця 2, якщо перший гравець прийме свою стратегію i, а 2 – свою стратегію j.

Кожен з гравців робить один хід: гравець 1 вибирає свою стратегію i (i= ), гравець 2 – свою стратегію j (j = ), після чого гравець 1 отримує виграш а_ij за рахунок гравця 2 (якщо а_ij< 0, то це значить, що гравець 1 платить другому суму програшу | а_ij |). На цьому гра закінчується.

Кожна стратегія гравця i= і j = часто називається чистою стратегією. Якщо розглянути нижченаведену платіжну матрицю то проведення кожної партії матричної гри з матрицею А зводиться до вибору гравцем 1 i -го рядка, а гравцем 2 j -го стовпця і отримання гравцем 1 (за рахунок гравця 2) виграші а_ij.

А =

Головним у дослідженні ігор є поняття оптимальних стратегій гравців. У це поняття інтуїтивно вкладається такий зміст – стратегія гравця є оптимальною, якщо застосування цієї стратегії забезпечує йому найбільший гарантований виграш за будь-яких стратегій іншого гравця.

Виходячи з цих позицій, гравець 1 досліджує матрицю виграшів А таким чином: для кожного значення i (i = ) визначається мінімальне значення виграшу залежно від застосовуваних стратегій гравця 2

а_ij, (i = ),

тобто визначається мінімальний виграш для гравця 1 за умови, що він прийме свою чисту стратегію i, потім з них відшукується така стратегія i = i_о, за якою цей мінімальний виграш буде максимальним, тобто знаходиться

а_ij = = . (8.1)

Означення 8.1. Число , визначене за виразом (8.1) називається нижньою чистою ціною гри і показує, який мінімальний виграш може гарантувати собі перший гравець, застосовуючи свої чисті стратегії для будь-яких дій другого гравця. Гравець 2 при оптимальному своєму поводженні повинен прагнути, по можливості, за рахунок своїх стратегій максимально зменшити виграш гравця 1. Тому для гравця 2 відшукується

а_ij,

тобто визначається максимальний виграш гравця 1, за умови, що гравець 2 застосує свою j -ту чисту стратегію. Потім гравець 2 шукає таку j = j₁ стратегію, за якою гравець 1 отримує мінімальний виграш, тобто знаходить

a_ij = = (8.2)

Означення 8.2 Число , визначене за виразом (8.2), називається чистою верхньою ціною гри і показує, який максимальний виграш за рахунок своїх стратегій може собі гарантувати гравець 1. Іншими словами, застосовуючи свої чисті стратегії гравець 1 може забезпечити собі виграш не менше , а гравець 2 за рахунок застосування своїх чистих стратегій може не допустити виграш гравця 1 більше, ніж .

Означення 8.3. Якщо у грі з матрицею А = , то говорять, що ця гра має сідлову точку в чистих стратегіях і чистій ціні гри u = = .

Сідлова точка – це пари чистих стратегій (i_о, j_о) щодо гравців 1 і 2, за якими досягається рівність = . У це поняття вкладено такий зміст: якщо один із гравців дотримується стратегії, що відповідає сідловій точці, то інший гравець не зможе діяти краще, ніж дотримуватись стратегії, що відповідає сідловій точці. Математично це можна записати й інакше:

, (8.3)

де i, j – будь-які чисті стратегії відповідно гравців 1 і 2; (i_о, j_о) – стратегії, що утворюють сідлову точку.

Таким чином, виходячи з (8.3), сідловий елемент є мінімальним в i -ому рядку і максимальним у j -ому стовпці матриці А. Відшукування сідлової точки матриці А здійснюється таким чином: в матриці А послідовно в кожному рядку знаходять мінімальний елемент і перевіряють, чи є цей елемент максимальним у своєму стовпці. Якщо це так, то він і є сідловим елементом, а пари стратегій, що йому відповідають, утворюють сідлову точку. Пари чистих стратегій (i_о, j_о) гравців 1 і 2, що утворюють сідлову точку і сідловий елемент , називається розв’язком гри. При цьому i_о і j_о називаються оптимальними чистими стратегіями відповідно першого і другого гравців.