Головна » Розсилка » Антагоністичні матричні ігри. Антагоністичні ігри з безперервними стратегіями В антагоністичній парній грі цілі гравців

Антагоністичні матричні ігри. Антагоністичні ігри з безперервними стратегіями В антагоністичній парній грі цілі гравців

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

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

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

Тепер про все по порядку та докладно.

Платіжна матриця, чисті стратегії, ціна гри

У матричної гри її правила визначає платіжна матриця .

Розглянемо гру, в якій є два учасники: перший гравець та другий гравець. Нехай у розпорядженні першого гравця є mчистих стратегій, а у розпорядженні другого гравця - nчисті стратегії. Оскільки розглядається гра, природно, що у цій грі є виграші та є програші.

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

Складемо платіжну матрицю:

Якщо перший гравець вибирає i-ю чисту стратегію, а другий гравець - j-ю чисту стратегію, то виграш першого гравця складе aijодиниць, а програш другого гравця - також aijодиниць.

Так як aij + (- a ij ) = 0, то описана гра є матричною грою з нульовою сумою.

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

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

Як відбувається вибір стратегії у матричній грі?

Знову подивимося на платіжну матрицю:

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

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

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

При вирішенні завдань на ціну гри та визначення стратегії для визначення цих величин у другого гравця слід чинити так. З кожного стовпця виписати значення максимального елемента і з них вибрати мінімальний. Таким чином, програш другого гравця буде мінімальним із максимальних. Звідси і назва – мінімаксний виграш. Номер шпальти цього елемента і буде номером чистої стратегії, яку обирає другий гравець. Якщо другий гравець використовує "мінімакс", то незалежно від вибору стратегії першим гравцем він програє не більше v2 одиниць.

приклад 1.

Найбільший із найменших елементів рядків – 2, це нижня ціна гри, їй відповідає перший рядок, отже, максиминна стратегія першого гравця перша. Найменший з найбільших елементів стовпців – 5, це верхня ціна гри, їй відповідає другий стовпець, отже, мінімаксна стратегія другого гравця – друга.

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

Отже, гарантований виграш першого гравця:

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

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

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

Ще приклад із тієї ж серії.

приклад 2.Дано матричну гру з платіжною матрицею

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

Рішення. Праворуч від платіжної матриці випишемо найменші елементи в її рядках і відзначимо максимальний з них, а знизу від матриці - найбільші елементи в стовпцях і оберемо мінімальний із них:

Найбільший із найменших елементів рядків – 3, це нижня ціна гри, їй відповідає другий рядок, отже, максиминна стратегія першого гравця другий. Найменший з найбільших елементів стовпців – 5, це верхня ціна гри, їй відповідає перший стовпець, отже, мінімаксна стратегія другого гравця – перша.

Сідлова точка в матричних іграх

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

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

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

приклад 3.Дано матричну гру з платіжною матрицею

Нижня ціна гри збігається із верхньою ціною гри. Таким чином, ціна гри дорівнює 5. Тобто . Ціна гри дорівнює значенню сідлової точки. Максиминна стратегія першого гравця – друга чиста стратегія, а мінімаксна стратегія другого гравця – третя чиста стратегія. Ця матрична гра має рішення у чистих стратегіях.

Вирішити завдання на матричну гру самостійно, а потім переглянути рішення

приклад 4.Дано матричну гру з платіжною матрицею

Знайти нижню та верхню ціну гри. Чи має ця матрична гра сідлову точку?

Матричні ігри з оптимальною змішаною стратегією

У більшості випадків матрична гра не має сідлової точки, тому відповідна матрична гра не має рішень у чистих стратегіях.

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

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

Якщо перший гравець використовує чисті стратегії з імовірностями , то вектор називається змішаною стратегією першого гравця. Інакше кажучи, це "суміш" чистих стратегій. При цьому сума цих ймовірностей дорівнює одиниці:

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

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

Приклад 5.Дано матричну гру з платіжною матрицею

Визначити математичне очікування виграшу першого гравця (програшу другого гравця), якщо змішана стратегія першого гравця, а змішана стратегія другого гравця.

Рішення. Відповідно до формули математичного очікування виграшу першого гравця (програшу другого гравця) воно дорівнює добутку вектора змішаної стратегії першого гравця, платіжної матриці та вектора змішаної стратегії другого гравця:

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

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

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

У такому разі для функції E існує сідлова точка що означає рівність.

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

Зведення матричної гри до задачі лінійного програмування

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

Функція мети у прямій задачі лінійного програмування:

Система обмежень у прямій задачі лінійного програмування:

Функція мети у подвійному завданні:

Система обмежень у подвійному завданні:

Оптимальний план прямого завдання лінійного програмування позначимо

а оптимальний план двоїстої задачі позначимо

Лінійні форми для відповідних оптимальних планів позначимо і ,

а знаходити їх слід як суми відповідних координат оптимальних планів.

Відповідно до визначень попереднього параграфа та координатами оптимальних планів, в силі наступні змішані стратегії першого та другого гравців:

Математики-теоретики довели, що ціна гри наступним чином виражається через лінійні форми оптимальних планів:

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

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

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

Приклад 6.Дано матричну гру з платіжною матрицею

Знайти ціну гри Vта оптимальні змішані стратегії та .

Рішення. Складаємо відповідне даної матричної гри завдання лінійного програмування:

Отримуємо вирішення прямого завдання:

Знаходимо лінійну форму оптимальних планів як суму знайдених координат.

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

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

Таблиця 26.1

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

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

Розглянемо приклад гри G (4X5) у матричній формі. У нашому розпорядженні (на вибір) чотири стратегії, у супротивника – п'ять стратегій. Матриця гри дана у таблиці 26.2

Давайте поміркуємо про те, якою стратегією нам (гравцеві А) скористатися? У матриці 26.2 є спокусливий виграш "10"; нас так і тягне вибрати стратегію, при якій цей «ласий шматок» нам дістанеться.

Але заждіть: противник теж не дурень! Якщо ми виберемо стратегію він, на зло нам, вибере стратегію і ми отримаємо якийсь жалюгідний виграш «1». Ні, вибирати стратегію не можна! Як же бути? Очевидно, виходячи з принципу обережності (а він – основний принцип теорії ігор), треба вибрати ту стратегію, за якої наш мінімальний виграш максимальний.

Таблиця 26.2

Це - так званий «принцип міні-максу»: роби так, щоб при найгіршій для тебе поведінці супротивника отримати максимальний виграш.

Перепишемо таблицю 26.2 та у правому додатковому стовпці запишемо мінімальне значення виграшу у кожному рядку (мінімум рядка); позначимо його для рядка а (див. таблицю 26.3).

Таблиця 26.3

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

Цей виграш називається нижньою ціною гри (або «максиміном» – максимальний із мінімальних виграшів). Позначатимемо його а. У нашому випадку

Тепер станемо на думку противника і поміркуємо за нього. Адже він не пішака якась, а теж розумний! Вибираючи стратегію, він хотів би віддати якомога менше, але повинен розраховувати на нашу, найгіршу для нього, поведінку. Якщо він вибере стратегію, ми йому відповімо і він віддасть 10; якщо вибере - ми йому відповімо і він віддасть і т. д. Припишемо до таблиці 26.3 додатковий нижній рядок і в ньому запишемо максимуми стовпців Очевидно, обережний супротивник повинен вибрати ту стратегію, при якій ця величина мінімальна (відповідне значення 5 виділено в таблиці 26). . Ця величина Р - значення виграшу, більше якого свідомо не віддасть нам розумний противник. Вона називається верхньою ціною гри (або «мінімаксом» - мінімальний з максимальних виграшів). У нашому прикладі і досягається за стратегії противника

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

Тепер уявімо собі на хвилину, що ми дізналися про те, що супротивник дотримується стратегії. Ану, покараємо його за це і виберемо стратегію ми отримаємо 5, а це не так вже й погано. Але противник - теж не промах; нехай він дізнався, що наша стратегія, він теж поспішає вибрати, звівши наш виграш до 2, і т. д. (партнери «металися по стратегіям»). Одним словом, мінімаксні стратегії у нашому прикладі, нестійкі стосовно інформації про поведінку іншої сторони; ці стратегії не мають властивість рівноваги.

Чи завжди це так? Ні не завжди. Розглянемо приклад із матрицею, даною в таблиці 26.4.

У цьому вся прикладі нижня вартість гри дорівнює верхньої: . Що з цього випливає? Мінімаксні стратегії гравців А та В будуть стійкими. Поки обидва гравці їх дотримуються, виграш дорівнює 6. Подивимося, що буде, якщо ми дізнаємося (А), що противник (В) тримається стратегії В?

Таблиця 26.4

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

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

У читача може виникнути питання: чому оптимальні стратегії називаються «чистими»? Дещо забігаючи вперед, відповімо на це питання: бувають стратегії «змішані», які полягають у тому, що гравець застосовує не одну якусь стратегію, а кілька, перемежуючи їх випадковим чином. Так от, якщо допустити крім чистих ще й змішані стратегії, будь-яка кінцева гра має рішення – точку рівноваги. Але про це ще попереду.

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

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

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

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

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

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

Отже, поговоримо про змішані стратегії. Будемо позначати змішані стратегії гравців А і В відповідно де (утворюють у сумі одиницю) - ймовірність застосування гравцем А стратегій - ймовірність застосування гравцем У стратегії

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

Існує основна теорема теорії ігор: будь-яка кінцева гра двох осіб з нульовою сумою має принаймні одне рішення - пару оптимальних стратегій, у загальному випадку змішаних та відповідну ціну

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

Розглянемо приклад гри без сідлової точки та наведемо (без доказу) її розв'язання. Гра полягає в наступному: два гравці А я В одночасно і не змовляючись показують один, два або три пальці. Виграш вирішує загальну кількість пальців: якщо воно парне, виграє А і отримує у суму, рівну цьому числу; якщо непарне, то, навпаки, А платить у суму, рівну цьому числу. Як чинити гравцям?

Складемо матрицю гри. В одній партії у кожного гравця три стратегії: показати один, два чи три пальці. Матриця 3х3 дана у таблиці 26.5; у додатковому правому стовпці наведено мінімуми рядків, а додатковому нижньому рядку - максимуми стовпців.

Нижня ціна гри і відповідає стратегії Це означає, що при розумній, обережній поведінці, ми гарантуємо, що не програємо більше, ніж 3. Слабка втіха, але все ж таки краще, ніж, скажімо, виграш - 5, що зустрічається в деяких клітинах матриці. Погано нам, гравцю Л... Але втішимося: становище супротивника, здається, ще гірше: нижня ціна гри при. розумному поведінці він віддасть нам мінімум 4.

Вступ

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

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

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

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

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

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

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

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

Завдання теорії полягає в тому, що:

1) оптимальною поведінкою у грі.

2) дослідження властивостей оптимальної поведінки

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

4) побудова чисельних методів знаходження оптимальної поведінки.

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

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

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

Математична ТЕОРІЯ ІГР розпочалася з аналізу спортивних, карткових та інших ігор. Розповідають, що першовідкривач теорії ігор, видатний американський математик XX ст. Джон фон Нейман прийшов до ідеї своєї теорії, спостерігаючи за грою в покер. Звідси і походить назва «теорія ігор».

Почнемо дослідження даної теми з ретроспективного аналізу розвитку теорії гр.Розглянемо історію та розвиток питання теорії ігор. Зазвичай «генеалогічне дерево» представляється як дерева у сенсі теорії графів, у яких розгалуження походить від деякого єдиного «кореня». Родовід теорії ігор - книга Дж. фон Неймана та О. Моргенштерна. Тому історичний хід розвитку теорії ігор як математичної дисципліни, природно розчленовується на три етапи:

Перший етап- До появи монографії Дж. фон Неймана і О. Моргенштерна. Його можна назвати "до монографічним". На цьому етапі гра виступає поки що як конкретне змагання, що описується своїми правилами змістовних термінах. Лише наприкінці його Дж. фон Нейман виробляє уявлення про гру як загальну модель абстрактного конфлікту. Підсумком цього етапу стало накопичення низки конкретних математичних результатів і навіть окремих принципів майбутньої теорії ігор.

Другий етапскладає сама монографія Дж. фон Неймана та

О. Моргенштерна «Теорія ігор та економічна поведінка» (1944), що об'єднала у собі більшість раніше отриманих (втім, за сучасними математичними масштабами досить нечисленних) результатів. Вона вперше представила математичний підхід до ігор (як у конкретному, так і абстрактному розумінні цього слова) у вигляді систематичної теорії.

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

Проте навіть математична теорія ігор неспроможна повністю визначити результат деяких конфліктів. Можливо виділити три основні причини невизначеності результату гри (конфлікту).

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

По-друге, непрогнозований гравцями, випадковий вплив факторів на гру. Ці фактори надають вирішальний вплив на результат гри і лише малою мірою можуть бути або взагалі не можуть бути контрольованими та визначеними граючими. Остаточний результат гри лише малою, вкрай незначною мірою визначається самими діями гравців. Ігри, результат яких виявляється невизначеним через випадкові причини, називаються азартними. Результат гри завжди має імовірнісний або ймовірний характер (рулетка, гра в кістки, гра в «орлянку»).

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

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

Призначення сервісу. За допомогою сервісу в онлайн режимі можна:

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

Інструкція. Виберіть розмір матриці, натисніть Далі. У новому діалоговому вікні виберіть метод розв'язання матричної гри. Приклад заповнення. Результати обчислень оформлюються у звіті формату Word.

Гра- Це математична модель реальної конфліктної ситуації. Конфліктна ситуація двох гравців називається парною грою. Парну гру з нульовою сумою зручно дослідити, якщо вона описана як матриці. Така гра називається матричної; матриця, складена з чисел a ij називається платіжний. У таблиці представлені варіанти розв'язання гри, заданої платіжною матрицею А.

Опис алгоритму:

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

Представимо алгоритм розв'язання матричної гри графічно.

Малюнок - Схема розв'язання матричної гри.

Методи вирішення матричної гри у змішаних стратегіях

Отже, якщо сідлова точка відсутня, рішення гри проводять у змішаних стратегіях та вирішують такими методами:

Розв'язання гри через систему рівнянь.
Якщо задана квадратна матриця nxn (n=m), вектор ймовірностей можна знайти, вирішивши систему рівнянь. Цей метод використовується не завжди і застосовується тільки в окремих випадках (якщо матриця 2x2, то рішення гри виходить практично завжди). Якщо рішенні виходять негативні ймовірності, то цю систему вирішують симплекс-методом.
Рішення гри графічним способом.
У випадках, коли n=2 або m=2 матричну гру можна вирішити графічно.
Рішення матричної гри симплекс-метод.
У цьому випадку матрична гра зводиться до

Надрукувати