11.2: Нестрого визначені ігри
- Page ID
- 67080
У цьому розділі ми вивчаємо ігри, які не мають сідлових очок. Це означає, що ці ігри не володіють чистою стратегією. Ми називаємо ці ігри нестрого визначеними іграми. Якщо гра грається лише один раз, це не матиме ніякої різниці, який хід зроблений. Однак, якщо гра грається неодноразово, може бути розроблена змішана стратегія, що складається з чергування випадкових ходів.
Розглянемо наступний приклад.
Припустимо, Роберт і Керол вирішили зіграти в гру, використовуючи копійки і чверть. При заданому сигналі вони одночасно показують одну з двох монет. Якщо монети збігаються, Роберт отримує обидві монети, але якщо вони не збігаються, Керол отримує обидві монети. Визначте, чи гра строго визначена.
Рішення
Матрицю виплат для Роберта записуємо наступним чином:
Щоб визначити, чи строго визначена гра, шукаємо сідлову точку. Знову ж таки, ми розміщуємо зірочку поруч з мінімальним значенням у кожному рядку, і поле навколо максимального значення в кожному стовпці. Ми отримуємо
Оскільки немає запису, який має і зірочку, і коробку, гра не має сідлової точки, і, таким чином, вона нестрого визначена.
Ми хочемо розробити стратегію для Роберта. Якщо Роберт послідовно покаже копійки, наприклад, Керол побачить закономірність і почне показувати чверть, а Роберт програє. І навпаки, якщо Керол неодноразово покаже чверть, Роберт почне показувати чверть, що призведе до втрати Керол. Таким чином, хороша стратегія полягає в тому, щоб скинути опонента, показуючи копійки деякі рази і показуючи чверть інших разів. Перш ніж розробити оптимальну стратегію для кожного гравця, розглянемо довільну стратегію для кожного і визначимо відповідні виграші.
Припустимо\(\PageIndex{1}\), у прикладі Роберт вирішує показати копійки з ймовірністю .20 і чверть з ймовірністю .80, а Керол вирішує показати копійки з ймовірністю .70 і чверть з ймовірністю .30. Яка очікувана виплата для Роберта?
Рішення
Нехай R позначає стратегію Роберта, а C позначає стратегію Керол.
Оскільки Роберт - гравець рядків, а Керол - гравець стовпців, їх стратегії написані наступним чином:
\ [\ mathrm {R} =\ left [\ begin {масив} {ll}
.20 & .80
\ end {масив}\ право]\ текст {і} C =\ left [\ begin {масив} {l}
.70\\
.30
\ end {масив}\ праворуч]\ nonumber. \ номер\]
Щоб знайти очікуваний виграш, скористаємося наступними міркуваннями.
Оскільки Роберт вирішує відтворити рядок 1 з ймовірністю .20, а Керол вирішує відтворити стовпець 1 з ймовірністю 0,70, рядок переміщення 1, стовпець 1 буде обраний з (.20) (.70) = .14 ймовірності. Той факт, що цей крок має винагороду в 10 центів для Роберта, очікуваний виграш Роберта за цей крок становить (.14) (.10) = .014 центів. Аналогічно, ми обчислюємо очікувані виплати Роберта для інших випадків. У таблиці нижче перераховані очікувані виплат за всіма чотирма випадками.
| Переміщення | Імовірність | Виплата | Очікуваний виграш |
|---|---|---|---|
| Рядок 1, Стовпець 1 | (2.0) (7.0) = 1,4 | 10 центів | 1,4 цента |
| Рядок 1, стовпець 2 | (2.0) (3.0) = 0,06 | -10 центів | -.6 центів |
| Рядок 2, Стовпець 1 | (8.0) (7.0) = 5.6 | -25 центів | -14 центів |
| Рядок 2, стовпець 2 | (8.0) (.30) = 2.4 | 25 центів | 6,0 центів |
| Підсумки | 1 | -7,2 цента |
Наведена вище таблиця показує, що якщо Роберт грає в гру зі стратегією\ (\ mathrm {R} =\ left [\ begin {array} {ll}
.20 & .80
\ end {масив}\ справа]\) і Керол грає зі стратегією\ (\ mathrm {C} =\ left [\ begin {array} {l}
.70\
.30
\ end {array}\ право]\), Роберт може розраховувати на втрату 7.2 центів за кожну гру.
Як варіант, якщо ми називаємо ігрову матрицю G, то очікуваний виграш для гравця рядків можна визначити множенням матриць R, G і C. Таким чином, очікувана виплата P для Роберта виглядає наступним чином:
\ [\ begin {масив} {l}
\ mathrm {P} =\ mathrm {RGC}\
\ mathrm {P} =\ лівий [\ begin {масив} {cc}
.20 & .80
\ end {масив}\ вправо]\ лівий [\ почати {масив} {cc}
10\\
-25 & 25
\ кінець {масив}\ праворуч]\ лівий [{масив} {c}
.70\\
.30
\ end {масив}\ право]\
\ mathrm {P} =-7.2\:\ mathrm {центи}
\ кінець {масив}\ nonumber\]
яка така ж, як і отримана з таблиці.
Для наступної ігрової матриці G визначте оптимальну стратегію як для гравця рядка, так і для гравця стовпця, і знайдіть значення гри.
\ [G=\ left [\ begin {масив} {cc}
1 & -2\\
-3 & 4
\ end {масив}\ праворуч]\ nonumber\]
Рішення
Припустимо, що гравець рядків використовує стратегію\ (\ mathrm {R} =\ left [\ begin {array} {ll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {array}\ right]\). Тепер, якщо гравець стовпця грає стовпець 1, очікуваний виграш P для гравця рядка є
\[\mathrm{P}(r) = 1(r) + (-3)(1 - r) = 4r - 3. \nonumber \]
Це також можна обчислити наступним чином:
\ [\ mathrm {P} (r) =\ left [\ begin {масив} {ll}
r & 1-r
\ end {масив}\ справа]\ лівий [\ begin {масив} {c}
1\
\
-3\ кінець {масив}\ праворуч]\ текст {або} 4 r-3\ nonumber\]
Якщо гравець рядка відтворює стратегію\ (\ left [\ begin {array} {ll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {array}\ right]\), а гравець стовпця відтворює стовпець 2, очікувана виплата P для гравця рядків буде
\ [P (r) =\ лівий [\ begin {масив} {ll}
r & 1-r
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
-2\\
4
\ end {масив}\ праворуч] =-6 r+4\ nonumber\]
У нас є два рівняння:\(\mathrm{P}(r) = 4r - 3\) і\(\mathrm{P}(r) = -6r + 4\)
Гравець рядка намагається покращити свій найгірший сценарій, і це відбувається лише тоді, коли дві лінії перетинаються. Будь-яка точка, крім точки перетину, не призведе до оптимальної стратегії, оскільки одне з очікувань не буде.
Розв'язуючи для\(r\) алгебраїчно, отримуємо
\ [\ begin {масив} {c}
4 р-3 = -6 r+4\\ r
= 7/10
\ кінець {масив}\ nonumber\]
Тому оптимальною стратегією для програвача рядків є\ (\ left [\ begin {array} {ll}
.7 & .3
\ end {array}\ right]\).
Крім того, ми можемо знайти оптимальну стратегію для гравця рядків, спочатку помноживши матрицю рядків на матрицю гри, як показано нижче.
\ [\ left [\ begin {масив} {ccc}
r & 1-r
\ end {масив}\ праворуч]\ лівий [\ begin {масив} {cc}
1 & -2\\
-3 & 4
\ end {масив}\ праворуч] =\ left [\ begin {масив} {cc}
4 r-3 & -6 r+4
\ кінець {масив}\ праворуч]\ nonumber\]
А потім за допомогою прирівнювання двох записів в матриці добутку. Знову отримуємо\(r = .7\), яка дає нам оптимальну стратегію\ (\ left [\ begin {array} {ll}
.7 & .3
\ end {array}\ right]\).
Ми використовуємо ту ж техніку, щоб знайти оптимальну стратегію для гравця колонки. Припустимо, що оптимальна стратегія гравця стовпця представлена\ (\ left [\ begin {array} {
c} c\\
1-c
\ end {array}\ right]\). Ми, по-перше, множимо матрицю гри на матрицю стовпців, як показано нижче.
\ [\ left [\ begin {масив} {cc}
1 & -2\\
-3 & 4
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
c\
1-c
\ end {масив}\ праворуч] =\ left [\ begin {масив} {c}
3 c-2\\
-7 c+4
\ end {масив}\ праворуч]\ номер\]
А потім прирівняти записи в матриці добутку. Ми отримуємо
\ [\ begin {масив} {l}
3 c-2 = -7 c+4\\
c=.6
\ кінець {масив}\ nonumber\]
Тому оптимальною стратегією гравця є\ (\ left [\ begin {array} {l}
.6\\
.4
\ end {array}\ right]\).
Щоб знайти очікуване значення, V, гри, знаходимо добуток матриць R, G і C.
\ [\ begin {масив} {l}
\ mathrm {V} =\ лівий [\ begin {масив} {ll}
.7 & .3
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {cc}
1 & -2\\
-3 & 4
\ end {масив}\ праворуч]\ left [\ begin {масив} {l}
.6\\
.4
\ end {масив}\ право]\
\ mathrm {V} =-2
\ end {масив}\ nonumber\]
Тобто, якщо обидва гравці грають свої оптимальні стратегії, гравець рядка може розраховувати на втрату 2 одиниці за кожну гру.
Для гри в\(\PageIndex{1}\) прикладі визначте оптимальну стратегію як для Роберта, так і для Керол, і знайдіть значення гри.
Рішення
Оскільки ми вже визначили, що гра нестрого визначена, переходимо до визначення оптимальної стратегії гри. Переписуємо матрицю гри.
\ [G=\ left [\ begin {масив} {cc}
10 & -10\\
-25 & 25
\ end {масив}\ праворуч]\ nonumber\]
Нехай\ (\ mathrm {R} =\ left [\ begin {масив} {ll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {масив}\ справа]\) буде стратегією Роберта, і\ (C=\ left [\ begin {масив} {
c}\
1-c
\ end {масив}\ праворуч]\) буде стратегією Керол.
Щоб знайти оптимальну стратегію для Роберта, ми, по-перше, знаходимо продукт RG, як показано нижче.
\ [\ left [\ begin {масив} {ccc}
\ mathrm {r} & 1-\ mathrm {r}
\ кінець {масив}\ справа]\ лівий [\ початок {масив} {cc}
10\\
-25 & 25
\ кінець {масив}\ справа] =\ лівий [\ початок {масив} {масив} {cc}
35\ mathrm {r} -25 & -35\ матрма {r} +25
\ end {масив}\ право]\ nonumber\]
Встановивши записи рівними, отримуємо
\[35r - 25 = -35r + 25 \nonumber \]
або\[ r = 5/7. \nonumber \]
Тому оптимальною стратегією для Роберта є\ [\ left [\ begin {array} {ll}
5/7 & 2/7
\ end {array}\ right]. \ номер\]
Щоб знайти оптимальну стратегію для Керол, ми, по-перше, знаходимо наступний продукт.
\ [\ left [\ begin {масив} {cc}
10 & -10\\
-25 & 25
\ кінець {масив}\ праворуч]\ лівий [\ початок {масив} {
c} c\
1-c
\ end {масив}\ право] =\ лівий [\ почати {масив} {c}
20 c+10\
-50 c+25
\ end {масив}\ праворуч]\ nonumber\]
Тепер ми встановлюємо записи рівними один одному, і отримуємо,
\[20c - 10 = -50c + 25 \nonumber \]
або\[c = 1/2 \nonumber \]
Тому оптимальною стратегією для Керол є\ [\ left [\ begin {array} {l}
1/2\
1/2
\ end {array}\ right]\ nonumber\].
Щоб знайти очікуване значення, V, гри, знаходимо продукт RGC.
\ [\ почати {вирівняний}
\ mathrm {V} &=\ лівий [\ begin {масив} {cc}
5/7 & 2/7
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив}
{cc} 10\
\
-25 & 25\ кінець {масив}\ праворуч [\ почати {масив} {c}
1\\
1/2
\ end {масив}\ праворуч]\\
&=\ left [\ begin {масив} {c}
0
\ end {масив}\ праворуч]
\ кінець {вирівняний}\ nonumber\]
Якщо обидва гравці грають свою оптимальну стратегію, значення гри дорівнює нулю. У такому випадку гра називається справедливою.