Лекція 26

ТЕОРІЯ ІГОР. ІГРОВІ МЕТОДИ ОБГРУНТУВАННЯ РІШЕНЬ.

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

При вирішенні низки практичних завдань дослідження операцій доводиться аналізувати ситуації, в яких зустрічаються дві і більше сторони, що переслідують різні цілі, причому результат будь-якого заходу кожної з сторін залежить від того, яку дію вибере «противник». Такі ситуації ми будемо називати конфліктними. Кожна безпосередньо узята з практики конфліктна ситуація дуже складна і її аналіз утруднений наявністю багатьох несуттєвих факторів. Щоб зробити можливим математичний аналіз ситуації, треба відволіктися від цих другорядних факторів і побудувати спрощену, схематизовану модель ситуації. Таку модель ми будемо називати грою. Від реальної конфліктної ситуації гра відрізняється тим, що ведеться по цілком певним правилам. Такі формалізовані ігри як шашки, шахи і т. д. є найбільш зручний матеріал для ілюстрації та засвоєння основних понять теорії ігор. Це відбилося і на її термінології: сторони, що беруть участь в конфлікті, умовно іменуються гравцями, результат конфлікту - виграшем. У грі можуть мати справу інтереси двох або більше супротивників; в першому випадку гра називається парною, у другому множинною.

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

Гра називається грою з нульовою сумою, якщо один гравець виграє рівно стільки, скільки програє інший, тобто сума виграшів сторін дорівнює нулю. У грі з нульовою сумою інтереси супротивників прямо протилежні. Розвиток гри в часі ми будемо представляти складаючим з ряду послідовних етапів або «ходів». Ходом в теорії ігор називається вибір одного з передбачених правилами гри дій та його здійснення. Ходи бувають особисті й випадкові, Особистим ходом називається свідомий вибір гравцем одного з можливих варіантів дій та його здійснення. Випадковим ходом називається вибір з ряду можливостей, здійснюваний не рішенням гравця, а яким-небудь механізмом випадкового вибору. Деякі ігри складаються тільки з випадкових ходів (т. зв. Азартні ігри) або тільки з особистих ходів (шахи), Теорія ігор займається аналізом лише тих ігор які дотримають особисті ходи. Стратегією гравця називається сукупність правил, що визначають вибір варіанта дій при кожному особистому ході цього гравця в залежності від ситуації, що склалася в процесі гри. Оптимальною стратегією гравця називається така стратегія, яка при багаторазовому повторенні гри забезпечує даному гравцеві максимально можливий середній виграш. (або мінімально можливий середній програш). У теорії ігор не враховуються прорахунки і помилки гравців, а також елемент азарту та ризику.

Розглянемо гру, в якій гравець А має m стратегій, а гравець В - n стратегій. Така гра називається грою m x n, Будемо позначати стратегії А - А₁, А₂,... А_m, а стратегії В - В₁, В₂,... В_n, Припустимо, що кожна сторона вибрала певну стратегію: А_i і В_j, Якщо гра складається лише з особистих ходів, то вибір стратегій А_i, В_j однозначно визначає результат гри - виграш, позначимо його a_ij, Припустимо, що нам відомі значення а_ij при кожній парі стратегій. Ці значення можна записати у вигляді прямокутної таблиці, рядки якої відповідають стратегіям А_i, а стовпці - стратегіям противника В_j, Така таблиця називається платіжною матрицею або просто матрицею гри (див. табл, 26.1).

Таблиця 26.1

Ai\Bj	В1	В2	………..	Вn	a
А1	а11	a12	………..	a1n	a1
А2	a21	a22	………..	a2n	a2
			………..
Аm	am1	am2	….…..	amn	am
b	b1	b2	….…..	bn

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

Поставимо задачу: визначити найкращу серед А_i (наших) стратегій. Проаналізуємо послідовно кожну з них починаючи з А₁ і закінчуючи А_m, Вибираючи А_i, ми повинні розраховувати, що противник відповість на неї тієї із стратегій В_j, для якої наш виграш мінімальний. Знайдемо мінімальне з чисел a_ij в i-й рядку і позначимо його a_i = min a_ij. Випишемо числа a_i i (мінімуми рядків) поряд з матрицею справа у вигляді додаткового стовпця. Вибираючи якусь стратегію А_i, ми повинні розраховувати на те, що в результаті розумних дій противника ми виграємо тільки a_i i, Природно, діючи найбільш обережно, ми повинні віддати перевагу іншим ту стратегію, для якої число a_i максимальне. Позначимо це значення a = max a_i i, або враховуючи сказане раніше:

a = max min a_ij

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

Очевидно, аналогічне міркування можна провести і за противника В. Він зацікавлений в тому, щоб звернути наш виграш в мінімум: значить, він повинен переглянути всі свої стратегії, виділяючи для кожної з них максимальне значення виграшу. Випишемо внизу матриці максимальні значення по стовпцях а_ij: b_j = max a_ij і знайдемо з них мінімальне b = min b_j = min max a_ij. Величина b називається верхньою ціною гри, або максимальним виграшем або мінімакс, а відповідна стратегія мінімаксною стратегією. Дотримуючись своєї найбільш обережною мінімаксною стратегією, противник гарантований, що в будь-якому випадку він програє не більше b, Принцип обережності, диктує гравцям вибір відповідних стратегій, є в теорії ігор основним і називається принципом мінімакса, Він випливає з припущення про розумність кожного гравця, який прагне досягти мети, протилежної мети противника.

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

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