542. Платіжна матриця. Основна теорема теорії ігор. Принцип мінімаксу.

Маємо два гравці А і В. Результати (плата) за всіма можливими варіантами гри задаються спеціальними функціями, які залежать від стратегій гравців, як правило, у вигляді платіжної матриці. Отже, мета гравця А — максимізувати, а гравця В — мінімізувати її. Маємо матрицю А:

А={a11 a12 … a1n}

{a21 a22 … a2n}

{am1 am2 … amn}

де рядки відповідають стратегіям Аі, а стовпці — стратегіям Bj.

Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці aij — це виграш гравця А, якщо він вибрав стратегію Ai, а гравець В — стратегію Bj.

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

Нехай гравець А вибрав стратегію Ai, тоді у найгіршому разі він отримає виграш, що дорівнює min aij, тобто навіть тоді, якщо гравець В і знав би стратегію гравця А. Передбачаючи таку можливість, гравець А має вибрати таку стратегію, щоб максимізувати свій мінімальний виграш, тобто a=maxmin aij

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

Гравець В, який програє суми у розмірі елементів платіжної матриці, навпаки має вибрати стратегію, що мінімізує його максимально можливий програш за всіма варіантами дій гравця А. Стратегія гравця В позначається через Вj0 і називається мінімакс­ною, а величина його програшу — верхньою ціною гри, тобто b=minmax aij

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

Теорема (основна теорема теорії ігор). Кожна скінченна гра має, принаймні, один розв’язок, можливий в області змішаних стратегій.