ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Платіжна матриця. Нижня та верхня ціна гри

Загрузка...

Розглянемо парну кінцеву гру. Нехай гравець А має m особистих стратегій, які позначають А1, А2,…, Аm. У гравця В є n особистих стратегій, позначимо їх В1, В2,…, Вn. В цьому випадку кажуть, що гра має розмір . В результаті вибору гравцями будь-якої пари стратегій Аi і Вj (i = 1, 2,…, m; j = 1, 2,…, n) однозначно визначається результат гри, тобто виграш aij гравця А (додатній або від’ємний) і програш (–aij) гравця В. Припустимо, що значення aij відомі для будь-якої пари стратегій (Аi, Вj). Матриця Р = (aij), (i = 1, 2,…, m; j = 1, 2,…, n) називається платіжною матрицею, або матрицею гри. Загальний вигляд такої матриці:

.

Приклад. Гра «вірю – не вірю». Правила гри: Гравець А має на руках 8 карт – 4 тузи і 4 двійки. Він витягує карту, не показуючи її гравцю В, і говорить: «туз» (при цьому він може збрехати, а може сказати правду). Якщо гравець В вірить, то він сплачує гравцю А 1 грн. Якщо гравець В не вірить, то гравець А показує карту і якщо це дійсно «туз», то гравець В платить гравцю А 2 грн. Якщо це «двійка», то гравець А сплачує гравцю В 2 грн. Якщо гравець А витягує «двійку» і говорить правду, то він сплачує гравцю В 1грн.

Розв’язання. У гравця А є дві стратегії: А1 – правда, А2 – брехня. У гравця В є дві стратегії: В1 – вірю, В2 – не вірю. Складемо матрицю платежів. Вона має вигляд

.

Знайдемо елементи матриці aij.

Нагадаємо, що ймовірність витягти «туз» дорівнює 0,5 і ймовірність витягти «двійку» теж дорівнює 0,5. При цьому зауважимо, якщо гравець А твердить, що він витягнув «двійку», то гравцю В не має сенсу не вірити, і якщо гравець витягнув «туз», то йому немає сенсу брехати. Тоді при стратегіях

А1В1 : а11 = 0,5·1+0,5·(-1) = 0,

А1В2 : а12 = 0,5·2+0,5·0 = 1,

А2В1 : а21 = 0,5·0+0,5·1 = 0,5,

А2В2 : а22 = 0,5·0+0,5·(-2) = -1.

Таким чином, маємо наступну платіжну матрицю:

.

 

Далі розглянемо гру з матрицею Р = (aij), (i = 1, 2,…, m; j = 1, 2,…, n) і визначимо найкращу серед стратегій А1, А2,…, Аm.

Наведемо міркування гравця А. Вибираючи стратегію Аi, гравець А повинен розраховувати, що гравець В відповість на неї стратегією Вj, для якої виграш для гравця А є мінімальним.

Позначимо через ai – найменший виграш гравця А при виборі ним стратегії Аi для всіх можливих стратегій гравця В (найменше число в і-му рядку платіжної матриці), тобто . Серед всіх чисел aі (i = 1, 2,…, m) виберемо найбільше . Назвемо aнижньою ціною гри, або максиміном. Це гарантований виграш гравця А при будь-якій стратегії гравці В.

.

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

Гравець В зацікавлений у тому, щоб зменшити виграш гравця А. Вибираючи стратегію Вj, він враховує максимально можливий при цьому виграш для А. Позначимо . Серед всіх чисел bj виберемо найменше . І назвемо bверхньою ціною гри, або мінімаксом. Це гарантований програш гравця В.

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

Встановимо зв’язок між a і b. Нехай a досягається на r-й стратегії (тобто a = ar), а b на стратегії s (тобто b =bs). На перетині r-го рядка s-го стовпця знаходиться елемент ars. Тоді b ars a. Тобто ab.

Якщо верхня та нижня ціни гри співпадають, то їх спільне значення позначається v і називається чистою ціною гри, або ціною гри. В такому випадку в платіжній матриці існує елемент ars , який дорівнює ціні гри, тобто

b = ars = a = v.

При цьому гравець А має максимальний гарантований виграш v, який не залежить від поведінки гравця В, якщо застосує стратегію Аr, а гравець В досягне мінімального програшу v (незалежного від поведінки гравця А), якщо застосує стратегію Вs. Кажуть, що розв’язок гри має стійкість, тобто, якщо один з гравців дотримується своєї оптимальної стратегії, то для другого не може бути вигідним відхилення від своєї оптимальної стратегії. Елемент ars у цьому випадку називається сідловою точкою.

Позначимо через А* і В* – пару чистих стратегій, на яких досягається розв’язок гри в задачі з сідловою точкою (А*= Аr, В*= Вs). Введемо в розгляд функцію виграшу у першого гравця на кожній парі стратегій: F(Аi, Вj) = aij.

Тоді з умови оптимальності у сідловій точці виконується подвійна нерівність:

F(Аi, В*) ≤ F(А*, В*) ≤ F(А*, Вj),

1 ≤ i m, 1 ≤ j n.

Дійсно, вибір стратегії А* першим гравцем при оптимальній стратегії В* другого гравця максимізує мінімальний можливий виграш:

F(А*, В*) ≥ F(Аi, В*),

а вибір стратегії В* другим гравцем при оптимальній стратегії А* першого гравця мінімізує максимальний програш:

F(А*, В*) ≤ F(А*, Вj).

Приклад. Визначити нижню і верхню ціну гри, що задана платіжною матрицею:

У даному прикладі

a = max(ai) = 3 ,

b = min(bj) = 3,

a = b = 3.

Таким чином, А3, В3 – урівноважені стратегії. Гра має сідлову точку а32 і ціну гри v = 3.

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти