Основні визначення

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

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

….Кількісна оцінка результатів гри називається платежем.

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

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

В результаті вибору дії у А гравець під впливом обстановки отримає результат, який позначимо як z А₀, де А₀ - множина всіх можливих для даної гри результатів діяльності.

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

. Стратегія гравця називається оптимальною, якщо при багаторазовому повторенні гри вона забезпечує гравцеві максимально можливий середній виграш (або, що те ж саме, мінімально можливий середній програш). Нехай є два гравці, один з яких може вибрати і-ю стратегію з m своїх можливих стратегій (і = 1.m), а другий, не знаючи вибору першого, вибирає j-ю стратегію з п своїх можливих стратегій (j=1, n). У результаті перший гравець виграє величину a_ij, а другий програє цю величину. З чисел а_ij складемо матрицю

  Рядки матриці А відповідають стратегіям першого гравця, а стовпці - стратегіям другого. Ці стратегії називаються чистими.

. Матриця А називається платіжною. (або матрицею гри)..

Гру, яка визначається матрицею А, що має m рядків і п стовпців, називають кінцевою грою розмірності m n.

Число = називається нижньою. ціною гри або максиміном, а відповідну йому стратегію (рядок) — максимінною.

Число називається верхньою ціною гри или мінімаксом, а відповідну йому стратегію гравцю(стовпчик) — минімаксною.

Теорема. Нижня ціна гри завжди не перевищує верхньої ціни гри.

. Якщо = υ, то число υ називається ціною гри.

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