Ігри зі змішаними стратегіями

Якщо , матриця не містить сідловкої точки. Застосування мінімаксних стратегій забезпечить виграш не менше і програш не більше відповідно. У цьому випадку говорять про розв’язок гри в змішаних стратегіях: кожний із гравців буде застосовувати кілька стратегій при їхньому випадковому виборі.

 

Введемо в розгляд два вектори:

;

і - це ймовірності, з якими кожен гравець застосовує свої первісні, чисті стратегії.

Виграш при використанні змішаних стратегій визначається як математичне сподівання виграшу чи як середній виграш.

 

змінними є і .

 

Виконано рівність:

(11.5)

 

Теорема:

Кожна скінченна гра має, принаймні, один розв’язок, можливо, в області змішаних стратегій.

- оптимальні ймовірності стратегій

– значення гри чи ціна гри

.

Розглянемо найпростіший окремий випадок.

; .

 

3. Якщо сідлівкої точки немає, необхідно застосовувати змішані стратегії. Вводимо в розгляд два вектори ймовірностей.

;

(11.6)

 

 

Система лінійна, може бути вирішена будь-якими способами.

(11.7)

 

 

Друга система для ймовірностей :

(11.7)

 

Приклад.

Розв’язок гри в змішаних стратегіях

 

– нижня ціна гри

– верхня ціна гри

Сідловкої точки немає, тому що . Шукаємо розв’язок гри в змішаних стратегіях.

. Аналогічно .

4. Розв’язок гри може бути отриманий геометрично (за допомогою графіків)

 

 

називається нижньою межею виграшу.

Верхня точка К визначає розв’язок гри ціну значення гри та ймовірностей.

 

 

 

Аналогічно може бути геометрично вирішена гра з матрицею . Результат розв’язання: ціна гри ; імовірності й і вектор , причому всі координати дорівнюють нулю, крім двох.

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

Аналогічно можна геометрично розв’язати гру з матрицею . Геометричний метод може бути використаний тільки для знаходження активних стратегій гравців. Для квадратної матриці другого порядку, що залишилася, розв’язок може бути знайдений аналітично.

Контрольні питання

1. Як визначаються нижня і верхня ціни гри?

2. Які стратегії гравців називаються максимінною і мінімаксною?

3. Що називається розв’язанням гри в змішаних стратегіях?

4. Як вирішити гру аналітично у випадку квадратної матриці другого порядку?

5. Як геометрично одержати розв’язок гри в змішаних стратегіях?

 

Лекція 12
Зведення матричної гри до задачі лінійного
програмування

 

1. Рівняння і нерівності моделі

2. Вибір заміни змінних, перехід до задачі лінійного програмування

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

4. Приклад військово-тактичної гри

 

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

Два гравці: і . Гра скінченна, маємо стратегій гравця і n стратегій гравця . Задано матрицю гри , ; ; елементи якої є можливими виграшами гравця .

 

Припустимо, що матриця не має сідловкої точки, значить . Гра розв’язується в змішаних стратегіях. Вектори ймовірностей і .

- значення гри.

При правильній грі гарантійний виграш першого гравця:

(12.1)

Для другого гравця:

(12.2)

Ці нерівності доповнюються умовами:

(12.3)

 

2.Припустимо, що . Введемо нову змінну:

 

 

Результат:

(12.4)

 

(12.5)

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

Цільова функція:

(12.6)

Задачу можна розв’язати симплекс-методом.

У результаті знайдемо вектор і .

Одержуємо:

,

(12.7)

Для виходить двоїста задача.

Цільова функція:	(12.8)
Система обмежень: ,	(12.9)

де ;

(12.10)

Задача (12.8) – (12.10) є двоїстою для задачі (12.4) – (12.6) і .

Оптимальний план задачі:

(12.11)

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

.

знаходиться тим же самим способом.

Значення гри вийде збільшеним на число :

.

Після закінчення розв’язання знаходимо і ; .

4. Приклад військово-тактичної гри.

Дві воюючі армії ведуть боротьбу за 2 пункти. Перша армія складається з 4-х полків, друга армія має 3 полки. Армія, що посилає більше полків на той чи інший населений пункт займає його і знищує всі спрямовані на цей пункт сили супротивника. Відповідний гравець одержує одиницю за зайнятий пункт і по одиниці за кожен знищений полк супротивника. У разі рівності сил, спрямованих у деякий пункт, очки не виграються.

Мета гри: розподілити сили так, щоб одержати максимальний загальний виграш.

Стратегія кожного гравця буде визначатися парою чисел .

– кількість військ, посланих на I пункт, – на II пункт.

– стратегії першого гравця .

– стратегії другого гравця .

Матриця гри

	(3;0)	(2;1)	(1;2)	(0;3)
(4;0)
(3;1)				-1
(2;2)	-2			-2
(1;3)	-1
(0;4)

 

;

Цільова функція:

 

Розв’язок

;

Не рекомендовані другий і четвертий варіанти.

Для супротивника .

Контрольні питання

1. Скільки змінних містить загальна математична модель матричної гри?

2. Який вид задачі лінійного програмування?

3. Як знайти розв’язок задач лінійного програмування?

4. Як одержати розв’язок гри в змішаних стратегіях?

 

Лекція 13
Ігри з природою

 

1. Основні визначення в іграх із природою

2. Критерії при розв’язуванні ігор з природою

3. Приклад гри: планування будівництва електростанції

 

Раніше були розглянуті парні ігри, учасники яких мали протилежні інтереси. Тому дії кожного гравця (стратегії) мали на меті збільшення виграшу (зменшення програшу) при відомих варіантах поводження супротивника. У багатьох реальних задачах невизначеність викликається відсутністю інформації про дії супротивника і його можливих стратегій, такі ігри називаються іграми з природою.

Приклад.

Сільськогосподарське виробництво: вирощування зернових. Стратегія людини визначається термінами посіву, технологією проведення робіт, розподілом культур по площах, кількістю і термінами внесених добрив, застосуванням засобів захисту, зрошенням (де є можливість). – людина – природа

Людина, в іграх із природою повинна діяти обачно, застосовуючи,наприклад, чи стратегію.

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

- стратегії гравця ;

- можливі стани природи;

Припустимо, що вдається на підставі попередніх розрахунків одержати матрицю:

; ;

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

Крім цієї матриці, може використовуватися матриця ризиків .

 

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