§ 3. Оптимальні змішані стратегії

Означення 5.2. Змiшаною стратегією гравця P₁ називається вектор

а змішаною стратегією гравця P₂ — вектор

Величини x_i (i=1,...,m) та y_j (j=1,...,n) трактуються як ймовірності, з якими гравці P₁ та P₂ вибирають відповідно i-й рядок та j-й стовпець матриці С.

Зрозумiло, що i-у чисту стратегію гравця P₁ можна розглядати як частинний випадок його змішаної стратегії x при x_i=1, x_k=0, k≠i. Це ж стосується i j-ї чистої стратегії гравця P₂.

Позначимо через X та Y, відповідно, множини змішаних стратегій першого та другого гравців, тобто

Якщо гравець P₁ використовує свою змiшану стратегію x є X, а P₂ — y є Y, то математичне сподівання плати гравця P₁ гравцеві P₂ (середній виграш гравця P₂) знаходиться звичайним чином

(10)

Трiйка називається усередненням матричної гри G.

Мiркуючи аналогічно випадку чистих стратегій, приходимо до висновку, що гравець P₁ може забезпечити собі середній програш не більше

(11)

а гравець P₂ може забезпечити собі середній виграш не менше

(12)

Задачі (11) та (12) є задачами пошуку гарантованих змішаних стратегій першим та другим гравцем відповідно.

Якщо для деяких змішаних стратегій x* є X, y* є Y

F(x*,y) ≤ F(x*,y*) ≤ F(x,y*), (13)

для всіх xєX, yєY, тобто якщо (x*,y*) є сiдловою точкою функції F(x,y), то, як було доведено раніше,

(14)

Аналогiчно випадку існування розв'язку гри G у чистих стратегіях можна дати такі означення.

Компоненти x* та y* сiдлової точки (x*,y*) функції F(x,y) називаються оптимальними змішаними стратегіями відповідно гравців P₁ та P₂, а F(x*,y*) — ціною гри G. При цьому кажуть, що матрична гра має розв'язок у змішаних стратегіях.

Теорема 5.2. Задачі (11), (12) гравців P₁ та P₂ еквівалентні відповідно таким ЗЛП:

(15)

(16)

Теорема 5.3 (про мiнiмакс). Будь-яка матрична гра має розв'язок у змішаних стратегіях.

Доведення. За теоремою 2 для ЗЛП (15)

(18)

а для ЗЛП (16)

де області D та визначаються обмеженнями розглядуваних задач. За лемою 3 ЗЛП (15) та (16) є двоїстими. Якщо існує розв'язок однієї з пари двоїстих ЗЛП, тобто існує

то за теоремою двоїстості існує розв'язок i другої задачі, причому

Враховуючи (18) та (19), звідси маємо

а це означає, що існують оптимальні змішані стратегії гравців у розглядуваній матричній грі.

Легко бачити, що ЗЛП (15), (16) завжди мають розв'язок. Розглянемо, наприклад, задачу (15). Оскiльки x_m+1 за знаком не обмежене, то множина D не є порожньою (будь-яке x є X є допустимим розв'язком). Через те, що

величина обмежена знизу для будь-якого j=1,...,n. Звiдси випливає, що x_m+1 обмежена знизу, отже існує .

Як відомо, у матричних іграх з сiдловою точкою жодному з гравців не слід відступати від своєї оптимальної чистої стратегії за умови, що його противник дотримується своєї оптимальної чистої стратегії. Дослiдимо наслідки аналогічних дій гравців у матричній грі, що не має сiдлової точки. За теоремою про мiнiмакс (основною теоремою матричних ігор) така гра завжди має розв'язок у змішаних стратегіях.

Білет18