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

І. Теоретичні відомості.

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

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

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

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

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

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

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

Ми будемо розглядати саме парні ігри з нульовою сумою.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

є ціною гри.

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

Теорема 2. Всяка матрична гра з нульовою сумою має розв’язок в мішаних стратегіях.

Теорема 3. Для того щоб число v було ціною гри, а і — оптимальними стратегіями, необхідно і достатньо виконання нерівностей

() і ()

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

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

Дата добавления: 2015-08-21