Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Государственный экономико-технологический университет транспорта

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

T_1-10.doc

Скачиваний:

Добавлен:

20.02.2016

Размер:

4.34 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 1313

Розв’язування ігор 2×2

Розглянемо гру двох учасників, кожен з яких має дві стратегії. Метод її розв’язання базується на наступному твердженні.

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

Нехай перший гравець використовує свою оптимальну стратегію, а другий гравець весь час використовує стратегію , тоді виграш першого гравця дорівнює

Тепер нехай другий гравець завжди використовує стратегію , тоді виграш першого гравця дорівнює

крім того сума ймовірностей

Отримали систему трьох рівнянь з трьома невідомими:

. (8.1)

Аналогічно, для визначення оптимальної стратегії другого гравця отримаємо систему

. (8.2)

Приклад 8.2. Знайти розв’язок у мішаних стратегіях гри з приклада 8.1.

Розв’язання. Розв’язуючи приклад 8.1 ми спростили платіжну матрицю до наступної


	3	6
	4	2

Для знаходження оптимальної стратегії першого гравця розв’яжемо систему

Оскільки праві частини перших двох рівнянь рівні, то прирівняємо їх ліві частини:

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

Перший гравець повинен застосовувати стратегію з імовірністю , стратегію з імовірністю , при цьому його середній виграш складе 3,6 умовних одиниць.

Для знаходження оптимальної стратегії другого гравця маємо систему

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

Відповідь. Перший гравець повинен застосовувати стратегію з імовірністю , стратегію з імовірністю . Другий гравець повинен застосовувати стратегію з імовірністю , а стратегію з імовірністю . Перший гравець в середньому виграє 3,6 умовних одиниць.

Графічне розв’язування ігор 2×n та m×2

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

Припустимо, що це перший гравець.

Алгоритм методу

Крок 1.

На осі ординат відкладемо виграші першого гравця при застосуванні першої стратегії, а на прямій Р = 1 – другої.

Крок 2 .

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

Крок 3.

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

, (8.3)

Де і номер одної із стратегій другого гравця, якій відповідає відрізок, що проходить через точку М.

Крок 4.

Оптимальну стратегію другого гравця знаходимо з умови, що він використовує лише ті дві стратегії, для яких відповідні відрізки перетинаються в точці М, тобто його оптимальна стратегія є розв’язком гри 2×2.

Графічне розв’язання гри 2×n показане на рис.8.1.

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

Рис. 8.1. Графічне розв’язання гри 2×n. Рис. 8.2. Графічне розв’язання гри m×2.

Приклад 8.3. Спростити платіжну матрицю гри та розв’язати її графічно.

Розв’язання. Знайдемо нижню та верхню ціни гри.


3	2	4	5	2
5	2	4	6	2
3	6	5	4	3
4	1	3	4	1
5	6	5	6	3 5

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


3	2	4	5
5	2	4	6
3	6	5	4
4	1	3	4

Спрощена платіжна матриця не має домінуючих рядків і стовпчиків. Отримали гру 2×3.


5	2	4
3	6	5

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

За формулою (8.3) .

Знайдемо оптимальну стратегію другого гравця. В точці М перетнулись відрізки, що відповідають стратегіям , . Отримуємо гру з платіжною матрицею


	5	2
	3	6

Запишемо систему (8.2)

розв’язавши яку одержуємо .

Відповідь. Перший гравець повинен застосовувати стратегії таз однаковими ймовірностями . Другий гравець повинен застосовувати стратегію з імовірністю , а стратегію з імовірністю . Перший гравець в середньому виграє 4 умовні одиниці.

а) б)

Рис. 8.3. Графічне розв’язання гри 2×3 (приклад 8.3).

Зауваження 8.3. Після визначення двох відрізків, що перетинаються в точці М і відповідних їм стратегій, ми отримали гру 2×2. Тому ми можемо знайти, як розв’язки системи (8.1), не використовуючи властивості подібних трикутників.

Приклад 8.4. Спростити платіжну матрицю гри та розв’язати її графічно.

Розв’язання. Знайдемо нижню та верхню ціни гри.


6	6	2	1	2	1
3	4	8	7	7	3
4	5	6	6	8	4
3	5	6	5	7	3
6	6	8	7	8	4 6

Гра сідлової точки не має (), тому перейдемо до спрощення платіжної матриці. Третій рядок домінує над четвертим, тому стратегію відкидаємо. Другий стовпчик домінує над першим, а третій та п’ятий над четвертим, тому відкидаємо стратегії,,.


6	6	2	1	2
3	4	8	7	7
4	5	6	6	8
3	5	6	5	7

Спрощена платіжна матриця не має домінуючих рядків і стовпчиків.


	6	1
	3	7
	4	6

а) б)

Рис. 8.4. Графічне розв’язання гри 3×2 (приклад 8.4).

Отримали гру 3×2.

Побудову ламаної максимальних виграшів першого гравця показано на рис. 8.4 а). Знаходимо на ній точку М з найменшою ординатою. В цій точці перетинаються відрізки, що відповідають стратегіям та . Стратегію відкидаємо. Із подібності виділених на рис. 8.4 б) трикутників маємо , тобто . З урахуванням того, що , маємо .