Матричні антагоністичні ігри з нульовою сумою в чистих стратегіях

Введення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другий етап становить сама монографія Дж. фон Неймана і

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

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

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

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

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

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

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

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

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

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

б) можливі дії кожної із сторін, іменовані також стратегіями або ходами;

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

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

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

ГЛАВА 1. МАТРИЧНІ Антагоністичні ГРИ

1.1 Прийняття рішень

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

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

Альтернативи.

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

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

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

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

Критерії

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

Нехай задано деякий кінцеве безліч альтернатив . З безлічі або будь-якого його підмножини необхідно виділити одну або кілька варіантів рішень в деякому сенсі кращих або більш відповідних яких-небудь заздалегідь обумовленим умовам. Для вирішення цього завдання звичайно використовується наступний підхід:

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

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

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

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

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

Повнота набору означає, що він повинен охоплювати всі важливі аспекти проблеми. Набір критеріїв є повним, якщо з його допомогою можна показати ступінь досягнення спільної мети, тобто набір з критеріїв повний, якщо, знаючи значення n-мірного критерію, пов'язаного із загальною метою, ЛПР має повне уявлення про ступінь досягнення спільної мети.

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

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

Ненадлишкових. Критерії повинні бути визначені так, щоб не дублювався облік одних і тих же аспектів розв'язуваної проблеми.

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

Формальні методи формування набору критеріїв запропонувати важко. Вони дуже сильно залежать від досвіду та здатності експертів і, що вкрай важливо, характеру особи, яка приймає рішення.

Схема процесу прийняття рішень

У класичній книзі лауреата нобелівської премії професора Г. Саймона «The New Science of Management Decision», 1960 процес прийняття рішень розбитий на чотири фази: збір інформації (intelligence); пошук і побудова альтернатив (design); вибір альтернатив (choice); оцінка результатів (review). Перша фаза - збір інформації, сконцентрована на ідентифікації проблеми прийняття рішення і зборі всієї доступної інформації про неї. При пошуку і побудові альтернатив (друга фаза) центральним питанням стає визначення щодо невеликого числа альтернатив, які слід вивчити в деталях. На третій фазі відбувається вибір одного з варіантів рішень з безлічі альтернатив, підготовлених на другій фазі. Останній крок у процесі прийняття рішень - це реалізація обраної альтернативи та узагальнення досвіду, отриманого в процесі вирішення проблеми.

Таким чином, саме рішення приймається в рамках другої і третьої фаз:

• конструювання відносно невеликого безлічі альтернатив;

• остаточний вибір варіанта рішення з сформованого множини.

Схематично ці дві фази представлені на малюнку 1. Фази істотно розрізняються як цілями та інформацією, так і методами. На фазі, в якій одним з питань є вибір відносно невеликого числа альтернатив (цю фазу часто називають early screening). ОПР має взяти до уваги всі можливі шляхи досягнення мети. У процесі ж детального аналізу та остаточного вибору альтернативи, ЛПР обмежує себе малим числом підготовлених варіантів рішень. Вибору альтернативи з цього числа передує їх детальне вивчення.

Рис. 1 - Фази процесу прийняття рішень

Класифікація задач прийняття рішень

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

де - Постановка задачі;

- Безліч допустимих альтернативних варіантів;

- Безліч методів вимірювання переваг;

- Безліч методів вимірювання переваг (наприклад, використання різних шкал);

- Відображення множини допустимих альтернатив в безліч критеріальних оцінок;

- Системи переваг експерта;

- Вирішальне правило, що відбиває систему переваг.

Будь-який з елементів цього набору може служити класифікаційною ознакою прийняття рішень.

По виду відображення F. Спроби застосування дослідження операцій для вирішення різного класу задач виявили великі відмінності в природі досліджуваних систем. У зв'язку з цим Г. Саймоном і А. Ньюеллом була запропонована наступна класифікація:

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

2. Слабоструктуровані або змішані проблеми, які містять як якісні, так і кількісні елементи, причому якісні, маловідомі і невизначені сторони мають тенденцію домінувати.

3. Неструктуровані або якісно виражені проблеми, що містять лише опис найважливіших ресурсів, ознак і характеристик, кількісні залежності між якими абсолютно невідомі.

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

Характерними особливостями проблем третього класу є:

1. унікальність вибору в тому сенсі, що кожен раз проблема є новою для ОПР;

2. невизначеність в оцінках альтернативних варіантів рішень проблеми;

3. якісний характер оцінки варіантів вирішення проблеми, найчастіше формульованій у словесній формі;

4. оцінка альтернатив може бути отримана лише на основі суб'єктивних переваг ОПР або ГПР;

5. критеріальні оцінки можуть бути отримані тільки від експертів.

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

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

За постановці завдання Т. Завдання прийняття рішень можна розбити на дві групи:

Завдання першої групи:

Дано: група з альтернатив-варіантів розв'язання проблеми та критеріїв, призначених для оцінки альтернатив, кожна з альтернатив має оцінку по кожному з критеріїв. Потрібно: побудувати вирішальні правила на основі переваг ОПР, що дозволяють: виділити кращу альтернативу; порядок альтернативи за якістю; віднести альтернативи до упорядкованим за якістю класів рішень.

Завдання другої групи:

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

Потрібно: на підставі переваг ОПР побудувати вирішальні правила, що дозволяють: порядок якості всі можливі альтернативи; віднести всі можливі альтернативи до одного з декількох (зазначених ЛПР) класів рішень.

А тепер від теорії прийняття рішень перейдемо до матричних ігор.

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

Гравець А має m стратегій i = 1, 2, ..., m. Гравець В має n стратегій j = 1, 2, ..., n. Кожній парі стратегій (i, j) поставлено у відповідність число а , Що виражає виграш гравця А за рахунок гравця В, якщо перший гравець прийме свою i-ю стратегію, а другий - свою j-ю стратегію.

Кожен з гравців робить один хід: гравець А вибирає свою i-ю стратегію (i = ), В - свою j-ю стратегію (j = ), Після чого гравець А отримує виграш а за рахунок гравця А (якщо а <0, то це означає, що гравець В платить другу суму | а |). На цьому гра закінчується.

Кожна стратегія гравця i = або j = часто називається чистою стратегією.

Якщо розглянути матрицю А:

а	а	...	а	...	а
...	...	...	...	...	...
а	а	...	а	...	а
...	...	...	...	...	...
а	а	...	а	...	а

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

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

Виходячи з цих позицій, гравець А досліджує матрицю виграшів наступним чином: для кожного значення i (i = ) Визначається мінімальне значення виграшу в залежності від застосовуваних стратегій гравця В

а (I = )

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

а = А = Α

1.2 Визначення ігри

Дамо визначення поняттю «Гра». Грою називається набір

,

де N - довільне безліч гравців; S - Довільна безліч всіх результатів гри; X _K - довільна безліч стратегій коаліції K N; S (X ^K) S - безліч можливих результатів, якщо коаліція K застосовує стратегію х ^K Х _K; - Транзитивне відношення переваги коаліції K N на S. При математичної формалізації гра, повинна проходити по певним правилам, які представляють наступну систему умов:

• можливі дії кожного з гравців;

• обсяг інформації, яку може отримати кожна сторона про дії іншого;

• результат гри в результаті кожної сукупності ходів супротивників.

Гравці: Вважається заданим список гравців. Якщо гравців розрізняти за номерами, то їх список зводиться до безлічі , Де - Число гравців. Вважається, що гравці поінформовані про наявність кожного зі своїх партнерів.

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

Інтереси: Ступінь зацікавленості гравця k в тій чи іншій ситуації s визначається розміром виграшу , Який в цій ситуації він може отримати. Таким чином, правила гри виходять завданням так званих, функцій виграшу . Ці функції беруть числові значення і мають загальну область визначення . Кожна з таких функцій є функція «n-змінних»: .

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

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

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

Прикладами ігор такого типу є шахи, в яких немає випадкових ходів (крім розігрування того, хто буде грати білими), бридж, в якому випадок грає велику роль.

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

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

1. чергування ходів, які можуть бути як особистими, так і випадковими

2. можлива недостатність інформації

3. функція виграшу

Запишемо тепер основні етапи пошуку рішення ігри:

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

2. пошук домінуючих стратегій (в разі успіху цього пошуку - відкидання домінуючих рядків і стовпців у вихідній матриці гри).

3. заміна гри на її змішане розширення і пошук оптимальних змішаних стратегій і ціни гри.

Зазначимо, що нормальна форма антагоністичної гри зводиться до деякої матриці А з числом рядків дорівнює кількості стратегій гравця 1 і з числом стовпців, що дорівнює кількості стратегій гравця 2. Виграш - якщо гравець 1 вибирає i-ю стратегію, а гравець 2 j-ю стратегію - є елементом в i-ої рядку і в j-му стовпці даної матриці.

Гравців, як учасників гри, цікавить, які з стратегій є виграшними з точки зору максимізації частки кожного гравця у виграші. Однак, результати випадкових ходів, відомі тільки в вероятностном сенсі, тому краще розглядати математичне сподівання функції виграшу, визначене у випадку, коли гравці використовують n-набір стратегій. Тому для опису математичного сподівання функції виграшу, за умови, що гравець i застосовує стратегію , Можна вжити таке позначення Виходячи з цього функцію на множині всіх можливих значень змінних можна висловити або у формі співвідношення, або у вигляді n-мірної матриці n-векторів. Така n-мірна таблиця називається нормальною формою гри Г. У нормальній (стратегічної) формі гра описується платіжної матрицею. Кожна сторона матриці - це гравець, рядки визначають стратегії першого гравця, а стовпці - другого. На перетині двох стратегій можна побачити виграші, які отримають гравці. На прикладі, якщо гравець 1 вибирає першу стратегію, а другий гравець - другу, то на перетині вийде (1, -1). Це означає, що в результаті ходу гравці втратили по одному очку.

Приклад 1: гра «Орлянка».

Перший гравець ховає монету орлом або решкою ​​вгору, а другий намагається вгадати, як вона захована. Якщо він не вгадує - плата першого одну грошову одиницю, якщо вгадує - перший платить йому одну грошову одиницю. В даній грі кожен гравець має дві стратегії: «орел» і «решка». Безліч ситуацій у грі складається з 4 елементів. У рядках таблиці вказані стратегії першого гравця Х, у стовпцях - стратегії другого гравця Y. Для кожної із ситуацій вказані виграші першого і другого гравців.

Розглянемо основну теорему матричних ігор.

Основна теорема теорії матричних ігор (по Дж. фон Нейманом).

Для матричної гри з будь матрицею А величини і рівні між собою, тобто

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

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

Наведемо доказ даної теореми (автор: Дж. Б. Данциг, 1951р.)

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

. (*)

Коментар. Формула (*) означає, що: якщо гравець 1 відхиляється від своєї оптимальної стратегії, то його виграш не збільшується в порівнянні з ціною гри; якщо від своєї оптимальної стратегії відхиляється гравець 2, то в порівнянні з ціною гри його програш не зменшується.

Доказ.

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

.

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

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

1.3 Класифікація ігор

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

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

1. так звана позиційна форма. При цьому визначаються:

   • порядок ходів

   • альтернативи (можливі ходи), доступні кожному з гравців на момент настання його ходу

   • інформація, якою володіє кожен з гравців на момент чергового ходу

   • виграші (для кожного гравця) як функції від обраних ходів

   • імовірнісні розподілу на безлічі можливих станів зовнішнього середовища

2. нормальна або стратегічна форма. Кожен учасник (гравець) k, де , Характеризується наявністю індивідуальної системи цільових установок і безліччю стратегій , Тобто можливих варіантів дій в грі.

Раніше згадувалося про таке поняття, як «антагоністична гра». Прикладом такої гри може бути гра «Орлянка». Дамо визначення антагоністичної гри.

Антагоністична гра - гра, в якій беруть участь два гравці (зазвичай позначаються I і II) з протилежними інтересами. Для антагоністичної гри характерно, що виграш одного гравця дорівнює програшу іншого і навпаки, тому спільні дії гравців, їх переговори і угоди позбавлені сенсу .. Визначаються антагоністичні ігри завданням множин стратегій гравців і виграшів гравця I в кожній ситуації, що складається у виборі гравцями своїх стратегій. Таким чином, формально антагоністична гра є трійка <А, В, Н>, в якій А і В - безлічі стратегій гравців, а Н (а, b) - речова функція (функція виграшу) від пар (а, b), де а  A, b  В. Гравець I, вибираючи а, прагне максимізувати Н (а, b), а гравець II, вибираючи b, - мінімізувати Н (а, b).

Приклад 2:

Розглянемо гру G (4х5) у матричній формі.

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

Теорема про Мінімакс.

Можна довести, що для будь-якої функції F (x, y) визначеної на довільному декартовому творі X × Y має місце нерівність . Звідси випливає, що

Запишемо 2 твердження:

Твердження 1. Точка 0 (у m-мірному просторі) міститься в опуклій оболонці m + n точок

і

Твердження 2. Існують числа задовольняють умовам

Доказ: Нехай А - матрична гра. Має місце або затвердження 1, або твердження 2. Якщо вірно твердження 1 то 0 є опуклою лінійною комбінацією m + n векторів. Тому існують такі

що

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

тоді можна покласти

і вийде для всіх i

Значить і

Припустимо, що вірно твердження 2. Тоді , Так що . Отже, нерівність не має сенсу. Припустимо, що гра А змінена на гру , Де . Для будь-яких х і y , Тому . Так як нерівність не має сенсу, то нерівність також не виконується. Але k довільно. Значить нерівність неможливо. Т.к. то . Що й треба було довести.

Принцип Мінімакс.

Розглянемо гру з платіжною матрицею Слід визначити найкращу стратегію гравця I серед стратегій , і гравця II серед стратегій , . Визначення найкращих стратегій гравців засноване на принципі, який передбачає, що противники, які беруть участь у грі, однаково розумні і кожен з них робить все для того, щоб досягти своєї мети. Знайдемо найкращу стратегію гравця I. Припустимо, що він вибрав i-ю стратегію (i-й рядок матриці (1)). Тоді він отримає менше, ніж - Найменше число в цьому рядку. Причому це буде в тому випадку, якщо гравець II якимось чином розкриє стратегію гравця I. Зі сказаного випливає, що I гравець, якщо він не бажає ризикувати, тобто грати не оптимально, повинен діяти таким чином - визначити найменші елементи всіх рядків і вибрати ту з них, в якій це число найбільше. У цьому випадку він гарантує собі виграш рівний найбільшому з менших чисел всіх рядків. Цей виграш дорівнює Число це "низький виграш" гравця I і його називають нижнім значенням або нижньої ціною гри. Як же міркує другий гравець? "Якщо я виберу j-у стратегію (j-ий стовпчик), то найкращий виграш у гравця I буде найбільше число цього стовпця. Щоб ризикувати, я повинен вибрати стовпець, в якому це число найменше. У результаті I гравець не зможе отримати більше, ніж Число являє собою "верхній виграш" гравця I і називається верхнім значення або верхньої ціною гри. Можна показати, що для всякої матричної гри виконується умова . Якщо , То такі ігри називаються іграми з сідлової крапкою. З нерівності випливає, що . Це фактично означає, гравець I міг би розраховувати на виграш .

1.4 Матричні ігри

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

	н / ч	ч
н / ч	1	-1
ч	-1	1

Почнемо безпосередньо з матричних ігор. Трійка (Де x і y - множини, H - функція від двох змінних ) Називається антагоністичною грою. Процес розігрування кінцевої антагоністичної гри (гра називається кінцевою, якщо трійка кінцева) полягає в тому, що гравці 1 і 2 незалежно один від одного обирають відповідно деякі чисті стратегії x і y, в результаті чого складається ситуація (x, y).

Ми знаємо, що антагоністичну гру двох учасників з нульовою сумою (нагадаємо, що нульова сума - це коли виграш одного гравця дорівнює програшу іншого) зручно задавати з допомогою, так званої платіжної матриці. Кожен елемент такої матриці містить числове значення виграшу гравця 1 (або програшу гравця 2) у ситуації, коли перший гравець застосовує стратегію i, а другий - стратегію j. Класичним прикладом антагоністичної гри є гра з двома учасниками, які незалежно один від одного загадують числа. Передбачається, що якщо сума виявляється парною, то виграш рівний 1, дістається першого гравця, а якщо непарної, то другого. Якщо припустити, що загадування непарного числа - стратегія першого гравця, а загадування парного числа - стратегія другого гравця, то платіжна матриця виглядає наступним чином:

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

Теорема про принцип максимина.

Для з (Де - Безлічі чистих стратегій гравців, (х, у) - ситуація ігри - Функції корисності гравців, задані на множині ситуацій ігри аналітично ) Загального виду

.

Доказ.

Для

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

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

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

Перший гравець має m страте6гій i = 1,2, ... m, другий має n стратегій j = 1,2, ... n. Кожній парі стратегій (i, j) поставлено відповідно число a , Що виражає виграш гравця 1 за рахунок гравця 2, якщо перший гравець візьме свою i-ю стратегію, а 2-у j-ю стратегію.

Кожен з гравців робить один хід: гравець 1 вибирає свою i-ю стратегію (i = ), 2 - свою j-ю стратегію (j = ) Після чого гравець 1 отримує виграш a за рахунок гравця 2 (якщо a <0, то це означає, що гравець 1 платить другу суму a ). На цьому гра закінчується.

Кожна стратегія гравця i = ; J = часто називається чистою стратегією.

Якщо розглянути матрицю

то проведення кожної партії матричної гри з матрицею А зводиться до вибору гравців 1 i - рядки, а гравець 2 j-го стовпця і одержання гравцем 1 (за рахунок гравця 2) виграшу a .

Головним у дослідженні ігор є поняття оптимальних стратегій гравців. У це поняття вкладається наступний сенс: забезпечується найбільший гарантований виграш при всіляких стратегіях іншого гравця. Виходячи з цих позицій, гравець 1 досліджує матрицю виграшів А наступним чином: для кожного значення i (i = ) Визначається мінімальне значення виграшу в залежності від застосовуваних стратегій гравця 2

min a (I = )

j

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

max min a = A = (1)

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

Гравець 2 при оптимальному своїй поведінці повинен прагнути по можливості за рахунок своїх стратегій максимально зменшити виграш гравця 1. Тому для гравця 2 відшукується

max a

i

тобто визначається max виграш гравця 1, за умови, що гравець 2 застосує свою j-ю чисту стратегію, потім гравець 2 відшукує свою j = j стратегію, при якій гравець 1 отримає min виграш, тобто знаходить

min max a = A = (2)

ji

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

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

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

ПРИКЛАД 3: Провести SP-розбиття матриці гри (Н)

X1	2	3	4	5
X2	1	4	0	5
X3	1	0	6	7
X4	1	2	3	4
	Y1	Y2	Y3	Y4