Платіжна матриця. Верхня і нижня ціна гри.

Розглянемо парну кінцеву гру:
Гравець А має m стратегій A1, A2.,Am.
Гравець В має n стратегій B1, B2.,Bn.
Розмірність гри m n.
В результаті вибору гравцями будь-якої пари стратегій Ai і Bj (i=1,2.m; j=1,2.n) однозначно визначається результат гри, тобто виграш гравця А aij і програш гравця В -aij.

Матриця P=(aij) (i=1,2.m; j=1,2.n), елементами якої є виграші, відповідні стратегіям Ai і Bj, називається платіжною матрицею або матрицею гри. Загальний вид матриці:

Рядки цієї таблиці відповідають стратегіям гравця А, стовпці - стратегіям гравця В.
Приклад . Гра "Пошук"
Гравець А може сховатися в одному з втечеш I або II. Гравець В шукає гравця А. Еслі знайде, то отримує від А штраф $1, якщо не знайде, то платить гравцеві А $1.
Стратегії гравця А:
А1 - гравець А ховається в притулку I;
А2 - гравець А ховається в притулку II.
Стратегії гравця В:
В1 - гравець В шукає в притулку I;
В2 - гравець В шукає в притулку II.
Якщо гравець А в притулку I і В його виявив (стратегія A1b1), то платить штраф $1 (а11=-1). Аналогічно для стратегії A2b2 а22=-

Якщо А в притулку I, а В його не виявив (стратегія A1b2), то гравець А отримує $1 (а12=1). Аналогічно для стратегії A2b1 а21=1.
Розмірність гри 22.
Платіжна матриця гра, матриця розміром 2*2:

Розглянемо гру m n з матрицею Р=(аij) розміром m n.
Визначимо якнайкращу стратегію гравця А серед стратегій A1, A2.,Am.
Вибираючи стратегію Аi, гравець А розраховує, що У вибере стратегію Вj, для якої виграш А мінімальний (гравець В шкодить А).
Позначимо - мінімальний виграш гравця А, при виборі ним стратегії Ai, для всіх можливих стратегіях В.
- мінімальне число в i-ой рядку платіжної матриці.
Серед всіх можливих виберемо максимальне:

- нижня ціна гри (максимін) - максимальний гарантований виграш гравця А.
Стратегія, відповідна максиміну називається максимінной стратегією.
Гравець В зацікавлений в тому, щоб зменшити виграш гравця А. Обираючи стратегію Вj, гравець В максимально можливий при цьому виграш гравця А. Позначимо- найбільший елемент в стовпці j. Тоді
- верхня ціна гри (мінімакс) - мінімальний гарантований виграш гравця В.
Стратегія, відповідна мінімаксу називається мінімаксною стратегією.
Принцип, що диктує гравцям вибір "обережних" мінімаксних або максимінних стратегій називається принципом мінімакса.
Знайдемо верхню і нижню ціну гри "Пошук".

Отже, гравець А може вибирати будь-яку стратегію А1 або А2, вони обидві масимінни. Нижня ціна гри рівна -1.

Будь-яка стратегія гравця В мінімаксна і верхній ціні гри рівна 1.
Якщо верхня ціна гри рівна нижній ціні гри, то - чиста ціна гри. Мінімаксні стратегії, відповідні чистій ціні гри, називаються оптимальними, а їх сукупність - оптимальним рішенням або вирішенням гри. Гравець А отримує гарантований, не залежною від стратегії гравця У виграш , а гравець В добивається мінімального гарантованого, не залежного від вибору А, програшу .
Вирішення гри стійке, якщо один з гравців дотримується оптимальної стратегії, то для іншого не може бути вигідним відхилятися від своєї оптимальної стратегії.
Пара чистих стратегій Ai Bj дає оптимальне вирішення гри тоді і тільки тоді, коли aij - максимум в своєму стовпці і мінімум в своєму рядку. Така ситуація, якщо вона існує, називається сідловою точкою.
Хай А* В* - пара чистих стратегій при яких досягається вирішення гри в завданні з седловою точкою. Введемо функцію виграшу гравця. P(Ai,bj)=aij. Тоді, з умови оптимальності в сідловій точкі виконується нерівність P(Ai,b*) P(A*,b*) P(A*,bj), яка справедлива для всіх i=1,2.m; j=1,2.n.