2.2: Стратегії, що переважають
- Page ID
- 65734
Нагадаємо, що в грі з нульовою сумою ми знаємо, що виграш одного гравця - це програш іншого гравця. Крім того, ми знаємо, що можемо переписати будь-яку гру з нульовою сумою, щоб виплати гравця були у формі\((a, -a)\text{.}\) Примітка, це працює, навіть якщо\(a\) є негативним; у цьому випадку\(-a\) позитивний.
Розглянемо гру з нульовою сумою з матрицею виплат в табл\(2.2.1\). Зауважте, що для простоти наша матриця виплат містить лише виплати, а не назви стратегій; але Гравець 1 все ще вибирає рядок, а Гравець 2 все одно вибирає стовпець.
| Таблиця\(2.2.1\): Матриця виплат на прикладі\(2.2.1\) | ||
|---|---|---|
| \ (2.2.1\): Матриця виплат, наприклад\(2.2.1\) «> | Гравець 2 | |
| \ (2.2.1\): Матриця виплат, наприклад\(2.2.1\) "RowSpan="2">Гравець 1 | \((1, -1)\) | \((-0, 0)\) |
| \((-1, 1)\) | \((-2, 2)\) | |
Якщо ми знаємо, що граємо в гру з нульовою сумою, то використання впорядкованих пар здається дещо зайвим: якщо гравець 1 виграє\(1\), то ми знаємо, що гравець 2 повинен програти\(1\) (виграти\(-1\)). Таким чином, якщо ми ЗНАЄМО, що граємо в гру з нульовою сумою, ми можемо спростити наші позначення, просто використовуючи виграші гравця 1. Наведену вище матрицю в таблиці\(2.2.2\) можна спростити як в табл\(2.2.2\).
| Таблиця\(2.2.2\): Матриця виплат, наприклад, з\(2.2.1\) використанням лише виграшів гравця 1. | ||
|---|---|---|
| \ (2.2.2\): Матриця виплат, наприклад, з\(2.2.1\) використанням виграшів лише гравця 1. «> | Гравець 2 | |
| \ (2.2.2\): Матриця виплат, наприклад, з\(2.2.1\) використанням виграшів лише гравця 1.» RowSpan="2">Гравець 1 | \(1\) | \(0\) |
| \(-1\) | \(-2\) | |
При спрощенні майте на увазі кілька речей:
- Ви ПОВИННІ знати, що гра нульова сума.
- Якщо не вказано інше, виплати представляють собою виграші гравця 1.
- Ви завжди можете дати подібну матрицю, що представляє виграші гравця 2. Однак через (2) слід вказати, що матриця для Player 2. Наприклад, матриця виплат гравця 2 буде вказана таблицею\(2.2.3\).
Таблиця\(2.2.3\): Матриця виплат, наприклад, з\(2.2.1\) використанням лише виграшів гравця 2. \ (2.2.3\): Матриця виплат, наприклад, з\(2.2.1\) використанням виграшів лише гравця 2. «> Гравець 2 \ (2.2.3\): Матриця виплат, наприклад, з\(2.2.1\) використанням виграшів лише гравця 2.» RowSpan="2">Гравець 1 \(-1\) \(0\) \(1\) \(2\) - Обидва гравці можуть приймати стратегічні рішення, враховуючи лише матрицю виплат гравця 1. (Чому?) Просто перевірити це, дивлячись лише на матрицю в таблиці 2.2.3 визначити, яку стратегію повинен вибрати кожен гравець.
Таблиця\(2.2.4\): Виплати гравця 1 у прикладі\(2.2.1\). \ (2.2.4\): Виплати гравця 1 у прикладі\(2.2.1\). «> Гравець 2 \ (2.2.4\): Виплати гравця 1 у прикладі\(2.2.1\).» RowSpan = «2">Гравець 1 \(1\) \(0\) \(-1\) \(-2\)
У цьому останньому прикладі повинно бути зрозуміло, що Гравець 1 шукає рядки, які дають їй найбільший виграш. У цьому немає нічого нового. Однак гравець 2 тепер шукає стовпці, які дають гравцеві 1 НАЙМЕНШИЙ виграш. (Чому?)
Тепер, коли ми спростили наші позначення для ігор з нульовою сумою, давайте спробуємо знайти спосіб визначити найкращу стратегію для кожного гравця.
Розглянемо гру з нульовою сумою, наведену в табл\(2.2.5\).
| Таблиця\(2.2.5\): Матриця виплат, наприклад\(2.2.2\). | |||
|---|---|---|---|
| \ (2.2.5\): Матриця виплат, наприклад\(2.2.2\). «> | Гравець 2 | ||
| \ (2.2.5\): Матриця виплат, наприклад\(2.2.2\).» RowSpan="2">Гравець 1 | \(1\) | \(0\) | \(2\) |
| \(-1\) | \(-2\) | \(2\) | |
Визначте, який рядок Гравець 1 повинен вибрати. Чи є ситуація, в якій Гравець 1 вибрав би інший рядок?
Розглянемо гру з нульовою сумою, наведену в табл\(2.2.6\).
| Таблиця\(2.2.6\): Матриця виплат, наприклад\(2.2.3\). | |||
|---|---|---|---|
| \ (2.2.6\): Матриця виплат, наприклад\(2.2.3\). «> | Гравець 2 | ||
| \ (2.2.6\): Матриця виплат, наприклад\(2.2.3\).» RowSpan = «2">Гравець 1 | \(1\) | \(0\) | \(2\) |
| \(-1\) | \(-2\) | \(3\) | |
Визначте, який рядок Гравець 1 повинен вибрати. Чи є ситуація, в якій Гравець 1 вибрав би інший рядок?
У прикладі\(2.2.2\), незалежно від того, що робить Гравець 2, гравець 1 завжди обирає рядок 1, оскільки кожен виграш у рядку 1 більше або дорівнює відповідному виграшу в рядку 2 (\(1\ge -1\text{,}\)\(0\ge -2\text{,}\)\(2\ge 2\)). У\(2.2.3\) прикладі це не так: якщо гравець 2 повинен був вибрати Стовпець 3, то гравець 1 віддасть перевагу рядку 2. У прикладі\(2.2.2\) ми б сказали, що рядок 1 домінує над рядком 2.
Стратегія\(X\) домінує над стратегією,\(Y\) якщо кожен запис для\(X\) більше або дорівнює відповідному запису для\(Y\text{.}\) У цьому випадку, ми говоримо, що\(Y\) переважає\(X\text{.}\)
Якщо стратегія\(X\) домінує над стратегією,\(Y\text{,}\) ми можемо написати\(X\succ Y\text{.}\)
У математичних позначеннях, нехай\(a_{ik}\) буде значення в\(i^{ \text{th}}\) рядку і\(k^{ \text{th}}\) стовпці. Аналогічно\(a_{jk}\) вказується значення в\(j^{ \text{th}}\) рядку і\(k^{ th}\) стовпці. \(i^{ \text{th}}\)Рядок домінує над\(j^{ \text{th}}\) рядком, якщо\(a_{ik}\ge a_{jk}\) для всіх\(k\text{,}\) і принаймні\(a_{ik}> a_{jk}\) для одного.\(k\text{.}\)
Це визначення можна використовувати і для Player 2: ми вважаємо стовпці замість рядків. Якщо ми дивимося на виграші гравця 1, то Гравець 2 віддає перевагу меншим виграшам. Таким чином, один стовпець\(X\) домінує над іншим стовпцем\(X\),\(Y\) якщо всі записи в менші або рівні відповідних записів у\(Y\text{.}\)
Ось чудова річ: ми завжди можемо усунути домінуючі стратегії! (Чому?) Таким чином, в\(2.2.2\) прикладі ми можемо усунути рядок 2, як на рис\(2.2.1\).
Тепер легко побачити, що повинен робити Player 2.
У прикладі\(2.2.3\) ми не можемо усунути рядок 2, оскільки в ньому не переважає рядок 1. Однак повинно бути зрозуміло, що стовпець 2 домінує у стовпці 3 (пам'ятайте, гравець 2 віддає перевагу меншим значенням). Таким чином, ми можемо усунути стовпець 3, як на малюнку\(2.2.2\).
ПІСЛЯ усунення стовпця 3, рядок 1 домінує над рядком 2. Тепер на малюнку\(2.2.3\) ми можемо усунути рядок 2.
Знову ж таки, тепер легко визначити, що повинен робити кожен гравець.
Перевірте, чи пари стратегій, які ми визначили в\(2.2.2\) Example та\(2.2.3\) Example, насправді є парами рівноваги.
Тепер озирніться назад на приклади виборів з розділу 2.1.1 та застосуйте процес усунення домінуючих стратегій.
Використовуйте ідею усунення домінуючих стратегій, щоб визначити, що повинен робити кожен гравець у прикладах Арнольда/Бейнбріджа в таблиці\(2.1.4\)\(2.1.5\), таблиці та таблиці\(2.1.6\). Чи отримуєте ви ті ж стратегії пари, які ви визначили у відповідних вправах (вправи\(2.1.1\), вправи\(2.1.2\), вправи\(2.1.3\))?
Наступні три вправи надають більше практики у використанні домінуючих стратегій для пошуку пар рівноваги.
Використовуйте ідею усунення домінуючих стратегій для визначення будь-яких пар рівноваги в грі з нульовою сумою, наведеної в табл\(2.2.7\). Зверніть увагу, оскільки це гра з нульовою сумою, нам потрібно лише показувати виграші гравця 1. Поясніть всі кроки у вашому рішенні. Якщо ви не в змозі знайти рівноважну пару, поясніть, що йде не так.
| Таблиця\(2.2.7\): Матриця виплат для вправ\(2.2.3\). | |||||
|---|---|---|---|---|---|
| \ (2.2.7\): Матриця виплат для вправи\(2.2.3\). «> | Гравець 2 | ||||
| \ (2.2.7\): Матриця виплат для вправ\(2.2.3\).» RowSpan = «5">Гравець 1 | Ш | Х | У | Z | |
| A | \(1\) | \(0\) | \(0\) | \(10\) | |
| Б | \(-1\) | \(0\) | \(-2\) | \(9\) | |
| C | \(1\) | \(1\) | \(1\) | \(8\) | |
| D | \(-2\) | \(0\) | \(0\) | \(7\) | |
Визначте будь-які рівноважні пари в грі з нульовою сумою, наведеної в табл\(2.2.8\). Поясніть всі кроки у вашому рішенні. Якщо ви не в змозі знайти рівноважну пару, поясніть, що йде не так.
| Таблиця\(2.2.8\): Матриця виплат для вправ\(2.2.4\). | |||||
|---|---|---|---|---|---|
| \ (2.2.8\): Матриця виплат для вправи\(2.2.4\). «> | Гравець 2 | ||||
| \ (2.2.8\): Матриця виплат для вправ\(2.2.4\).» RowSpan = «5">Гравець 1 | Ш | Х | У | Z | |
| A | \(1\) | \(2\) | \(3\) | \(4\) | |
| Б | \(0\) | \(-1\) | \(-0\) | \(5\) | |
| C | \(-1\) | \(3\) | \(2\) | \(4\) | |
| D | \(0\) | \(1\) | \(-1\) | \(1\) | |
Визначте будь-які рівноважні пари в грі з нульовою сумою, наведеної в табл\(2.2.9\). Поясніть всі кроки у вашому рішенні. Якщо ви не в змозі знайти рівноважну пару, поясніть, що йде не так.
| Таблиця\(2.2.9\): Матриця виплат для вправ\(2.2.5\). | |||||
|---|---|---|---|---|---|
| \ (2.2.9\): Матриця виплат для вправи\(2.2.5\). «> | Гравець 2 | ||||
| \ (2.2.9\): Матриця виплат для вправ\(2.2.5\).» RowSpan = «5">Гравець 1 | Ш | Х | У | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| Б | \(1\) | \(-2\) | \(-3\) | \(0\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(15\) | |
Визначте будь-які рівноважні пари в грі з нульовою сумою, наведеної в табл\(2.2.10\). Поясніть всі кроки у вашому рішенні. Якщо ви не в змозі знайти рівноважну пару, поясніть, що йде не так.
| Таблиця\(2.2.10\): Матриця виплат для вправ\(2.2.6\). | |||||
|---|---|---|---|---|---|
| \ (2.2.10\): Матриця виплат для вправи\(2.2.6\). «> | Гравець 2 | ||||
| \ (2.2.10\): Матриця виплат для вправ\(2.2.6\).» rowspan = «5">Гравець 1 | Ш | Х | У | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| Б | \(1\) | \(-2\) | \(-5\) | \(-3\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(8\) | |
Швидше за все, у вас виникли проблеми з визначенням рівноваги пари для гри в вправи\(2.2.10\). Чи означає це, що немає рівноважної пари? Не обов'язково, але ми застрягли, якщо намагаємося використовувати лише ідею усунення домінуючих стратегій. Тому нам потрібен новий метод.
Ми можемо вважати наш наступний метод «найгіршим сценарієм» або «надзвичайно оборонною грою». Ідея полягає в тому, що ми хочемо припустити, що наш суперник - найкращий гравець, який коли-небудь жив. Насправді, ми можемо припустити, що наш опонент телепатичний. Тож що б ми не робили, наш опонент завжди буде здогадуватися, що ми збираємося вибрати.
Припустимо, що ви гравець 1, і ви граєте проти цього «нескінченно розумного» гравця 2. Розглянемо гру в табл\(2.2.7\). Якщо ви виберете рядок A, що зробить Гравець 2? Гравець 2 обере стовпець X або Y. Спробуйте це для кожного з рядків. Який ряд ваш найкращий вибір? Якщо ви виберете A, ви отримаєте,\(0\text{;}\) якщо ви виберете B, ви отримаєте,\(-2\text{;}\) якщо ви виберете C, ви отримаєте,\(1\text{;}\) і якщо ви виберете D ви отримаєте\(-2\text{.}\) Таким чином, ваш найкращий вибір - вибрати C і отримати\(1\text{.}\) Тепер припустимо, що ви гравець 2, а гравець 1 «нескінченно розумний». Яка колонка ваш найкращий вибір? Якщо ви виберете W, гравець 1 отримає\(1\) (ви отримаєте\(-1\)); якщо ви виберете X, гравець 1 отримає,\(1\text{;}\) якщо ви виберете Y, гравець 1 отримає,\(1\text{;}\) і якщо ви виберете Z, ви отримаєте\(10\text{.}\) Таким чином, ви можете вибрати W, X або Y (так як ви хочете, щоб гравець 1, щоб виграти найменше) і отримати\(-1\text{.}\)
Використовуючи метод, описаний у прикладі\(2.2.4\), визначте, що повинен робити кожен гравець в грі в таблиці\(2.2.8\).
Використовуючи метод, описаний у прикладі\(2.2.4\), визначте, що повинен робити кожен гравець в грі в таблиці\(2.2.9\).
Пропрацювавши кілька прикладів, чи можете ви описати більш загалом процес, який використовується в Example\(2.2.4\)? Що гравець 1 шукає в кожному рядку? Тоді як вона вибирає, який ряд грати? Що гравець 2 шукає в кожній колонці? Як він вибирає, в яку колонку грати?
Узагальнити метод, описаний у прикладі\(2.2.4\). Іншими словами, дайте загальне правило, як Гравець 1 повинен визначити свій найкращий хід. Зробіть те ж саме для гравця 2.
Що ви помічаєте щодо використання цього методу на іграх у таблицях\(2.2.7\)\(2.2.8\), таблицях та таблицях\(2.2.9\)? Чи є рішення рівноважною парою?
Тепер спробуйте цей метод на невловимою матриці виплат в табл\(2.2.10\). Що повинен робити кожен гравець? Як ви думаєте, ми отримуємо рівноважну пару? Поясніть.
Стратегії, які ми знайшли за допомогою вищевказаного методу, мають більш офіційну назву. Стратегія гравця 1 називається стратегією maximin. Гравець 1 максимізує мінімальні значення з кожного рядка. Стратегія гравця 2 називається стратегією minimax. Гравець 2 мінімізує максимальні значення з кожного стовпця. Зверніть увагу, ми можемо знайти максимальні та мінімаксні стратегії для будь-якої гри з нульовою сумою. Але чи завжди наші гравці хочуть використовувати ці стратегії? Чи завжди вони призведуть до рівноважної пари? Наступні п'ять вправ досліджують ці питання.
Розглянемо ще одну ігрову матрицю, наведену в табл\(2.2.11\). Поясніть, чому ви не можете використовувати домінуючі стратегії, щоб знайти рівноважну пару. Як ви думаєте, існує рівноважна пара для цієї гри (чому чи чому б і ні)?
| Таблиця\(2.2.11\): Матриця виплат для вправ\(2.2.12\). | |||||
|---|---|---|---|---|---|
| \ (2.2.11\): Матриця виплат для вправи\(2.2.12\). «> | Гравець 2 | ||||
| \ (2.2.11\): Матриця виплат для вправ\(2.2.12\).» rowspan = «5">Гравець 1 | Ш | Х | У | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| Б | \(1\) | \(2\) | \(-3\) | \(0\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(15\) | |
Якщо обидва гравці використовують стратегію максимін/мінімакс, який результат гри в таблиці\(2.2.11\)?
У грі в таблиці\(2.2.11\), якщо опонент гравця 1 може здогадатися, що гравець 1 вирішить використовувати стратегію максиміну, чи краще гравцеві 1 не використовувати стратегію максиміну?
Припустимо, обидва гравці спочатку вирішують використовувати стратегію minimax/maximin в грі в таблиці\(2.2.11\). Чи краще гравцеві 1 вибрати іншу стратегію? Якщо гравець 2 вгадує зміни, чи краще гравцеві 2 змінювати стратегії? Продовжуйте цей рядок міркування протягом декількох ітерацій. Які стратегії вибирає кожен з гравців? Принаймні одному гравцеві завжди краще перемикати стратегії? Чи можна зробити висновок, що стратегія максимін/мінімакс не призводить до рівноважної пари?
Порівняйте свої відповіді в розділі «Вправа»\(2.2.15\) з тим, що відбувається у Вправи\(2.2.3\)\(2.2.4\), Вправи та Вправи\(2.2.5\). Чи можете ви визначити будь-які ключові відмінності між іграми у Вправи\(2.2.15\) та вправи\(2.2.3\)\(2.2.4\), вправи та вправи\(2.2.5\).
Враховуючи матричну гру з нульовою сумою, ми можемо знайти пари рівноваги (якщо вони існують) методом «вгадай і перевіряй», усуваючи домінуючі стратегії та шукаючи стратегії minimax/maximin. Ви повинні бути в змозі застосувати всі три методи і думати про те, який метод може бути найбільш підходящим для даної матричної гри. Наприклад, хоча «вгадай і перевіряй» завжди повинен знаходити точку рівноваги, якщо вона існує, це може бути дуже нудно застосовувати до дійсно великої матриці. Метод максимін/мінімакс може бути набагато швидшим.