11.1: Суворо визначені ігри

Last updated
Save as PDF

Page ID: 67056

$ \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}}$

У цьому розділі ми вивчимо ігри, в яких беруть участь лише два гравці. У цих іграх, оскільки виграш для однієї людини - це програш для іншої, ми називаємо їх іграми з нульовою сумою двох осіб. Хоча ігри, які ми тут вивчимо, досить прості, вони дадуть нам розуміння того, як працюють ігри та як вони застосовуються в практичних ситуаціях. Почнемо з прикладу.

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

Роберт і Керол вирішують зіграти в гру, використовуючи копійки і чверть. Кожен вибирає одну з двох монет, кладе її в руку і закриває кулак. При заданому сигналі вони одночасно відкривають кулаки. Якщо сума монет менше 35 центів, Роберт отримує обидві монети, інакше Керол отримує обидві монети. Напишіть матрицю для гри, визначте оптимальні стратегії для кожного гравця, і знайдіть очікуваний виграш для Роберта.

Рішення

Припустимо, Роберт - гравець рядків, тобто він грає рядки, а Керол - гравець стовпців. Якщо Роберт покаже копійки, а Керол покаже копійки, сума буде менше тридцяти п'яти центів, а Роберт виграє десять центів. Але, якщо Роберт покаже копійки, а Керол покаже чверть, сума не буде менше тридцяти п'яти центів, а Керол виграє десять центів або Роберт втратить десять центів. Наступна матриця зображує всі чотири випадки і відповідні їм виплати для Роберта. Пам'ятайте, що негативне значення - це програш для Роберта і виграш для Керол.

$Приклад 11.1.1.PNG$

Найкраща стратегія для Роберта - це завжди показувати копійки, тому що таким чином найгірше, що він може зробити, - це втратити десять центів. І найкраща стратегія для Керол - це завжди показувати чверть, тому що найгірше, що вона може зробити, - це втратити десять центів. Якщо і Роберт, і Керол грають свої оптимальні стратегії, Роберт буде втрачати десять центів кожен раз. Тому значення гри негативне десять центів.

У наведеному вище прикладі, оскільки існує лише одна фіксована оптимальна стратегія для кожного гравця, незалежно від стратегії суперника, ми говоримо, що гра має чисту стратегію і строго визначена.

Далі формулюємо метод пошуку оптимальної стратегії для кожного гравця і значення гри. Метод передбачає розгляд найгіршого сценарію для кожного гравця.

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

Пошук оптимальної стратегії та значення для строго визначених ігор

Поставте зірочку (*) біля мінімального запису в кожному рядку.
Поставте коробку навколо максимального запису в кожному стовпці.
Запис, який має як зірочку, так і поле, представляє значення гри і називається точкою сідла.
Рядок, пов'язаний з точкою сідла, представляє найкращу стратегію для гравця рядка, а стовпець, який пов'язаний з точкою сідла, представляє найкращу стратегію для гравця стовпця.
Матриця гри може мати більше однієї точки сідла, але всі точки сідла мають однакове значення.
Якщо немає сідлової точки, гра не визначена строго. Нестрого визначені ігри є предметом наступного розділу.

Приклад$\PageIndex{2}$

Знайдіть точки сідла та оптимальні стратегії для наступної гри.

$Приклад 11.1.1. PNG$

Рішення

Ми знаходимо точку сідла, розмістивши зірочку поруч із мінімальним записом у кожному рядку, і поставивши поле навколо максимального запису в кожному стовпці, як показано нижче.

$Приклад 11.1.1 б.пнг$

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

Стратегія гравця рядків записується як\ (\ left [\ begin {array} {ll}
0 & 1
\ end {array}\ right]\), що вказує на те, що він буде грати рядок 1 з ймовірністю 0 і рядок 2 з ймовірністю 1.

Аналогічно стовпчик стратегії гравця записується як\ (\ left [\ begin {array} {l}
1\\
0
\ end {array}\ right]\), що означає, що він буде грати стовпець 1 з імовірністю 1, і стовпець 2 з ймовірністю 0.