Принцип гарантованого результату
Так як антагоністичні ігри володіють тієї властивістю, що виграш одного (А) дорівнює програшу іншого (В), то всі необхідні дані можна помістити в таблицю (матрицю). Елементи матриці, числа aij. Така матриця - це нормальна форма подання ігри і називається вона платіжною (ігровою) матрицею, aij - виграш (програш) гравців. Гру, що представлена матрицею, називають грою m´n.
Табл.1.1
В А | S1b | S2b | - - - | Snb |
S1a | a11 | a12 | - - - | a1n |
- - - - | ||||
Sma | am1 | am2 | - - - | amn |
Нехай задана антагоністична гра в нормальній формі, тобто матрицею табл.1.1.
Знайдемо оптимальну стратегію гравців.
Очевидно, що для А при використанні стратегії S1а гарантованим виграшем буде найменше з a11, a12,..., a1n, тобто a1. Кращого результату, при правильній стратегії В, очікувати не доводиться.
Таким же чином А може розраховувати при виборі стратегії S2a, на min {a21,..., a2n}=a2, тобто у випадку стратегії Ska на min {akj}=a k і т. і.
Найкращої з всіх стратегій для А буде та, для якої a k - max, тобто виграш А ((гарантований) a =max a k =max min {akj}
1<k<m 1<k<m 1<j<n
Така стратегія називається максимінною.
Якщо А буде дотримуватись максимінної стратегії, то поза залежністю від стратегії В він виграє не менше a.
Тому a - це нижня ціна гри або максимінний виграш.
Аналогічне міркування для В, оскільки йдеться про програші сторони А, так як в антагоністичній грі ПВ(Ukj)=-ПА(Ukj)=-akj. Тоді при стратегії Skb це найкращий показник. Вj=max{akj} =>В=minВj= min max akj
1<k<m 1<j<m 1<j<n 1<k<m
- де В - min програш з усіх max. Така стратегія B називається мінімаксною, а В - верхньою ціною гри або мінімаксним програшем. Це результат, що не залежить від поведінки А.
В проведеному аналізі кожна із сторін була орієнтована на гіршу, з її точки зору ситуацію, а після цього з всіх гірших вибиралася найкраща. Цей принцип - принцип гарантованого результату (або принцип мінімаксу). Він припускає відсутність ризику.
ПРОБЛЕМА РІВНОВАГИ В ГРІ, ЧИСТІ
І ЗМІШАНІ СТРАТЕГІЇ
Якщо a=b, то в платіжній матриці присутній елемент apq, який мінімальний в р - рядку і max в q- стовпці і apq= a = b.
Приклад такої матриці
-22 | -7 | -8 | |||
a23=8=apq | |||||
-9 | -13 | ||||
-5 | -3 |
Очевидно, що елемент apq являє собою сідлову точку, що поєднує в собі і властивості т. min (для однієї перспектної) і точку max для іншої.
Такі ігри називаються іграми з сідловою точкою, мал.1.
![]() | Мал.1. |
Положення, при якому немає сенсу міняти стратегію жодної з сторін, називається ситуацією рівноваги. В іграх з сідловою точкою така ситуація виникає, якщо А та В використають стратегії Spa і Sqb, що називаються чистими. apq=a=b називається чистою ціною гри, а стратегії Spa і Sqb - оптимальними.
Чисті стратегії застосовуються, коли А та В володіють відомостями про дії один іншого і про їх результати. Якщо такої інформації немає, то принцип рівноваги порушується і гра ведеться безсистемно, тобто наосліп. Тому треба розрізняти ігри з повною інформацією, коли будь-який учасник знає всю передісторію ігри та ігри з неповною інформацією, в яких знання передісторії обмежене (наприклад, можливістю приховати від супротивника хід).
Ми будемо розглядати ігри з повною інформацією та з однією сідловою точкою, бо за наявності двох сідлових точок apq і azt, можна показати, що apq=azt.
Хоча на практиці найбільш розповсюджений випадок, коли платіжна матриця взагалі не має сідлової точки та a ¹ b.
Якщо в гру привноситься елемент випадку, тобто стратегія Sia буде обрана з ймовірністю Pia, то можна говорити про розподіл ймовірності на множині стратегій сторони А, причому .
А самий розподіл {P1a, P2a,…,Pma}=SA називається змішаною стратегією, якою володіє А в даній грі.
Аналогічно для B вводиться змішана стратегія SB={P1b,P2b,…,Pnb}, тобто деякий розподіл.
Чисті стратегії являються окремим випадком змішаних, наприклад, стратегію SPA можна задати SA={0, …,0,1, …,0}
При виборі змішаних стратегій зберігається принцип min max.
Нехай {SА} - множина змішаних стратегій А, а {SВ} - множина змішаних стратегій В. Тоді середня величина (мат. сподівання) платежу:
(4.1)
Це виграш А, отже програш В.
Сторона А повинна орієнтуватися на гірше (принцип гарантованості результату). Тоді - оптимальна стратегія Sa. Аналогічно
- оптимальна стратегія Sb. Але такі рішення тільки в простих випадках.