Тема 6. Елементи теорії ігор

23 24 25 26 27 28 29

ЛАБОРАТОРНЕ ЗАНЯТТЯ № 20.

Тема заняття: Розв’язання задач теорії ігор.

(Графічний метод розв’язання задач теорії ігор розміром 2x2, 2xn, mx2).

Мета: сформувати вміння та навички розв’язання задач теорії ігор розміром 2x2, 2xn, mx2 графічним методом.

Методичні рекомендації: Вивчити лекцію №6 та ознайомиться з наступною літературою [3 с. 224-250], [4 с. 239-251].

Постановка задачі

Найпростішим випадком скінченної гри є парна гра, коли у кожного учасника є дві стратегії.

В_j A_i	B ₁	B ₂
A ₁	a ₁₁	a ₁₂
A ₂	a ₂₁	a ₂₂

Розглянемо випадок, коли гра не має сідлової точки. Отже, . Необхідно знайти змішані стратегії та ціну гри. Позначимо шукані значення ймовірноcтей застосування «чистих» стратегій гравця А через , а для гравця В — через .

Згідно з основною теоремою теорії ігор, якщо гравець А притримується своєї оптимальної стратегії, то виграш буде дорівнювати ціні гри. Отже, якщо гравець А притримуватиметься своєї оптимальної стратегії , то:

(1)

Оскільки , то . Підставивши цей вираз у систему рівнянь (1), отримаємо:

Розв’язавши дане рівняння відносно невідомого , маємо:

, (2)

тоді: = . (3)

Провівши аналогічні міркування стосовно гравця В, маємо:

(4)

Оскільки , то .

Розв’язавши це рівняння відносно невідомого , маємо:

, (5)

тоді: . (6)

Ціну гри u знаходять, підставлючи значення (або ) в будь-яке з рівнянь (1) або (4):

. (7)

Приклад. Знайти розв’язок гри з платіжною матрицею:

В_j A_i	B ₁	B ₂
A ₁
A ₂

Розв’язання. Переконаємося, що гра не має сідлової точки:

Отже, ця гра не має сідлової точки. Скористаємося формулами (2), (3), (5), (6), (7). Маємо:

;

Ціна гри .

Отже, оптимальна стратегія кожного гравця полягає в тому, щоб випадково чергувати свої «чисті» стратегії. Гравець А має використовувати першу стратегію з імовірністю , а другу — з імовірністю , а гравець В — навпаки. За цих умов середній виграш дорівнюватиме 3,5.

Розв’язку гри 2 ´ 2 можна дати наочну геометричну інтерпретацію.

Розглянемо гру з платіжною матрицею виду:

В_j A_i	B ₁	B ₂
A ₁	a ₁₁	a ₁₂
A ₂	a ₂₁	a ₂₂

Відмітимо на осі абсцис відрізок довжиною, що дорівнює одиниці (рис. 1). Лівий кінець відрізка (точка з абсцисою х = 0) буде відповідати стратегії А ₁, а правий кінець (х = 1) — стратегії А ₂, всі проміжні точки цього відрізка відповідатимуть змішаним стратегіям гравця А, причому імовірність х ₁ стратегії А ₁ буде дорівнювати відстані від точки Р до правого кінця відрізка, а ймовірність х ₂ стратегії А ₂ — відстані до лівого кінця відрізка. Проведемо через точки А ₁ та А ₂ два перпендикуляри до осі абсцис: вісь І і вісь ІІ. На першій з них відмітимо виграш за вибору стратегії А ₁, а на другій — за стратегії А _2.

Нехай противник вибрав стратегію В ₁, їй відповідають на осях І та ІІ дві точки В ₁, причому довжина відрізка А ₁ В ₁ дорівнює а ₁₁, а довжина відрізка А ₂ В ₁ дорівнює а ₁₂.

Аналогічно будуємо пряму В ₂ В ₂, яка відповідає стратегії В ₂.

Необхідно знайти оптимальну стратегію Х ^*, таку, за якої мінімальний виграш гравця А буде максимальним. Для цього виділимо жирною лінією на малюнку нижню межу виграшу за умови вибору стратегій В ₁ та В ₂, тобто ламану лінію В ₁ МВ ₂. На цій межі знаходяться значення мінімального виграшу гравця А за будь-якої його змішаної стратегії. Очевидно, що найкраще з можливих мінімальних значень у нашому прикладі знаходиться в точці М, а в загальному випадку відповідає тій точці, де крива, що позначає мінімальний виграш гравця А, набуває максимального значення. Ордината цієї точки є ціною гри u. Відстань до лівого кінця відрізка х ₂ та відстань до правого кінця відрізка — х ₁ дорівнюють відповідно ймовірностям стратегій А ₂та А ₁.

Рис. 1

Геометрична інтерпретація дає також змогу наочно зобразити нижню та верхню ціну гри (рис.2). Для нашого прикладу нижньою ціною гри є величина відрізка А ₂ В ₂, а верхньою ціною гри — А ₂ В ₁.

Рис.2

На цьому ж рисунку можна розглянути і геометричну інтерпретацію оптимальних стратегій противника В. Дійсно, частка стратегії В₁в оптимальній змішаній стратегії дорівнює відношенню довжини відрізка КВ₂до суми довжин відрізків КВ ₂ та КВ ₁ на осі І: .

З наведених міркувань легко висновувати, що гру 2 ´ 2 можна розв’язати елементарними прийомами. Аналогічно може бути розв’язана гра 2 ´ n, тобто коли гравець А має лише дві стратегії, а гравець
В – n. У такому разі на рисунку слід зобразити перетин n прямих, що відповідатимуть n стратегіям гравця В. Мінімальні виграші гравця А являтимуть собою також ламану лінію, максимальне значення якої і визначатиме оптимальну стратегію для гравця А (рис.3).

Рис.3

Можна також розв’язати і гру m ´ 2, з тією різницею, що необхідно визначати не нижню величину виграшу, а верхню і знаходити не максимальне з можливих значення, а мінімальне

Задача 1

Визначити оптимальні стратегії і ціну гри, використовуючи геометричну інтерпретацію:

1.1. ; 1.2. ;