11.3: Зменшення домінантності

Last updated
Save as PDF

Page ID: 67055

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Іноді\(m \times n\) ігрова матриця може бути зведена до\(2 \times 2\) матриці шляхом видалення певних рядків і стовпців. Рядок можна вилучити, якщо існує інший рядок, який призведе до виплати рівного або кращого значення. Аналогічно, стовпець може бути видалений, якщо є інший стовпець, який дасть виплати рівному або кращому значенню для гравця стовпця. Рядок або стовпець, який забезпечує кращий виграш для відповідного гравця, як кажуть, домінують над рядком або стовпцем з меншим виграшним.

Приклад\(\PageIndex{1}\)

Для наступної гри визначте оптимальну стратегію як для гравця рядка, так і для гравця стовпця, і знайдіть значення гри.

\ [G=\ left [\ begin {масив} {ccc}
-2 & 6 & 4\\
-1 & -2 & -3\\
1 & 2 & 2
\ -2\ кінець {масив}\ праворуч]\ nonumber\]

Рішення

Спочатку шукаємо точку сідла і визначаємо, що жодної не існує. Далі ми намагаємося звести матрицю до\(2 \times 2\) матриці, усунувши переважаючий рядок.

Оскільки кожен запис у рядку 3 більше, ніж відповідний запис у рядку 2, рядок 3 домінує над рядком 2. Тому раціональний гравець ряду ніколи не буде грати ряд 2, і ми усуваємо ряд 2. Ми отримуємо

\ [\ left [\ begin {масив} {ccc}
-2 & 6 & 4\\
1 & 2 & -2
\ end {масив}\ праворуч]\ nonumber\]

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

Гравець стовпця ніколи не гратиме стовпець 2, тому що в ньому переважають як стовпець 1, так і стовпець 3. Тому усуваємо стовпець 2 і отримуємо змінену матрицю, M, нижче.

\ [\ mathrm {M} =\ left [\ begin {масив} {cc}
-2 & 4\
1 & -2
\ end {масив}\ справа]\ nonumber\]

Щоб знайти оптимальну стратегію як для гравця рядків, так і для гравця стовпців, ми використовуємо метод, вивчений у розділі 11.2.

Нехай стратегія гравця в рядку буде\ (\ mathrm {R} =\ left [\ begin {масив} {ll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {масив}\ справа]\), а гравець стовпця буде стратегією\ (C=\ left [\ begin {масив} {c}
c\\
1-c
\ end {масив}\ праворуч]\)

Щоб знайти оптимальну стратегію для рядового гравця, ми, по-перше, знаходимо продукт RM, як показано нижче.

\ [\ left [\ begin {масив} {lll}
\ mathrm {r} & 1-\ mathrm {r}
\ кінець {масив}\ справа]\ лівий [\ початок {масив} {cc}
-2 & 4\
1 & -2
\ кінець {масив}\ праворуч] =\ лівий [\ початок {масив} {ll}
-3 r+1 & 6 r-2
\ кінець {масив}\ праворуч]\ номер\]

Встановивши записи рівними, отримуємо

\[-3r + 1 = 6r - 2 \nonumber \]

або

\[r = 1/3 \nonumber. \nonumber \]

Тому оптимальною стратегією для програвача рядків є\ (\ left [\ begin {array} {ll}
1/ 3 & 2/3
\ end {array}\ right]\), але відносно вихідної ігрової матриці це\ (\ left [\ begin {array} {lll}
1/3 & 0 & 2/3
\ end {array}\ right]\).

Щоб знайти оптимальну стратегію для гравця колонки, ми, для початку, знаходимо наступний продукт.

\ [\ left [\ begin {масив} {cc}
-2 & 4\
1 & -2
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {
c} c\\
1-c
\ end {масив}\ праворуч] =\ left [\ begin {масив} {c}
-6\\
3 c-2
\ кінець {масив}\ праворуч]\ номер\]

Встановлюємо записи в матриці добутку рівні один одному, і отримуємо,

\[-6c + 4 = 3c - 2 \nonumber \]

або

\[c = 2/3 \nonumber. \nonumber \]

Тому оптимальною стратегією для гравець стовпців є\ (\ left [\ begin {array} {l}
2/3\\
1/3
\ end {array}\ right]\), але щодо вихідної ігрової матриці стратегія для гравця стовпця -\ (\ left [\ begin {array} {c}
2\\\
0\\
1/3
\ end {масив}\ право]\).

Щоб знайти очікуване значення V гри, у нас є два варіанти: або знайти добуток матриць R, M і C, або помножити оптимальні стратегії щодо вихідної матриці на вихідну матрицю. Вибираємо перший, і отримуємо

\ [\ begin {масив} {l}
\ mathrm {V} =\ лівий [\ begin {масив} {lll}
1/3 & 2/3
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {cc}
-2 & 4
\
1\ кінець {масив}\ праворуч]\ лівий [\ початок {масив} {l}
2/3\
1/ 3
\ end {масив}\ праворуч]\
\ mathrm {V} =\ лівий [\ початок {масив} {l}
0
\ кінець {масив}\ праворуч]
\ кінець {масив}\ nonumber\]

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

Підсумовуємо наступним чином:

Зменшення домінантності

Іноді\(m \times n\) ігрова матриця може бути зведена до\(2 \times 2\) матриці шляхом видалення переважаючих рядків і стовпців.
Рядок називається переважаючим рядком, якщо існує інший рядок, який призведе до виплати рівного або кращого значення. Це трапляється, коли існує рядок, кожен запис якого більший за відповідний запис переважаючого рядка.
Стовпець називається домінуючим стовпцем, якщо існує інший стовпець, який призведе до виплати рівного або кращого значення. Це відбувається, коли існує стовпець, кожен запис якого менший за відповідний запис переважаючого рядка.