ТЕОРІЯ ПРО МІНІМАКС. УСТАЛЕНІСТЬ ОДЕРЖУВАНИХ РІШЕНЬ

Нехай дана ігрова матриця А={аij} та , . Причому аке= і аgh= .

Тоді аке аkh , а аghаkh => аке=аkhаgh=.

Якщо немає сідлової точки ( ¹), то <.

Якщо <, то застосування змішаних стратегій S*А, S*B повинно призвести до поліпшення в середньому, положення учасників гри, тобто А , В, чим при чистих стратегіях.

Як пов'язані А и В? Відповідь дає теорема про мінімакс.

Теорема У випадку кінцевої антагоністичної гри з повною інформацією А=В при ¹ b.

Ця теорема вказує на існування ситуації рівноваги для випадку ¹b а отже, оптимальних стратегій S*А, S*B, тобто рішення гри, що дозволяє домагатися середньоочікуваного виграшу =А=В, називаного ціною гри. Причому .

Визначення. Ті з стратегій Sia, Sjb, що входять до S*А, S*B (тобто Pia>0, Pjb>0) називаються активними стратегіями в складі S*А, S*B.

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

Доказ.Нехай JА, JB - множина i, j, таких, що P*ia>0, P*jb>0, тобто Sia, Sjb - активні стратегії, - ціна гри, при оптимальних S*А та S*B, а i - середній виграш А при стратегії S*А проти Sjb. Очевидно, що i (перехід до неоптимальної стратегії Sjb тільки збільшує програш В).

Тоді при , де , одержимо, що усі i=, тобто програш В не залежить від чистої стратегії Sjb при S*А. Аналогічний доказ при змішаній стратегії Sb. Тут очікуваний виграш А складе , тому що Sb не оптимальний, то , але , тому що тоді S*А не оптимальна. Тому . Аналогічно для В.

Зауваження 1. S*А и S*B - оптимальні для {аij}, оптимальні і для {аij+c}.

Висновок. Кожна кінцева (матрична) гра з повною інформацією має хоча б одне рішення або в чистих стратегіях (=), або в змішаних ( ¹ ), тобто будь-яка така ситуація має ситуацію рівноваги.

ЗАСОБИ ПОШУКУ ОПТИМАЛЬНИХ СТРАТЕГІЙ.

ЗАГАЛЬНІ ПІДХОДИ

Якщо в матриці А={аij} є сідлова точка, то ми маємо аpq= = . Нехай ¹ , тобто немає сідлової точки. Тоді рішення треба шукати в змішаних стратегіях SA={P1a,P2a,…,Pma}; SB={P1b,P2b,…,Pnb}. Так як m і n можуть бути великі, то треба подумати про спрощення гри.

Визначення. Якщо матриця А={аij} має властивості аkj аrj (k=1,2, …,m; j=1,2,…,n), k¹r і хоча б одне аkj>аrj, то її k-й рядок домінує над r-м рядком.

При аil аih (i=1,2,…,m) і хоча б одному аil<аih , говорять, що l-й стовпчик домінує над h - м. Очевидно сторона А вибере стратегію Sка, замість Sra, сторона B - стратегію Slb, замість Shb.

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

Приклад 3.

  S1b S2b S3b S4b 2-ий стовпчик домінує над 4-м   S1b S2b S3b 3-ий рядок домінує над 1-м
S1a S1a
S1a S2a
S1a S3a

 

  S1b S2b S3b 2-ий стовпчик домінує над 3-м   S1b S2b Гра зредуциру-вала з 3´4 до 2´2
S2a S2a
S3a S3a
                 

Іншим розповсюдженим способом спрощення ігор являється штучна заміна вихідних чистих стратегій S1a,…,Sma,S1b,…,Snb очевидними змішаними стратегіями з внесенням відповідний коректив у платіжну матрицю А.

Приклад 4. Нехай у грі припускається змішування стратегій у рівних пропорціях. Так в силу однаковості елементів перших двох стовпчиків стратегій S1b і S2b потрібно змінювати з частотою ½ (без урахування S3b і S4b).

Такою ж властивістю володіє і S3b та S4b.

Нові

  S1b S2b S3b S4b     Þ   S’1b S2b   S1a домінує над S2a   S’1b S2b
S1a S1a 3,5 S1a 3,5
S1a -7 S2a -3,5 S2a -3,5
S1a -7 -1 -1 S3a -1      

Тоді а11=3,5 - сідлова точка. Отже оптимальне рішення (S1a, S1b).

Висновок. При дослідженні будь-якої гри (m´n)

1) перевіряємо, чи є в А сідлові точки і пов'язані з ними рішення в чистих стратегіях;

2) якщо ¹ , то намагаються виявити домінуючу стратегію, а також стратегії, що призводять до однакових результатів;

3) потім переходять до формування змішаних стратегій. У результаті знаходиться спрощена гра без сідлових точок, аналог гри m´n.