2. Платіжна матриця парної гри.

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

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

стратегії			…..
			…..
			…..
.....	…..	…..	…..	…..
			…..

Приклад 12.1. Складемо платіжну матрицю для гри «пошук»: Гравець може сховатись в одному з сховищ ( 1 і 2 ); гравець шукає гравця , і якщо знаходить, то отримує штраф - 1 грош. од. від гравця , в протилежному випадку -- платить штраф 1 грош.од. гравцю .

Розв'язання. Для складання платіжної матриці слід проаналізувати поведінку кожного з гравців. Гравець може сховатись в сховищі 1 – позначимо цю стратегію через , а в сховищі 2 – стратегія .

Гравець може шукати гравця в сховищі 1 – стратегія , або в сховищі 2 – стратегія .

Якщо гравець знаходиться в сховищі 1 і там його шукає гравець , то здійснюється пара стратегій . При цьому гравець платить штраф, тобто . Аналогічно отримуємо ( ). Очевидно, що стратегії ( ) і ( ) дають гравцю виграш 1, тому . Таким чином для гри «пошук» розміром одержуємо платіжну матрицю .

3. Принцип мінімаксу.

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

Серед чисел виберемо найбільше: . Назвемо нижньою ціною гри, або максиміним виграшем (максиміном). Це гарантований виграш гравця при будь-якій стратегії гравця . Отже

Стратегія, що відповідає максиміну, називається максиміною стратегією.

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

Серед чисел виберемо найменше і назвемо верхньою ціною гри або мінімаксним виграшем (мінімаксом). Це гарантований програш гравця . Отже

Стратегія, що відповідає мінімаксу, називається мінімаксною стратегією. Принцип, що диктує гравцям вибір найбільш «обережних» мінімаксних і максиміних стратегій, називається принципом мінімаксу.

Визначимо верхню і нижню ціни гри і відповідні стратегії в прикладі 12.1, доповнивши таблицю рядком і стовпцем :

стратегії
	-1	1	-1
	1	-1	-1
	1	1

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

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

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

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

Позначимо і -- пару чистих стратегій, на яких досягається розв’язок гри в задачі з сідловою точкою. Введемо функцію виграшу першого гравця на кожній парі стратегій: . Тоді з умов оптимальності в сідловій точці виконується подвійна нерівність:

,

яка справедлива для всіх .

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

Приклад 12.2. Визначити нижню і верхню ціну гри, заданої платіжною матрицею:

Чи має гра сідлову точку?

Розв’язок. Всі розрахунки проведемо в таблиці, до якої крім матриці , введемо стовбець і рядок . Аналізуючи рядки матриці ( стратегії гравця ), заповнимо стовбець . Аналогічно по стовпцях : .

стратегії
	0,5	0,6	0,8	0,5
	0,9	0,7	0,8	0,7
	0,7	0,6	0,6	0,6
	0,9	0,7	0,8

Нижня ціна гри , а верхня ціна гри . Ці значення рівні: і досягаються на одній і тій же парі стратегій . Отже, гра має сідлову точку і ціна гри .