Теорія про мінімакс. усталеність одержуваних рішень

Нехай дана ігрова матриця А={аij} та теорія про мінімакс. усталеність одержуваних рішень - student2.ru , теорія про мінімакс. усталеність одержуваних рішень - student2.ru . Причому аке=α і а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 тільки збільшує програш В).

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

Зауваження 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 і хоча б одне аkjrj, то її k-й рядок домінує над r-м рядком.

При аil≤ аih (i=1,2,…,m) і хоча б одному аilih , говорять, що 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.

Нові теорія про мінімакс. усталеність одержуваних рішень - student2.ru

  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.

Наши рекомендации