Економічна і геометрична інтерпретації задач теорії ігор

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

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

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

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

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

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

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

Парні ігри з нульовою сумою.

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

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

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

З чисел  складемо матрицю

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

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

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

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

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

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

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

Визначення 2. Гра, для якої  , називається грою із сідловою точкою.

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

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

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

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

Змішану стратегію першого гравця позначають ,

а другого гравця – як вектор ,

де , , ,

Якщо  – оптимальна стратегія першого гравця,

а  – оптимальна стратегія другого гравця,

то число  є ціною гри.