Змішане розширення матричної гри

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

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

Означення 8.4. Змішаною стратегією гравця називається повний набір ймовірностей застосування його чистих стратегій, тобто – це вектор, компонентами якого є ймовірності вибору чистих стратегій гравців.

Таким чином, якщо гравець 1 має m чистих стратегій 1,2,...,m, то його змішана стратегія x – це набір чисел x = (x₁,..., x_m), що задовольняють співвідношення

x_i ³ 0, (i = 1, m), = 1.

Аналогічно для гравця 2, що має n чистих стратегій, змішана стратегія y – це набір чисел

y = (y₁,..., y_n), y_j ³ 0, (j = 1, n), = 1.

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

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

Означення 8.5. Середній виграш гравця 1 у матричній грі з матрицею А описується у вигляді математичного сподівання його виграшів

E (A, x, y) = = x A y.

Перший гравець має на меті за рахунок зміни своїх змішаних стратегій х максимально збільшити свій середній виграш Е (А, х, y), а другий – за рахунок своїх змішаних стратегій прагне зробити Е (А, х, y) мінімальним, тобто для розв’язання гри необхідно знайти такі х і y, при яких досягається верхня ціна гри

Е (А, х, y).

Аналогічною повинна бути ситуація і для гравця 2, тобто нижня ціна гри повинна бути

Е (А, х, y).

Подібно іграм, що мають сідлові точки в чистих стратегіях, вводиться таке означення: оптимальними змішаними стратегіями гравців 1 і 2 називаються такі набори х^о і у^о, відповідно до яких задовольняються рівності

Е (А, х, y) = Е (А, х, y) = Е (А, х^о, у^о).

Величина Е (А, х^о ,у^о) при цьому називається ціною гри і позначається через символ u.

Є також й інше означення оптимальних змішаних стратегій: х^о, у^о називаються оптимальними змішаними стратегіями відповідно до гравців 1 і 2, якщо вони утворять сідлову точку:

Е (А, х, у^о) £ Е (А, х^о, у^о) £ Е (А, х^о, у)

Оптимальні змішані стратегії і ціна ігри називаються розв’язком матричної гри.

Основна теорема матричних ігор має вигляд:

Теорема (про мінімакс). Для матричної гри з будь-якою матрицею А існують рівні між собою величини

Е (А, х, y) і Е (А, х, y).

Звідси, для того щоб x * = (x *₁,…, x *_m) була оптимальною змі­шаною стратегією першого гравця для матричної гри з нульовою сумою , платіжною матрицею А та ціною гри n, необхідне та достатнє виконання нерівностей

Для другого гравця у * = (у *₁,…, y *_n) буде оптимальною змішаною стратегією, якщо

Компонентами векторів (х *, у *) є ймовірності вибору чистих стратегій гравцями в змішаній стратегії.