Матричні ігри з нульовою сумою

Класифікація задач теорії ігор.

Тема 6. Основи теорії ігор.

Теорія ігор – це математична теорія конфліктних ситуацій, яка дозволяє розробити рекомендації, щодо найбільш раціонального способу дій будь-якого учасника конфліктної ситуації.

Конфліктна ситуація – це така ситуація, в якій зіштовхуються інтереси двох і більше сторін, що мають різні цілі.

Гра - це математична модель конфліктної ситуації, яка розвивається за певними правилами.

Гра – це певний набір правил, угод, або домовленостей, що визначають можливі дії учасників конфліктної ситуації.

Правила гри включають:

а) порядок чергування дій учасників конфліктної ситуації (хід);

б) правила виконання кожного ходу;

в) кількісний результат гри (виграш або програш) до якого призводить вказана сукупність ходів;

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

Вибір одним із гравців своєї стратегії, називається ходом.

Партія – можлива реалізація правил гри.

Результат гри – значення деякої функції, яка може бути задана аналітично або таблично (матрично).

а) за кількістю сторін в конфлікті:

- ігри з двома гравцями (двосторонні);

- ігри, більше ніж з 2-ма гравцями (багатосторонні) – коаліційні та антагоністичні (інтереси діаметрально протилежні);

б) за кількістю ходів:

- одноходові;

- багатоходові;

в) за кількістю стратегій:

- з кінцевою кількістю;

- з нескінченною кількістю;

г) за кількісним результатом гри:

- ігри з нульовою сумою;

- ігри з ненульовою сумою;

д) за правилами гри і наявністю стратегії:

- стратегічні ігри;

- ігри з чисто випадковим результатом;

е) за наявністю інформації:

- з повною інформацією;

- з неповною інформацією;

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

Вибрані числа порівнюються. Припустимо, що 1-й гравець, вибравши число і платить другому гравцю, який вибрав число j певну суму .

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

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

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

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

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

min max a_ij = - ціною гри для гравця А;

max min a_ij = - ціною гри для гравця В.

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

(i,j) a_j = max min a_ij - оптимальні чисті стратегії гравців А і В.

Стр. А
max

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

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

, що задовольняють:

умовам =

Змішаною стратегією

Числа та представляють собою імовірності вибору гравцем А чистої стратегії і

і, відповідно, гравцем B – чистої стратегії j.

Значення - оптимальні змішані стратегії гравців, якщо виконується умова:

a_ij

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

Дата добавления: 2014-12-07