Рішення антагоністичної гри. Рішення матричної гри
Вступ
Реальні конфліктні ситуації призводять до різних видів ігор. Ігри розрізняються за цілою низкою ознак: за кількістю гравців, що беруть участь в них, за кількістю можливих гравців, за кількістю можливих стратегій, за характером взаємин між гравцями, за характером виграшів, за видом функцій виграшів, за кількістю ходів, за характером інформаційної забезпеченості гравців і т.д. .д. Розглянемо види ігор залежно від їхнього розбиття:
· За кількістю стратегій гри діляться на кінцеві(кожен із гравців має кінцеву кількість можливих стратегій) і нескінченні(де хоча один із гравців має нескінченну кількість можливих стратегій).
· За характером виграшів розрізняють ігри з нульовою сумою(загальний капітал гравців не змінюється, а перерозподіляється між гравцями в залежності від результатів, що виходять) і гри з ненульовою сумою.
· За видом функцій виграші гри діляться на матричні (це кінцева гра двох гравців з нульовою сумою, в якій задається виграш гравця Ау вигляді матриці (рядок матриці відповідає номеру стратегії гравця, що застосовується) У, стовпець – номер застосовуваної стратегії гравця У; на перетині рядка та стовпця матриці знаходиться виграш гравця А, що відповідає застосовуваним стратегіям.
Для матричних ігор доведено, що будь-яка з них має рішення, і воно може бути легко знайдено шляхом зведення гри до задачі лінійного програмування), біматричніігри (це кінцева гра двох гравців з ненульовою сумою, в якій виграші кожного гравця задаються матрицями окремо для відповідного гравця (у кожній матриці рядок відповідає стратегії гравця) А, стовпець – стратегії гравця У, на перетині рядка та стовпця у першій матриці знаходиться виграш гравця А, у другій матриці – виграш гравця У.
Для біматричних ігор також розроблено теорію оптимальної поведінки гравців, проте вирішувати такі ігри складніше, ніж звичайні матричні безперервніігри ( Безперервнийвважається гра, у якій функція виграшів кожного гравця є безперервною залежно від стратегій. Доведено, що ігри цього класу мають рішення, проте не розроблено практично прийнятних методів їх знаходження) тощо.
Можливі також інші підходи до розбиття ігор. Тепер повернемося безпосередньо до теми дослідження, саме до Теорії ігор. Для початку дамо визначення цього поняття.
Теорія ігор - Розділ математики, що вивчає формальні моделі прийняття оптимальних рішень в умовах конфлікту. При цьому під конфліктом розуміється явище, в якому беруть участь різні сторони, наділені різними інтересами та можливостями вибирати доступні для них дії відповідно до цих інтересів. В умовах конфлікту прагнення противника приховати свої майбутні дії породжує невизначеність. Навпаки, невизначеність при ухваленні рішень (наприклад, на основі недостатніх даних) можна інтерпретувати як конфлікт приймаючого рішення суб'єкта з природою. Тому теорія ігор розглядається також як теорія прийняття оптимальних рішень в умовах невизначеності. Вона дозволяє систематизувати деякі важливі аспекти прийняття рішень у техніці, сільському господарстві, медицині та соціології та інших науках. Сторони, що беруть участь у конфлікті, називаються коаліціями дії; доступні їм дії - їх стратегіями; можливі наслідки конфлікту – ситуаціями.
Завдання теорії полягає в тому, що:
1) оптимальною поведінкою у грі.
2) дослідження властивостей оптимальної поведінки
3) визначення умов, за яких його використання осмислене (питання існування, єдиності, а для динамічних ігор та питання іменної спроможності).
4) побудова чисельних методів знаходження оптимальної поведінки.
Теорія ігор, створена для математичного рішеннязадач економічного та соціального походження, не може в ціломузводитися до класичних математичних теорій, створених для вирішення фізичних та технічних завдань. Однак у різних конкретних питаннях теорія ігор широко використовуються різноманітні класичні математичні методи.
Крім цього, теорія ігор пов'язана з низкою математичних дисциплін внутрішнім чином. Теоретично ігор систематично і з суті використовуються поняття теорії ймовірностей. На мові теорії ігор можна сформулювати більшість завдань математичної статистики, і оскільки теорія ігор, пов'язана з теорією прийняття рішень, вона розглядається як істотна складова частинаматематичного апарату дослідження операцій.
Математичне поняття гри надзвичайно широко. Воно включає так звані салонні ігри (у тому числі шахи, шашки, гра ГО, карточні ігри, доміно), але може використовуватися і для опису моделей економічної системиз численними покупцями і продавцями, що конкурують один з одним. Не вдаючись у деталі, гру в загальних рисах можна визначити як ситуацію, в якій одна або кілька осіб («гравців») спільно управляють деякою кількістю змінних і кожен гравець, приймаючи рішення, повинен враховувати дії всієї групи. «Платіж», що припадає на частку кожного гравця, визначається не лише його власними діями, а й діями інших членів групи. Деякі з «ходів» (індивідуальних дій) під час гри можуть мати випадковий характер. Наочною ілюстрацією може служити відома грав покер: початкова здача карт є випадковим ходом. Послідовність ставок і контрставок, що передує фінальному порівнянню хабарів, утворена рештою ходів у грі.
Математична ТЕОРІЯ ІГР розпочалася з аналізу спортивних, карткових та інших ігор. Розповідають, що першовідкривач теорії ігор, видатний американський математик XX ст. Джон фон Нейман прийшов до ідеї своєї теорії, спостерігаючи за грою в покер. Звідси і походить назва «теорія ігор».
Почнемо дослідження даної теми з ретроспективного аналізу розвитку теорії гр.Розглянемо історію та розвиток питання теорії ігор. Зазвичай «генеалогічне дерево» представляється як дерева у сенсі теорії графів, у яких розгалуження походить від деякого єдиного «кореня». Родовід теорії ігор - книга Дж. фон Неймана та О. Моргенштерна. Тому історичний хід розвитку теорії ігор як математичної дисципліни, природно розчленовується на три етапи:
Перший етап- До появи монографії Дж. фон Неймана і О. Моргенштерна. Його можна назвати "до монографічним". На цьому етапі гра виступає поки що як конкретне змагання, що описується своїми правилами змістовних термінах. Лише наприкінці його Дж. фон Нейман виробляє уявлення про гру як загальну модель абстрактного конфлікту. Підсумком цього етапу стало накопичення низки конкретних математичних результатів і навіть окремих принципів майбутньої теорії ігор.
Другий етапскладає сама монографія Дж. фон Неймана та
О. Моргенштерна «Теорія ігор та економічна поведінка» (1944), що об'єднала у собі більшість раніше отриманих (втім, за сучасними математичними масштабами досить нечисленних) результатів. Вона вперше представила математичний підхід до ігор (як у конкретному, так і абстрактному розумінні цього слова) у вигляді систематичної теорії.
Зрештою, на третьому етапітеорія ігор у своєму підході до об'єктів, що вивчаються, мало, чим відрізняється від інших розділів математики і розвивається значною мірою за спільними з ними закономірностями. У цьому, очевидно, значний вплив формування напрямів теорії ігор надає специфіка її практичних додатків, як фактичних, і можливих.
Проте навіть математична теорія ігор неспроможна повністю визначити результат деяких конфліктів. Можливо виділити три основні причини невизначеності результату гри (конфлікту).
По-перше, це ігри, в яких є реальна можливістьдослідження всіх або, принаймні, більшості варіантів ігрової поведінки з них однієї найбільш істинної, яка веде до виграшу. Невизначеність викликана значною кількістю варіантів, тому не завжди можливим досліджувати абсолютно всі варіанти (наприклад, японська гра ГО, російські і міжнародні шашки, британські реверс).
По-друге, непрогнозований гравцями, випадковий вплив факторів на гру. Ці фактори надають вирішальний вплив на результат гри і лише малою мірою можуть бути або взагалі не можуть бути контрольованими та визначеними граючими. Остаточний результат гри лише малою, вкрай незначною мірою визначається самими діями гравців. Ігри, результат яких виявляється невизначеним через випадкові причини, називаються азартними. Результат гри завжди має імовірнісний або ймовірний характер (рулетка, гра в кістки, гра в «орлянку»).
По-третє, невизначеність викликана відсутністю інформації про те, якої саме стратегії дотримується противник, що грає. Незнання гравців про поведінку суперника має принциповий характер і визначається самими правилами гри. Такі ігри називаються стратегічними.
Теорія ігор одна із важливих розділів «Дослідження операцій» і є теоретичні основи математичних моделей прийняття оптимальних рішень у конфліктних ситуаціях ринкових відносин, які мають характер конкурентної боротьби, у яких одна протиборча сторона виграє в інший з допомогою програшу інший. Поряд із такою ситуацією в рамках науки «Дослідження операцій», яка надає математичний опис постановок різних завдань щодо прийняття рішень, розглядаються ситуації ризику та невизначеності. У ситуації невизначеності ймовірності умов невідомі і немає можливості отримати про них додаткову статистичну інформацію. Навколишнє вирішення завдання середовище, яке проявляється в тих чи інших умовах, називається «природою», а відповідні математичні моделі називаються «іграми з природою» або «теорією статистичних ігор». Основною метою теорії ігор є вироблення рекомендацій для задовільного поведінки гравців у конфлікті, тобто виявлення кожному з них «оптимальної стратегії».
Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.
Вступ
1. Теоретична частина
1.3 Гра порядку 2х2
1.4 Алгебраїчний метод
1.5 Графічний метод
1.6 Ігри 2xn або mx2
1.7 Рішення ігор матричним методом
2. Практична частина
2.2 Ігри 2xn та mx2
2.3 Матричний метод
2.4 Метод Брауна
Аналіз результатів
Вступ
Антагоністична гра – це гра з нульовою сумою. Антагоністичною грою називається некооперативна гра, в якій беруть участь два гравці, виграші яких протилежні.
Формально антагоністична гра може бути представлена трійкою
Оскільки інтереси гравців є протилежними, функція F одночасно представляє і програш другого гравця.
Історично антагоністичні ігри є першим класом математичних моделей теорії ігор, за допомогою яких описувалися азартні ігри. Вважається, що завдяки цьому предмету дослідження теорія ігор отримала свою назву. В даний час антагоністичні ігри розглядаються як частина ширшого класу некооперативних ігор.
1. Теоретична частина
1.1 Основні визначення та положення гри
Гра характеризується системою правил, що визначають кількість учасників гри, їх можливі дії та розподіл виграшів залежно від їхньої поведінки та наслідків. Гравцем прийнято вважати одного учасника або групу учасників гри, які мають одні спільні для них інтереси, що не збігаються з інтересами інших груп. Тож не кожен учасник вважається гравцем.
Правила чи умови гри визначають можливі поведінки, вибори та ходи для гравців на будь-якому етапі розвитку гри. Зробити вибір гравцеві, це означає зупинитися на одній із його можливостей поведінки. Потім гравець здійснює цей вибір за допомогою ходів. Зробити хід - це означає певному етапі гри здійснити відразу весь вибір чи його частина залежно від можливостей, передбачених правилами гри. Кожен гравець на певному етапі гри робить хід згідно зробленого вибору. Інший гравець, знаючи чи не знаючи про вибір першого гравця, також робить хід. Кожен із гравців намагається врахувати інформацію про минулий розвиток гри, якщо така можливість дозволяється правилами гри.
Набір правил, які однозначно вказують гравцю, який вибір він повинен зробити при кожному ході в залежності від ситуації, що склалася в результаті гри, називається стратегією гравця. Стратегія теорії ігор означає певний закінчений план дій гравця, показує, як треба діяти йому у всіх можливих випадках розвитку гри. Стратегія означає сукупність всіх вказівок для будь-якого стану інформації, що є у гравця будь-якому етапі розвитку гри. Звідси вже видно, що стратегії можуть бути хорошими та поганими, вдалими та невдалими тощо.
Гра з нульовою сумою буде тоді, коли сума виграшів усіх гравців у кожній її партії дорівнює нулю, тобто у грі з нульовою сумою загальний капітал усіх гравців не змінюється, а перерозподіляється між гравцями в залежності від результатів, що виходять. Так, багато економічних та військових ситуацій можна розглядати як ігри з нульовою сумою.
Зокрема гра двох гравців із нульовою сумою називається антагоністичною, оскільки цілі гравців у ній прямо протилежні: виграш одного гравця відбувається лише за рахунок програшу іншого.
1.1.1 Визначення, приклади та рішення матричних ігор у чистих стратегіях
Матрична гра двох гравців із нульовою сумою може розглядатися як наступна абстрактна гра двох гравців.
Перший гравець має т стратегій i = 1, 2, ..., т, другий має п стратегій j = 1, 2, ..., п. Кожній парі стратегій (i, j) поставлено у відповідність число a ij , що виражає виграш першого гравця за рахунок другого гравця, якщо перший гравець застосує свою i-ю стратегію, а другий - свою j-ю стратегію.
Кожен із гравців робить один хід: перший гравець вибирає свою i-ю стратегію (i = 1, 2, ..., т), другий -свою j-юстратегію (j = 1, 2, ..., п), після чого перший гравець отримує виграш a ij за рахунок другого гравця (якщо a ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.
Кожна стратегія гравця i = 1, 2, ... т; j = 1, 2, ..., п часто називається чистою стратегією.
Матрична гра двох гравців із нульовою сумою далі називатиметься просто матричною грою. Очевидно, матрична гра відноситься до антагоністичних ігор. З її визначення випливає, що для завдання матричної гри достатньо встановити матрицю А = (a ij) порядку тп виграшів першого гравця.
Якщо розглянути матрицю виграшів
то проведення кожної партії матричної гри з матрицею А зводиться до вибору першим гравцем i-йрядка, а другим гравцем j-го стовпця та отримання першим гравцем (за рахунок другого) виграшу, що знаходиться в матриці А на перетині i-го рядка та j-го стовпця.
Для формалізації реальної конфліктної ситуації у вигляді матричної гри треба виділити та перенумерувати чисті стратегії кожного гравця та скласти матрицю виграшів.
Наступний етап - це визначення оптимальних стратегій та виграшів гравців.
Головним у дослідженні ігор поняття оптимальних стратегій гравців. У це поняття інтуїтивно вкладається такий зміст: стратегія гравця є оптимальною, якщо застосування цієї стратегії забезпечує йому найбільший гарантований виграш за всіляких стратегій іншого гравця. Виходячи з цих позицій, перший гравець досліджує матрицю А своїх виграшів за формулою (1.1) наступним чином: для кожного значення i (i = 1, 2, ..., т) визначається мінімальне значення виграшу в залежності від стратегій другого гравця, що застосовуються.
(i = 1, 2, ..., m) (1.2)
тобто визначається мінімальний виграш для першого гравця за умови, що він застосує свою i - ю чисту стратегію, потім із цих мінімальних виграшів відшукується така стратегія i = i 0, при якій цей мінімальний виграш буде максимальним, тобто знаходиться
Визначення. Число б, визначене за формулою (1.3), називається нижньою чистою ціною гри і показує, який мінімальний виграш може гарантувати собі перший гравець, застосовуючи свої чисті стратегії при дії другого гравця.
Другий гравець за оптимальної своєї поведінки повинен прагнути по можливості за рахунок своїх стратегій максимально зменшити виграш першого гравця. Тому для другого гравця відшукується
тобто визначається максимальний виграш першого гравця, за умови, що другий гравець застосує свою j-ю чистустратегію, потім другий гравець відшукує таку свою j = j 1 стратегію, при якій перший гравець отримає мінімальний виграш, тобто знаходить
Визначення. Число, визначене за формулою (1.5), називається чистою верхньою ціною гри і показує, який максимальний виграш за рахунок своїх стратегій може гарантувати собі перший гравець. Іншими словами, застосовуючи свої чисті стратегії, перший гравець може забезпечити собі виграш не менше б, а другий гравець за рахунок застосування своїх чистих стратегій може не допускати виграш першого гравця більше, ніж в.
Визначення. Якщо у грі з матрицею А нижня та верхня чисті ціни гри збігаються, тобто б = в, то кажуть, що ця гра має сідлову точку в чистих стратегіях і чисту ціну гри:
н = б = (1.6)
Сідлова точка - це пара чистих стратегій () відповідно першого і другого гравців, при яких досягається рівність
У поняття сідлової точки вкладено наступний зміст: якщо один із гравців дотримується стратегії, що відповідає сідловій точці, то інший гравець не зможе вчинити краще, ніж дотримуватися стратегії, що відповідає сідловій точці. Маючи на увазі, що найкраща поведінка гравця не повинна призводити до зменшення його виграшу, а найгірше - може призводити до зменшення його виграшу, ці умови можна записати математично у вигляді наступних співвідношень:
де i, j - будь-які чисті стратегії відповідно першого та другого гравців; (i 0, j 0) - стратегії, що утворюють сідлову точку. Нижче буде показано еквівалентність визначення сідлової точки умов (1.8).
Таким чином, виходячи з (1.8), сідловий елемент є мінімальним в i 0 -му рядку і максимальним в j 0 -му стовпці в матриці А. Відшукування сідлової точки матриці А відбувається легко: в матриці А послідовно в кожному рядку знаходять мінімальний елемент і перевіряють, чи є цей елемент максимальним у своєму стовпчику. Якщо він є таким, то він і є сідловий елемент, а пара стратегій, що відповідає йому, утворює сідлову точку. Пара чистих стратегій (i 0 , j 0) першого та другого гравців, що утворює сідлову точку та сідловий елемент називається рішенням гри.
Чисті стратегії i 0 і j 0 утворюють сідлову точку називаються оптимальними чистими стратегіями відповідно першого і другого гравців.
Теорема 1. Нехай f (х, у) речова функція двох змінних х А і у В і існує
тоді б = в.
Доведення. З визначення мінімуму та максимуму випливає, що
Оскільки в лівій частині (1.11) х будь-яке, то
У правій частині нерівності (1.12) будь-яке, тому
що й потрібно було довести.
Зокрема, матриця () є окремим випадком функції f (х, у), тобто якщо покласти х = i, у = j, = f (х, у), то з теореми 1 отримаємо, що нижня чиста ціна не перевершує верхню чисту ціну гри в матричній грі.
Визначення. Нехай f (х, у) дійсна функція двох змінних х А і у В. Точка (х 0 , у 0) називається сідловою для функції f (х, у), якщо виконуються такі нерівності
f (х, у 0) f (х 0, у 0) f (х 0, у) (1.14)
за будь-яких х А і у Ст.
1.2 Оптимальні змішані стратегії та їх властивості
Дослідження матричної гри починається з знаходження її сідлової точки у чистих стратегіях. Якщо матрична гра має сідлову точку у чистих стратегіях, то знаходженням цієї точки закінчується дослідження гри. Якщо ж у матричній грі немає сідлової точки в чистих стратегіях, то можна знайти нижню та верхню чисті ціни цієї гри, які вказують, що перший гравець не повинен сподіватися на більший виграш, ніж верхня ціна гри, і може бути впевнений в отриманні виграшу не менше нижньої ціни гри. Такі рекомендації щодо поведінки гравців у матричній грі без сідлової точки у чистих стратегіях не можуть задовольняти дослідників та практичних працівників. Поліпшення рішень матричних ігор слід шукати у використанні секретності застосування чистих стратегій та можливості багаторазового повторення ігор у вигляді партій. Так, наприклад, проводиться серія ігор у шахи, шашки, футбол, і щоразу гравці застосовують свої стратегії таким чином, що їхні противники не здогадуються про їх зміст, і на цьому шляху в середньому досягають певних виграшів, зігравши всю серію партій. Ці виграші в середньому більше нижньої ціни гри та менше верхньої ціни гри. Чим більше це середнє значення, тим краще стратегіїзастосовує гравець. Тому виникла ідея застосовувати чисті стратегії випадково, з певною ймовірністю. Це повністю забезпечує таємність їх застосування. Кожен гравець може змінювати ймовірність застосування своїх чистих стратегій таким чином, щоб максимально збільшити свій середній виграш і на цьому шляху отримувати оптимальні стратегії. Така ідея спричинила поняття змішаної стратегії.
Визначення. Змішаною стратегією гравця називається повний набірймовірності застосування його чистих стратегій.
Таким чином, якщо перший гравець має т чистих стратегій 1, 2, ... i, ... m, то його змішана стратегія х - це набір чисел х = (х 1, х 2, ..., х i, ..., х т ) задовольняють співвідношенням
x i 0 (i = 1, 2, ..., т), = 1. (1.15)
Аналогічно для другого гравця, який має п чистих стратегій, змішана стратегія у - це набір чисел у = (у 1, ..., у j, ... у n), що задовольняють співвідношенням
y j 0 (j = 1, 2, ..., n), = 1. (1.16)
Оскільки щоразу застосування гравцем однієї чистої стратегії унеможливлює застосування іншої, то чисті стратегії є несумісними подіями. Крім того, вони є єдиними можливими подіями.
Очевидно, чиста стратегія є окремим випадком змішаної стратегії. Справді, якщо у змішаній стратегії будь-яка i-я чистаСтратегія застосовується з ймовірністю одиниця, то всі інші чисті стратегії не застосовуються. І ця перша чиста стратегія є окремим випадком змішаної стратегії. Для секретності кожен гравець застосовує свої стратегії незалежно від вибору іншого гравця.
Визначення. Середній виграш першого гравця у матричній грі з матрицею А виражається у вигляді математичного очікування його виграшів
Е (А, х, у) = (1.20)
Очевидно, середній виграш першого гравця є функція двох наборів змінних х та у. Перший гравець має на меті за рахунок зміни своїх змішаних стратегій х максимально збільшити свій середній виграш Е (А, х, у), а другий - за рахунок своїх змішаних стратегій прагне зробити Е (А, х, у) мінімальним, тобто. для вирішення гри необхідно знайти такі х, у яких досягається верхня ціна гри.
1.3 Гра порядку 22
Матрична гра порядку 22 задається наступною матрицею виграшів першого гравця:
Вирішення цієї гри слід починати з відшукання сідлової точки в чистих стратегіях. З цією метою знаходять мінімальний елемент у першому рядку та перевіряють, чи є він максимальним у своєму стовпці. Якщо такого елемента не знайшли, аналогічно перевіряють другий рядок. Якщо у другому рядку такий елемент знайдено, він є сідловим.
Відшуканням сідлового елемента, якщо такої є, закінчується процес знаходження її рішення, оскільки в цьому випадку знайдена ціна гри - сідловий елемент і сідлова точка, тобто пара чистих стратегій, для першого та другого гравця, що становлять оптимальні чисті стратегії. Якщо ж сідлової точки в чистих стратегіях не виявилося, то треба знайти сідлову точку в змішаних стратегіях, яка обов'язково існує згідно з основною теоремою матричних ігор.
Позначимо через х = (х 1, х 2), у = (у 1, у 2) змішані стратегії відповідно першого і другого гравців. Нагадаємо, що х 1 означає ймовірність застосування першим гравцем своєї першої стратегії, а х 2 = 1 – х 1 – ймовірність застосування ним своєї другої стратегії. Аналогічно для другого гравця: у 1 – ймовірність застосування ним першої стратегії, у 2 = 1 – у 1 – ймовірність застосування ним другої стратегії.
Відповідно до слідства з теореми, для оптимальності змішаних стратегій х і у необхідно і достатньо, щоб для невід'ємних х 1, х 2, у 1, у 2 виконувались такі співвідношення:
Покажемо тепер, що якщо матрична гра не має сідлової точки в чистих стратегіях, то ці нерівності повинні перетворюватися на рівність:
Справді. Нехай гра не має сідлової точки в чистих стратегіях, тоді оптимальні значення змішаних стратегій задовольняють нерівності
0<<1, 0<< 1,
0< <1, 01. (1.25)
Припустимо, що обидві нерівності з (1.22) будуть суворими
тоді згідно з теоремою має у 1 = у 2 = 0, що суперечить умовам (1.25).
Аналогічно доводиться, що обидві нерівності з (1.23) не можуть бути суворими нерівностями.
Припустимо тепер, що одне з нерівностей (1.22) може бути суворим, наприклад перше
Це означає, що згідно з теоремою у 1 = 0, у 2 =1. Отже, з (1.23) отримуємо
Якщо обидві нерівності (1.24) суворі, то по теоремі має бути х 1 = х 2 = 0, що суперечить (1.25). Якщо ж а 12 а 22 то одна з нерівностей (1.27) суворе, а інше - рівність. Причому рівність буде виконуватися для більшого елемента а 12 і а 22 , тобто одна нерівність з (1.27) має бути суворим. Наприклад, а 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.
Таким чином, показано, що якщо матрична гра не має сідлової точки в чистих стратегіях, то для оптимальних стратегій першого гравця нерівності (1.22) перетворюються на рівності. Аналогічні міркування щодо нерівностей (1.23) призведуть до того, що в цьому випадку нерівності (1.23) мають бути рівними.
Отже, якщо матрична гра порядку 22 не має сідлової точки, оптимальні змішані стратегії гравців і ціну гри можна визначити, вирішивши систему рівнянь (1.24). Встановлено також, що якщо в матричній грі близько 2x2 один із гравців має оптимальну чисту стратегію, то інший гравець також має оптимальну чисту стратегію.
Отже, якщо матрична гра не має сідлової точки в чистих стратегіях, вона повинна мати рішення в змішаних стратегіях, які визначаються з рівнянь (1.24). Рішення системи (1.25)
1.4 Алгебраїчний метод
Можливі два випадки для вирішення задач методом алгебри:
1. матриця має сідлову точку;
2. матриця немає сідлову точку.
У першому випадку рішення - це пара стратегій, що утворюють сідлову точку гри. Розглянемо другий випадок. Рішення тут слід шукати у змішаних стратегіях:
Знайдемо стратегії в. При використанні першим гравцем своєї оптимальної стратегії другий гравець може, наприклад, застосувати дві такі чисті стратегії
При цьому в силу якості, якщо один з гравців застосовує оптимальну змішану стратегію, а інший - будь-яку чисту, що входить до його оптимальної змішаної стратегії з ймовірністю, що не дорівнює нулю, то математичне очікування виграшу завжди залишається незмінним і рівним ціні гри, тобто.
Виграш повинен у кожному з цих випадків дорівнювати ціні гри V. У такому випадку справедливі такі співвідношення:
Систему рівнянь, аналогічну (2.5), (2.6), можна скласти і для оптимальної стратегії другого гравця:
Беручи до уваги умову нормування:
Вирішимо спільно рівняння (1.37) - (1.41) щодо невідомих можна вирішувати і не всі відразу, а по три: окремо (1.36), (1.38), (1.40) та (1.37), (1.39), (1.41). В результаті рішення отримаємо:
1.5 Графічний метод
Наближене рішення 22 гри можна досить просто отримати скориставшись графічним методом. Суть його полягає в наступному:
Малюнок 1.1-знаходження ділянки одиничної довжини
Виділити на осі абсцис ділянку одиничної довжини. Лівий кінець його зображатиме першу стратегію першого гравця, а праву другу. Усі проміжні точки відповідають змішаним стратегіям першого гравця, причому довжина відрізка праворуч від точки дорівнює ймовірності застосування першої стратегії, а довжина відрізка ліворуч - ймовірності застосування другої стратегії першим гравцем.
Проведено дві осі І-І та ІІ-ІІ. На I-I відкладатимемо виграш при використанні першим гравцем першої стратегії, на II-II при використанні ним другої стратегії. Нехай, наприклад, другий гравець застосував свою першу стратегію, тоді осі I-I слід відкласти величину, але в осі II-II - величину
За будь-якої змішаної стратегії першого гравця його виграш визначиться величиною відрізка. Лінія I-I відповідає застосуванню першої стратегії другим гравцем, називатимемо її першою стратегією другого гравця. Аналогічно можна збудувати і другу стратегію другого гравця. Тоді в цілому графічне відображення матриці гри набуде такого вигляду:
Малюнок 1.2 - знаходження ціни гри
Слід зазначити, що це побудова проводилося першого гравця. Тут довжина відрізка дорівнює ціні гри V.
Лінія 1N2 називається нижньою межею виграшу. Тут видно, що точка N відповідає максимальній величині гарантованого виграшу першого гравця.
Взагалі, стратегію другого гравця також можна визначити з цього малюнка, наприклад такими способами. На осі І-І:
або на осі II-II
Однак стратегію другого гравця можна визначити і аналогічно до того, як це робиться для першого гравця, тобто. побудувати такий графік.
Рисунок 1.3 – визначення стратегії другого гравця
Тут лінія 1N2 – верхня межа програшу. Точка N відповідає мінімальному з можливих програшів другого гравця, вона й визначає стратегію.
Залежно від конкретних значень коефіцієнтів матриці графіка можуть мати інший вигляд, наприклад, такий:
Малюнок 1.4 – визначає оптимальну стратегіюпершого гравця
У такій ситуації оптимальна стратегія першого гравця є чистою.
1.6 Ігри 2n або m2
У іграх порядку 2n перший гравець має 2 чисті стратегії, а другий n чисті стратегії, тобто. матриця виграшів першого гравця має вигляд:
Якщо така гра має сідлову точку, її легко знайти і отримати рішення.
Припустимо, що гра має сідлові точки. Тоді необхідно знайти такі змішані стратегії і відповідно першого та другого гравців та ціну гри v, які задовольняють співвідношенням:
Оскільки гра не має сідлової точки, то нерівність (1.54) замінюють не рівностями
Для вирішення систем (1.56), (1.55), (1.53) доцільно скористатися графічним методом. Для цього введемо позначення для лівої частини нерівності (1.53)
матричний гра математичний модель
або, поставивши з (1.55) і провівши прості перетворення, отримаємо
де - це середній виграш першого гравця за умови, що він застосовує свою змішану стратегію, а другий - свою j-ю чисту стратегію.
Кожному значенню j=1, 2, … n відповідно до виразу відповідає пряма лінія в прямокутній системі координат.
Ціль другого гравця мінімізувати виграш першого гравця за рахунок вибору своїх стратегій. Тому обчислюємо
де - нижня межа безлічі обмежень. На малюнку 1.6 графік функції зображено жирною лінією.
Розміщено на http://www.allbest.ru/
Рисунок 1.6 – графік функції
Мета першого гравця максимізувати власний виграш з допомогою вибору, тобто. обчислити
На малюнку 1.6 точка означає максимальне значення, що виходить при. Ціна гри, оскільки:
Таким чином, графічно визначається оптимальна змішана стратегія першого гравця і пара чистих стратегій другого гравця, які у перетині утворюють точку. Для таких стратегій нерівності (1.53) перетворюються на рівність. На малюнку 1.6 це стратегії j=2, j=3.
Тепер можна вирішити систему рівнянь
і точно визначити значення (графічно вони визначаються приблизно). Потім поклавши всі значення при тих j, для яких не утворюють точку, вирішуючи систему рівнянь (1.56).
а решту Цю систему можна вирішити, покладаючи Якщо при деякій j=j 0 стратегії другого гравця утворюють точку М 0 і то максимальне значення нижньої межі множини обмежень зображується відрізком, паралельним осі У цьому випадку перший гравець має нескінченно багато оптимальних значень а ціна гри зображений малюнку 1.7, де і відрізок MN зображують верхнє обмежень, оптимальні значення перебувають у межах У другого гравця є чиста оптимальна стратегія j=j 0 .
Матричні ігри порядку m2 вирішуються також з допомогою графічного способу. Матриця виграшів першого гравця у цьому випадку має вигляд
Змішані стратегії відповідно до першого і другого гравців визначаються аналогічно, як у випадку ігор порядку 2n. Нехай по горизонтальній осі відкладається значення від 0 до 1, по вертикальній - значення середнього виграшу першого гравця за умов, що перший гравець застосовує свою чисту i-ю стратегію (i=1, 2, …, m), другий - свою змішану стратегію (y 1, 1-y 1) = y. Наприклад, при m=4 можуть бути представлені так, як зображено на малюнку 1.7.
Малюнок 1.7 – графік функції)
Перший гравець намагається максимізувати свій середній виграш, тому він прагне знайти
Функція зображена жирною лінією і є верхню межу безлічі обмежень. Другий гравець намагається мінімізувати з допомогою вибору своєї стратегії, тобто. величина відповідає
На малюнку значення позначено точкою. Іншими словами визначаються такі дві стратегії першого гравця та ймовірність для другого гравця, при яких досягається рівність
З малюнка бачимо, що ціна гри – це ордината крапки, ймовірність – це абсциса крапки. Для інших чистих стратегій першого гравця в оптимальній змішаній стратегії має бути ().
Таким чином, вирішуючи систему (1.69), отримаємо оптимальну стратегію другого гравця та ціну гри. Оптимальну змішану стратегію для першого гравця знайдемо, вирішуючи таку систему рівнянь:
1.7 Матричний метод вирішення ігор
Позначення:
Будь-яка квадратна підматриця матриці порядку
Матриця (1);
Матриця, транспонована до;
Матриця, приєднана до;
- (1) матриця отримана з X викреслюванням елементів, які відповідають рядкам, викресленим при отриманні;
- (1) матриця отримана з викреслюванням елементів, які відповідають рядкам, викресленим при отриманні.
Алгоритм:
1. Виберемо квадратну підматрицю матриці порядку () та обчислимо
2. Якщо деяке або відкидаємо знайдену матрицю і пробуємо іншу матрицю.
3. Якщо (), (), обчислюємо та будуємо X та з і, додаючи у відповідних місцях нулі.
Перевіряємо, чи задовольняються нерівності
для кожного (1.75)
та нерівності
для кожного (1.76)
Якщо одне із співвідношень не виконано, то пробуємо інше. Якщо всі співвідношення справедливі, то X і шукані рішення.
1.8 Метод послідовного наближення ціни гри
При дослідженні ігрових ситуацій часто може статися так, що немає необхідності в отриманні точного рішення гри або внаслідок будь-яких причин знайти точне значення ціни гри та оптимальних змішаних стратегій неможливо або дуже важко. Тоді можна скористатися наближеним методом розв'язання матричної гри.
Опишемо один із таких методів – метод послідовного наближення ціни гри. Кількість обчислених під час використання методу збільшується приблизно пропорційно числу рядків і стовпців матриці виграшів.
Сутність методу полягає у наступному: подумки гра проводиться багато разів, тобто. послідовно, у кожній партії гри гравець вибирає ту стратегію, яка дає йому найбільший загальний (сумарний) виграш.
Після такої реалізації деяких партій обчислює середні значення виграшу першого гравця, програшу другого гравця та їхнє середнє арифметичне приймається за наближене значення ціни гри. Метод дає можливість знайти наближене значення оптимальних змішаних стратегій обох гравців: треба підрахувати частоту застосування кожної чистої стратегії та прийняти її за наближене значення оптимальної змішаної стратегії відповідного гравця.
Можна довести, що з необмеженим збільшенням числа програмних партій середній виграш першого гравця і середній програш другого гравця необмежено наближатися до ціни гри, а наближені значення змішаних стратегій у разі, коли рішення гри єдине, прагнутиме оптимальним змішаним стратегіям кожного гравця. Взагалі, прагнення наближених значень вище зазначених величин до справжніх значень відбувається повільно. Однак цей процес легко механізувати і тим самим допомогти отримати рішення гри з необхідним ступенем точності навіть при матрицях виграшів порівняно великого порядку.
2. Практична частина
Пара вирішує куди піти погуляти та з користю для двох провести час.
Дівчина вирішує піти погуляти до парку подихати свіжим повітрям, увечері сходити на перегляд кінофільму до найближчого кінотеатру.
Хлопець пропонує піти сходити в технопарк, а потім подивитися матч футболістів місцевого клубу в центральному стадіоні.
Відповідно, потрібно знайти за який час буде досягнута мета одного з гравців. Матриця виграшів виглядатиме таким чином:
Таблиця 1. Матриця виграшів
|
Стратегії |
||||
Так як 1 2 , Очевидно, в цій грі немає сідлової точки у чистих стратегіях. Тому скористаємося наступними формулами і отримаємо:
Розміщено на http://www.allbest.ru/
2.2 Гра 2xn та mx2
Завдання 1(2xn)
Вирощується дві зернові культури для сухого та вологого клімату.
А стан природи можна як сухе, вологе, помірне.
Розміщено на http://www.allbest.ru/
Максимальне значення М() досягається в точці М, що утворюється перетином ліній, відповідних j=1, j"=2.
Завдання 2(mx2)
Хлопець і дівчина розглядають варіанти, куди піти на вихідні.
Вибір місця відпочинку можна представити як парк, кіно, ресторан.
Розміщено на http://www.allbest.ru/
Максимальне значення М() досягається в точці E, що утворюється перетином ліній, відповідних j=1, j"=2.
Для визначення значення v треба розв'язати наступні рівняння:
2.5 Матричний метод
Два конкуруючих один з одним ресторану (підприємства комунального харчування) надають такі набори послуг. Перший ресторан розташований у центрі, а друга на околиці міста.
Центральний ресторан включає такі послуги:
1) більш дороге та якісне обслуговування клієнтів;
2) страви орієнтовані французьку кухню;
Другий ресторан надає:
1) не дороге та якісне обслуговування;
2) меню поєднує різні відомі кухні світу;
3) також постійні акції та знижки;
4) здійснює доставку та приймає замовлення з доставки додому.
Відповідно до завдання прибуток за один день між двома ресторанами розподілиться таким чином:
Таблиця 2. Матриця виграшів
|
Стратегії |
||||||
Рішення гри виду матричним способом:
Існує шість підматриць та:
Розглянемо матрицю:
x 1 =? 0, x 2 =? 0
Оскільки x 2 =< 0, то мы отбрасываем.
Розглянемо тепер матрицю:
x 1 =? 0, x 2 =? 0
Ціна гри.
Це співвідношення суперечить вимогам, тому не підходить.
Розглянемо тепер матрицю:
x 1 = , x 2 =? 0,
y 1 =< 0, y 2 = ? 0.
Оскільки y 1 =< 0, то мы отбрасываем и.
Розглянемо тепер матрицю:
x 1 = , x 2 = 0, оскільки x 2 = 0, то ми відкидаємо і.
Розглянемо тепер матрицю:
x 1 = , x 2 =? 0. Оскільки x 1 = 0, ми відкидаємо в.
Розглянемо тепер матрицю:
x 1 = , x 2 =, y 1 = , y 2 =, то продовжуємо далі:
x 1 = , x 2 =, y 1 = , y 2 = або
Ціна гри.
Тепер перевіряються основні співвідношення:
Розміщено на http://www.allbest.ru/
Відповідь: x 1 = , x 2 =, y 1 = , y 2 = , y 3 = 0, y 4 = 0,.
Метод Брауна
На вимогу робітників деякої компанії профспілка веде з керівництвом переговори про організацію гарячих обідів за рахунок компанії. Профспілка, яка представляє інтереси робітників, домагається того, щоб обід був якомога якіснішим і, отже, дорожчим. Керівництво компанії має протилежні інтереси. Зрештою, сторони домовилися про наступне. Профспілка (гравець 1) вибирає одну з трьох фірм (А1, А2, А3), що постачають гаряче харчування, а керівництво компанії (гравець 2) - набір страв з трьох можливих варіантів (B1, B2, B3) . Після підписання угоди профспілка формує наступну платіжну матрицю, елементи якої становлять вартість набору страв:
Нехай гра задана наступною матрицею виграшів:
Припустимо, що другий гравець вибрав свою 2-у стратегію, тоді перший отримає:
2, якщо він застосує свою першу стратегію,
3, якщо він застосує свою третю стратегію.
Отримані значення зводиться до таблиці 1.
Таблиця 3. Стратегія другого гравця
|
№ партії |
Стратегія 2-го гравця |
Виграш 1-го гравця |
|||
З таблиці 3 видно, що з 2-ї стратегії другого гравця перший отримає найбільший виграш 3, використовуючи свою 2-у чи 3-ю стратегію. Оскільки перший гравець бажає отримати максимальний виграш, він на 2-ю стратегію другого гравця відповідає своєю 2-ою стратегією. При 2-й стратегії першого гравця другий програє:
1, якщо він застосує свою першу стратегію,
3, якщо він застосує свою 2-у стратегію,
4, якщо він застосує свою третю стратегію.
Таблиця 4. Стратегія першого гравця
|
№ партії |
Стратегія 1-го гравця |
Програш 2-го гравця |
|||
З таблиці 2 видно, що з 2-ї стратегії першого гравця другий гравець матиме найменший програш 1, якщо він застосує свою 1-ю стратегію. Оскільки другий гравець бажає програти менше, то у відповідь на 2 стратегію першого гравця він застосує свою 1 стратегію. Отримані результати зводяться до таблиці 5.
Таблиця 5. Стратегії відповідно до першого і другого гравців
|
№ партії |
Стратегія 2-го гравця |
Сумарний виграш 1-го гравця |
Стратегія 1-го гравця |
|||||||||
У табл. 5 у стовпці стратегії другого гравця у другому рядку знаходиться цифра 1, яка вказує, що у другій партії другому гравцю вигідно застосовувати свою 1 стратегію; у стовпці та знаходиться найбільший середній виграш 3 першого гравця, отриманий ним у першій партії; у стовпці w стоїть найменший середній програш 1, отриманий другим гравцем у першій партії; у стовпці v знаходиться середнє арифметичне v = (і + w) - тобто наближене значення ціни гри, отримане в результаті відтворення однієї партії гри. Якщо другий гравець застосує свою 1-шу стратегію, то перший отримає 3, 1, 2 відповідно за своїх 1-ї, 2-ї, 3-ї стратегій, а сумарний виграш першого гравця за обидві партії складе:
2 + 3=5 за його 1-ї стратегії,
3 + 1=4 за його 2-ї стратегії,
3 + 2 = 5 за його 3-ї стратегії.
Ці сумарні виграші записуються на другому рядку табл. 3 та у стовпцях, що відповідають стратегіям першого гравця: 1, 2, 3.
З усіх сумарних виграшів найбільшим є 5. Він виходить за 1-ї та 3-ї стратегій першого гравця, то йому можна вибирати будь-яку з них; скажімо, у разі, коли є два (чи кілька) однакових сумарних виграшів, вибирають стратегію з найменшим номером (у разі треба взяти 1-ю стратегію).
При 1-й стратегії першого гравця другий програє 3, 2, 3 відповідно 1-й, 2-й, 3-й його стратегіям, а сумарний програш другого гравця за обидві партії становитиме:
1 + 3=4 за його 1-ї стратегії,
3 + 2=5 за його 2-ї стратегії,
4 + 3 = 7 за його 3-ї стратегії.
Ці сумарні програші записуються на другому рядку табл. 5 та у стовпцях, що відповідають 1-й, 2-й, 3-й стратегіям другого гравця.
З усіх сумарних програшів другого гравця найменшим є 4. Він виходить за його першої стратегії, отже, у третій партії другий гравець повинен застосувати свою першу стратегію. У стовпець і ставиться найбільший сумарний виграш першого гравця за дві партії, поділений число партій, т. е. ; в стовпець w ставиться найменший сумарний програш другого гравця за дві партії, поділений число партій, т. е. ; в стовпці v ставиться середнє арифметичне цих значень, т. Е. = Це число приймається наближене значення ціни гри при двох зіграних партіях.
Таким чином, виходить наступна таблиця 4 для двох партій гри.
Таблиця 6. Сумарні виграш та програш гравців при двох зіграних партіях
|
Стратегія 2-го гравця |
Сумарний виграш 1-го гравця |
Стратегія 1-го гравця |
Сумарний програш 2-го гравця |
|||||||||
У третьому рядку таблиці 6 у стовпці стратегії другого гравця знаходиться число 1, яке показує, що у третій партії другий гравець має застосувати свою 1 стратегію. У цьому випадку перший гравець виграє 3, 1, 2, використовуючи відповідно свої 1, 2, 3 стратегії, а його сумарний виграш за три партії складе:
3 + 5 = 8 за його 1-ї стратегії,
1 +4 = 5 за його 2-ї стратегії,
2 + 5 = 7 за його 3-ї стратегії.
Ці сумарні виграші першого гравця записуються в третьому рядку таблиця 6 і стовпцях, що відповідають його стратегіям 1, 2, 3. Оскільки найбільший сумарний виграш першого гравця 8 виходить при 1-й стратегії, відповідно вибирає 1-ю.
При 1-й стратегії першого гравця другий програє 3, 1, 2 відповідно 1-й, 2-й, 3-й його стратегіям, а сумарний програш другого гравця за обидві партії становитиме:
3 + 4=7 за його 1-ї стратегії,
2 + 5 = 7 за його 2-ї стратегії,
3 + 7 = 10 за його 3-ї стратегії.
Ці сумарні поразки записуються в третьому рядку табл. 6 та у стовпцях, що відповідають 1-й, 2-й, 3-й стратегіям другого гравця. З усіх сумарних його програшів 7 є найменшим і виходить за його 1-ї та 2-ї стратегій, далі другому гравцю треба застосувати свою 1-у стратегію.
У табл. 6 у третьому рядку в стовпці і записується найбільший сумарний виграш першого гравця за три партії, поділений на число партії, тобто ; в стовпці w ставиться найменший сумарний програш другого гравця за три партії, поділений на число партій, тобто ; у стовпці v ставиться їхнє середнє арифметичне
Таким чином одержуємо табл. 7 для трьох партій.
Таблиця 7. Сумарні виграш та програш гравців при трьох зіграних партіях
|
№ партії |
Стратегія 2-го гравця |
Сумарний виграш 1-го гравця |
Стратегія 1-го гравця |
Сумарний програш 2-го гравця |
||||||||
Таблиця 8. Кінцева таблиця при двадцяти зіграних партіях
|
№ партії |
Стратегія 2-го гравця |
Сумарний виграш 1-го гравця |
Стратегія 1-го гравця |
Сумарний програш 2-го гравця |
||||||||
З табл. 7 і 8 видно, що в 20 програних партіях стратегії 1, 2, 3 для першого гравця зустрічаються відповідно 12, 3, 5 разів, отже, їх відносні частоти відповідно рівні; стратегії 1, 2, 3 для другого гравця зустрічаються відповідно 7, 11,2 рази, отже їх відносні частоти відповідно дорівнюють; наближене значення ціни гри. Таке наближення досить хороше.
Насамкінець зазначимо, що, якщо гра має більше одного рішення, то наближені значення ціни гри, як і раніше, будуть необмежено наближатися до справжньої ціни гри, а відносні частоти появи стратегій гравців вже не обов'язково наближатимуться до справжніх оптимальних змішаних стратегій гравців.
Аналіз результатів
У цій роботі вивчений матеріал знаходження рішення антагоністичних ігор графічним, матричним методом, методом послідовного наближення ціни гри. Знайдено оптимальні стратегії першого та другого гравця, а також ціна гри в іграх 2x2, 2xn та mx2, а також в іграх з використанням матричного методу та методу Брауна.
На прикладі пари була змодельована гра 2x2, яка була вирішена методом алгебри і графічним. Вирішуючи гру методом алгебри рішення показує, що застосовуючи свої оптимальні змішані стратегії перший і другий гравець проведуть разом 4.6 години. Графічне вирішення завдання вийшло з невеликою похибкою і становило 4.5 години.
А також були змодельовані два завдання 2xn і mx2. У задачі 2xn була розглянута с/г культура і стратегія показує, що краще засадити поле 50 на 50, а ціна гри склала 3.75 млн. рублів. А в задачі mx2 була розглянута пара, стратегія якої показала, що дешевше піти в парк та кіно, а ціна витрати становитимуть 4.3 рублів.
Було змодельовано завдання для матричного методу, в якому розглядалися два ресторани, рішення задачі показало, що при застосуванні своєї оптимальної змішаної стратегії прибуток першого ресторану становитиме 15.6 млн. рублів, а при використанні своєї оптимальної змішаної стратегії другим рестораном, він не дозволить першому заробити більше 15.6 млн. рублів. Рішення графічним шляхом дало похибка і вартість гри становила 14.9 млн. рублів.
Для методу Брауна було складено завдання у якій розглядається профспілка та керівництво компанії, їхнє завдання забезпечити харчування робітників. При використанні обома гравцями своїх оптимальних стратегій харчування на людину становитиме 2.45 тис. руб.
Список використаних джерел
1) Вілісов В.Я. Конспект лекцій «Теорія ігор та статистичних рішень», - Філія – «Схід» МАІ. 1979. 146 с.
2) Крушевський А.В. Теорія ігор, – Київ: Вища школа, 1977. – 216 с.
3) Черчмінь У., Акоф Р., Арноф Л., Введення у дослідження операцій. - М: Наука. 1967. – 488 с.
4) http://www.math-pr.com/exampl_gt2.htm
5) http://ua.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0
Розміщено на Allbest.ru
Подібні документи
Ухвалення рішень як особливий вид людської діяльності. Раціональне уявлення матриці гри. Приклади матричних ігор у чистій та змішаній стратегії. Дослідження операцій: взаємозв'язок задач лінійного програмування з теоретико-ігровою моделлю.
курсова робота , доданий 05.05.2010
Ігри, що повторюються багаторазово, їх відмінні властивості та етапи. Змішані стратегії, умови та можливості їх використання на практиці. Аналітичний метод розв'язання гри типу 2 x 2. Основні теореми для прямокутних ігор. Алгебраїчні рішення.
презентація , доданий 23.10.2013
Основні визначення теорії біматричних ігор. Приклад біматричної гри "Студент-Викладач". Змішані стратегії у біматричних іграх. Пошук "рівноважної ситуації". 2x2 біматричні ігри та формули для випадку, коли кожен гравець має дві стратегії.
реферат, доданий 13.02.2011
Вивчення загальних відомостей про матричні та антагоністичні ігри. Поняття позиційної гри, дерева, інформаційної множини. Розгляд принципу максиміну та принципу рівноваги. Оптимальність за Парето. Позиційна неантагоністична гра, її характеристики.
курсова робота , доданий 17.10.2014
Теорія ігор – розділ математики, предметом якого вивчення математичних моделей прийняття оптимальних рішень за умов конфлікту. Ітеративний метод Брауна-Робінсона. Монотонний ітеративний алгоритм розв'язання матричних ігор.
дипломна робота , доданий 08.08.2007
Складання платіжної матриці, пошук нижньої та верхньої чистої ціни гри, максимінної та мінімаксної стратегії гравців. Спрощення платіжної матриці. Вирішення матричної гри за допомогою зведення до завдання лінійного програмування та надбудови "Пошук рішення".
контрольна робота , доданий 10.11.2014
Теорія ігор – математична теорія конфліктних ситуацій. Розробка математичної моделі гри двох осіб із нульовою сумою, її реалізація у вигляді програмних кодів. Метод розв'язання задачі. Вхідні та вихідні дані. Програма, посібник користувача.
курсова робота , доданий 17.08.2013
Основні відомості про симплекс-метод, оцінка його ролі та значення у лінійному програмуванні. Геометрична інтерпретація та алгебраїчний сенс. Знаходження максимуму та мінімуму лінійної функції, особливі випадки. Розв'язання задачі матричним симплекс-методом.
дипломна робота , доданий 01.06.2015
Прийоми побудови математичних моделей обчислювальних систем, що відображають структуру та їх функціонування. Число звернень до файлів у процесі вирішення середньої задачі. Визначає можливість розміщення файлів у накопичувачах зовнішньої пам'яті.
лабораторна робота , доданий 21.06.2013
Проектування математичної моделі. Опис гри в хрестики-нуліки. Модель логічної гри на основі булевої алгебри. Цифрові електронні пристрої та розробка їх математичної моделі. Ігровий пульт, ігровий контролер, рядок ігрового поля.
Підхід до вирішення матричних ігор може бути узагальнений на випадок антагоністичних ігор, у яких платіж гравців задається у вигляді безперервної функції (нескінченна гра антагоністичної).
Така гра представляється як гра двох гравців, у якій гравець 1 вибирає число хз множини X,гравець 2 вибирає число у з множини 7, і після цього гравці 1 і 2 отримують відповідно виграші U (х,у) та -U(x, у).Вибір певного числа гравцем означає застосування його чистої стратегії, що відповідає цій кількості.
За аналогією з матричними іграми чистою нижньою ціною можна назвати v (= max min U(x, у),а чистою верхньою ціною гри -v 2 =
min max U(x, у).Тоді за аналогією можна вважати, що якщо для якої-
у *
або нескінченної антагоністичної гри величини Vі v 2існують і рівні між собою («i =v 2 =v),то така гра має рішення у чистих стратегіях, тобто. оптимальною стратегією гравця 1 є вибір числа х°е X,а гравця 2 - числа у 0е 7, при яких Щх (у 0) -v.
В цьому випадку vназивається чистою ціною гри, а (х °, у 0) - сідловою точкою нескінченної антагоністичної гри.
Для матричних ігор величини v xі v 2завжди існують, але у нескінченних антагоністичних іграх можуть і існувати, тобто. нескінченна антагоністична гра не завжди можна розв'язати.
При формалізації реальної ситуації у вигляді нескінченної антагоністичної гри зазвичай вибирається одиничний стратегічний інтервал – одиничний проміжок, з якого гравці можуть зробити вибір (х -число (стратегія), що вибирається гравцем 1; -
число (стратегія), що вибирається гравцем 2). Технічно це полегшує рішення, оскільки простим перетворенням будь-який інтервал можна перевести в одиничний і навпаки. Така гра називається антагоністичної гри на одиничному квадраті.
Наприклад припустимо, що гравець 1 вибирає число хз множини Х =, гравець 2 вибирає число у з множини Y=. Після цього гравець 2 сплачує гравцю 1 суму Щх, у) -2х 2-у 2 .Оскільки гравець 2 прагне мінімізувати платіж гравця 1, він визначає min ( 2х 2 - у 2) = 2х 2- 1, тобто. при цьому = 1. Гравець 1 прагне мак-тег
зимизувати свій платіж, тому визначає maxi min Щх,у) 1 =
xGX у ег
- max (2х 2 - 1) = 2- 1 = 1, який досягається при х = 1.
Таким чином, нижня чиста ціна гри v x - 1. Верхня чиста
ціна гриv 2 =min – min (2 – у 2) = 2 – 1 = 1, тобто. в цій
>егхех у еу
грі v l = v 2 = l.Тому чиста ціна гри v= 1, а сідлова точка (х ° = 1; у ° = 1).
Припустимо тепер, що Хі Y-відкриті інтервали, тобто. гравець 1 вибирає xeA "= (0; 1), гравець 2 вибирає уе 7 = (0; 1). У цьому випадку, вибираючи х,досить близьке до 1, гравець 1 буде впевнений, що він отримає виграш не менше ніж число, близьке до »=1; вибираючи у, близьке до 1, гравець 2 не допустить, щоб виграш гравця 1 значно перевищував чисту ціну гри v= 1.
Ступінь близькості до ціни гри може характеризуватись числом?>0. Тому в описуваній грі можна говорити про оптимальність чистих стратегій х°= 1, у 0 = 1 відповідно до гравців 1 і 2 з точністю до довільного числа?>0. Крапка (х„, у Е), де х ее X, у (. eY, в нескінченній антагоністичній грі називається точкою z-рівноваги (с.-сідловою точкою), якщо для будь-яких стратегій хеТигрока 1,уе Тігро-ка 2 має місце нерівність Щх,у.) - ? Щ x r, у (.) U (x t., У) +?. У цьому випадку стратегії х до.та у. називаються з,-оптимальними стратегіями. Ці стратегії оптимальні з точністю до? у тому сенсі, що якщо відхилення від оптимальної стратегії ніякої користі гравцеві принести не може, його відхилення від з-оптимальної стратегіїможе збільшити його виграш лише на е.
Якщо гра немає сідлової точки (з-сідлової точки), тобто. рішення в чистих стратегіях, то оптимальні стратегії можна шукати серед змішаних стратегій, як використовуються функції розподілу ймовірностей застосування гравцями чистих стратегій.
Нехай F(x)- функція розподілу ймовірностей застосування чистих стратегій гравцем 1. Якщо число Е - чиста стратегія гравця 1, то F(x) = P(q де P(q -Х)- ймовірність того, що випадково обрана чиста стратегія Е, не перевершуватиме х.Аналогічно розглядається функція розподілу ймовірностей застосування чистих стратегій р| гравцем 2: Q(y) = Р(р.
Функції F(x)і Q(y)називаються змішаними стратегіямивідповідно гравців 1 та 2. Якщо Fx)і Q(y)диференційовані, тобто існують їх похідні, що позначаються відповідно через f(x)і q(y)(функції густини розподілу).
У випадку диференціал функції розподілу dF(x) висловлює ймовірність того, що стратегія с,знаходиться в проміжку х Е, Аналогічно для гравця 2: dQ(y)означає ймовірність того, що його стратегія р знаходиться в інтервалі у р| у+dy.Тоді платіж гравця 1 становитиме Щх, у) dF(x),а платіж гравця 2 дорівнює Щх, у) dQ(y).
Середній платіж гравця 1 за умови, що гравець 2 застосовує свою чисту стратегію у,можна отримати, проінтегрувавши платежі за всіма можливими значеннями х,тобто. на одиничному інтервалі:
Середній платіж гравця 1 за умови, що обидва гравці застосовують свої змішані стратегії F(x)і Q(y),дорівнюватиме
За аналогією з матричними іграми визначаються оптимальні змішані стратегії гравців та ціна гри: якщо пара змішаних стратегій F*(x) та Q*(y)відповідно для гравців 1 та 2 є оптимальними, то для будь-яких змішаних стратегій F(x)і Q(y)справедливі співвідношення:
Якщо гравець 1 відступає від своєї стратегії F*(x),то його середній виграш не може збільшитися, але може зменшитися через раціональні дії гравця 2. Якщо гравець 2 відступить від своєї змішаної стратегії Q*(y),то середній виграш гравця 1 може збільшитися, але не зменшитися за рахунок розумніших дій гравця 1. Середній виграш E(F*, Q*),отримуваний гравцем 1 при застосуванні гравцями оптимальних змішаних стратегій відповідає ціні гри.
Тоді нижня ціна нескінченної антагоністичної гри, яка вирішується у змішаних стратегіях, може бути визначена як v x= шах
min Е(FQ),а верхня ціна гри як v 2 = min max Е(F, Q).
Q Q f
Якщо існують такі змішані стратегії F* (х)і Q*(у) відповідно для гравців 1 та 2, при яких нижня та верхня ціни гри збігаються, то F*(x)і Q*(y)природно назвати оптимальними змішаними стратегіями відповідних гравців, a v = v x = v 2- Ціною гри.
На відміну від матричних ігор, рішення нескінченної антагоністичної гри існує не для будь-якої функції. Щх, у).Але доведено теорему про те, що будь-яка нескінченна антагоністична гра з безперервною платіжною функцією Щх, у)на одиничному квадраті має рішення (гравці мають оптимальні змішані стратегії), хоча загальних методів на вирішення нескінченних антагоністичних ігор, зокрема безперервних ігор, немає. Однак досить просто вирішуються антагоністичні нескінченні ігриз опуклими та увігнутими безперервними платіжними функціями (вони називаються відповідно опуклимиі увігнутими іграми).
Розглянемо рішення ігор із опуклою платіжною функцією. Вирішення ігор з увігнутою функцією виграшу симетрично.
Випуклоюфункцією/змінною хна інтервалі ( а; Ь)називається така функція, для якої виконується нерівність
де Ххі х 2 -будь-які дві точки з інтервалу (а; b);
Х.1, А.2> 0, причому + Х.2 = 1.
Якщо для / год * 0 Д 2 * 0, завжди має місце сувора нерівність
то функція/називається суворо опуклоюна (а; Ь).
Геометрично опукла функція зображує дугу, графік якої розташований нижче хорди, що стягує її. Аналітично опуклість двічі диференційованої функції відповідає невід'ємності (а разі суворої опуклості - позитивності) її другий похідної.
Для увігнутих функцій властивості протилежні, їм повинна виконуватися нерівність/(/4X1 +А.2Х2) > Kf(xi) +)-if(х 2) (> при суворій увігнутості), а друга похідна/"(х)
Доведено, що безперервна і строго опукла функція на замкнутому інтервалі набуває мінімального значення лише в одній точці інтервалу. Якщо Щх,у) - безперервна функція виграшів гравця 1 на одиничному квадраті та сувороопукла по удля будь-якого х, то є єдина оптимальна чиста стратегія у = у °е для гравця 2, ціна гри визначається за формулою
а значення у 0визначається як рішення наступного рівняння:
Якщо функція Щх,у) не суворо опукла по, то у гравця 2 оптимальна чиста стратегія не буде єдиною.
Симетрична властивість виконується і для суворо увігнутих функцій. Якщо функція Щх,у) безперервна за обома аргументами і суворо увігнута по х за будь-якого у, то гравець 1 має єдину оптимальну стратегію.
Ціна гри визначається за формулою
а чиста оптимальна стратегія х 0 гравця 1 визначається з рівняння
На підставі цих властивостей нескінченних антагоністичних ігор з опуклою або увігнутою функціями виграшу побудовано загальну схему вирішення таких ігор на одиничному квадраті (х е, у е). Наведемо цю схему лише опуклих ігор , оскільки увігнутих ігор вона симетрична.
1. Перевірити функцію Щх,у) на опуклість по у (друга приватна похідна має бути більшою або дорівнює 0).
2. Визначити у 0 із співвідношення v- min max Щх, у)як значення
у,на якому досягається мінімакс.
3. Знайти рішення рівняння v = U(x,у 0) і скласти пари його рішень Хі х 2 ,для яких
4. Знайти параметр аз рівняння
Параметр авизначає оптимальну стратегію гравця 1 і має сенс ймовірності вибору ним його чистої стратегії х х.Величина 1 - а має сенс ймовірності вибору гравцем 1 його чистої стратегії х 2 .
Покажемо з прикладу використання цієї схеми на вирішення гри такого виду. Нехай функція виграшу в нескінченній антагоністичній грі задана на одиничному квадраті і дорівнює Щх, у) = =(х - у) 2 = х 2 - 2 хуч-у 2 .
1. Ця функція безперервна по хі у,і тому ця гра має рішення. Функція Щх, у)суворо випукла по у,так як 
Отже, гравець 2 має єдину чисту оптимальну стратегію 0 .
2. Маємо v= min max (х - у) 2 . Для визначення max (х 2 - 2ху Ч-у 2)
послідовно знайдемо першу та другу приватні похідні платіжної функції з х:
Таким чином, функція Uмає мінімум для будь-якого у при х=у. Це означає, що при ху - зростає, а її максимум повинен досягатися в одній із крайніх точок х = 0 або х = 1. Визначимо значення функції Uу цих точках:
Тоді шах (х - у) 2 = тах (у 2; 1 - 2у + у 2). Порівнюючи «внутрішні»
максимуми, що стоять у фігурних дужках, легко помітити, що у 2 > 1 - - 2у+у 2 ,якщо у >*/ 2 та у 2 1 - 2 у+у 2 ,якщо у "/ 2 . Наочно це представляється графіком (рис. 2.5).
Мал. 2.5. Внутрішні максимуми платіжної функції U(х,у) = (х- у) 2
Тому вираз (х - у) 2досягає свого максимуму при х = 0, якщо у > 7 2 , і при х= 1, якщо у У 2:
Отже, v= min (min у 2; min (1 - у) 2). Кожен із вну-
тренних мінімумів досягається при у=*/ 2 і набуває значення У 4 . Таким чином, ціна гри г = У 4 а оптимальна стратегія гравця 2:
3. Визначимо оптимальну стратегію гравця 1 із рівняння U(x,у 0) = v,тобто. для цієї гри (х - У 2) 2 = У 4 . Рішенням цього рівняння Є Х| = 0, х 2 = 1.
Для них виконуються умови
4. Визначимо параметр а, тобто. ймовірність застосування гравцем 1 його чистої стратегії Х] = 0. Складемо рівняння а-1 + (1 - а) (-1) = 0, звідки а = У 2 . Таким чином, оптимальна стратегія гравця 1 полягає у виборі ним своїх чистих стратегій 0 та 1 з ймовірністю 1 / 2 кожна. Завдання вирішено.
Називається гра двох осіб з нульовою сумою, в якій у розпорядженні кожного з них є безліч стратегій. Правила матричної гри визначає платіжна матриця, елементи якої – виграші першого гравця, які є також програшами другого гравця.
Матрична гра є антагоністичною грою. Перший гравець отримує максимальний гарантований (не залежить від поведінки другого гравця) виграш, що дорівнює ціні гри, аналогічно, другий гравець досягає мінімального гарантованого програшу.
Під стратегією розуміється сукупність правил (принципів), що визначають вибір варіанта дій при кожному особистому ході гравця в залежності від ситуації, що склалася.
Тепер про все по порядку та докладно.
Платіжна матриця, чисті стратегії, ціна гри
У матричної гри її правила визначає платіжна матриця .
Розглянемо гру, в якій є два учасники: перший гравець та другий гравець. Нехай у розпорядженні першого гравця є 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та оптимальні змішані стратегії та .
Рішення. Складаємо відповідне даної матричної гри завдання лінійного програмування:
Отримуємо вирішення прямого завдання:
.
Знаходимо лінійну форму оптимальних планів як суму знайдених координат.
Тести для підсумкового контролю
1. Антагоністична гра може бути задана:
а) безліччю стратегій обох гравців та сідловою точкою.
б) безліччю стратегій обох гравців та функцією виграшу першого гравця.
2. Ціна гри існує для матричних ігор у змішаних стратегіях завжди.
а) так.
3. Якщо в матриці виграшів усі стовпці однакові і мають вигляд (4 5 0 1), то яка стратегія оптимальна для одного гравця?
а) перша.
б) друга.
в) будь-яка з чотирьох.
4.Нехай у матричній грі одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.4, 0, 0.6). Яка розмірність цієї матриці?
а) 2*3.
в) інша розмірність.
5. Принцип домінування дозволяє видаляти із матриці за один крок:
а) повністю рядки.
б) окремі числа.
6.У графічному методі вирішення ігор 2*m безпосередньо з графіка знаходять:
а) оптимальні стратегії обох гравців.
б) ціну гри та оптимальні стратегії 2-го гравця.
в) ціну гри та оптимальні стратегії 1-го гравця.
7.Графік нижньої огинаючої для графічного методу вирішення ігор 2*m є в загальному випадку:
а) ламану.
б) пряму.
в) параболу.
8. У матричній грі 2*2 дві компоненти змішаної стратегії гравця:
а) визначають значення один одного.
б) незалежні.
9. У матричній грі елемент aij є:
а) виграш 1-го гравця при використанні ним i-ї стратегії, а 2-м – j-ї стратегії.
б) оптимальну стратегію одного гравця при використанні супротивником i-йабо j-ї стратегії.
в) програш 1-го гравця при використанні ним j-ї стратегії, а 2-м - i-ї стратегії.
10. Елемент матриці aij відповідає сідловій точці. Можливі такі ситуації:
а) цей елемент суворо найменше у рядку.
б) цей елемент другий по порядку у рядку.
11. У методі Брауна-Робінсон кожен гравець при виборі стратегії на наступному кроці керується:
а) стратегіями супротивника на попередніх кроках.
б) своїми стратегіями попередніх кроках.
в) ще чимось.
12. За критерієм математичного очікування кожен гравець виходить із того, що:
а) станеться найгірша йому ситуація.
в) всі або деякі ситуації можливі з деякими ймовірностями.
13. Нехай матрична гра задана матрицею, де всі елементи негативні. Ціна гри позитивна:
б) ні.
в) немає однозначної відповіді.
14. Ціна гри – це:
а) число.
б) вектор.
в) матриця.
15. Яка максимальна кількість сідлових точок може бути в грі розмірності 5 * 5 (матриця може містити будь-які числа):
16. Нехай у матричній грі розмірності 2*3 одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.3, x, 0.5). Чому дорівнює число x?
в) іншому числу.
17. Для якої розмірності ігрової матриці критерій Вальда звертається до критерію Лапласа?
в) тільки в інших випадках.
18. Верхня ціна гри завжди менша від нижньої ціни гри.
б) ні.
б) питання некоректне.
19. Які стратегії бувають у матричній грі:
а) чисті.
б) змішані.
в) і ті, і ті.
20. Чи можуть у якійсь антагоністичній грі значення функції виграшу обох гравців для деяких змінних значень дорівнювати 1?
а) завжди.
б) інколи.
в) ніколи.
21.Нехай у матричній грі одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.4, 0.1,0.1,0.4). Яка розмірність цієї матриці?
в) інша розмірність.
22. Принцип домінування дозволяє видаляти із матриці за один крок:
а) цілком стовпці,
б) окремі числа.
в) підматриці менших розмірів.
23. У матричній грі 3*3 дві компоненти змішаної стратегії гравця:
а) визначають третю.
б) не визначають.
24. У матричній грі елемент aij є:
а) програш 2-го гравця при використанні ним j-ї стратегії, а 2-м – i-ї стратегії.
б) оптимальну стратегію 2-го гравця при використанні противником i-ї або j-ї стратегії,
в) виграш 1-го гравця при використанні ним j-ї стратегії, а 2-м – i-ї стратегії,
25. Елемент матриці aij відповідає сідловій точці. Можливі такі ситуації:
а) цей елемент найбільше у стовпці.
б) цей елемент строго найбільше по порядку в рядку.
в) у рядку є елементи і більше, і менше, ніж елемент.
26. За критерієм Вальда кожен гравець виходить із того, що:
а) станеться найгірша для нього ситуація.
б) усі ситуації рівноможливі.
в) усі ситуації можливі з деякими заданими ймовірностями.
27. Нижня ціна менша від верхньої ціни гри:
б) який завжди.
в) ніколи.
28. Сума компонентів змішаної стратегії для матричної гри завжди:
а) дорівнює 1.
б) невід'ємна.
в) позитивна.
г) який завжди.
29. Нехай у матричній грі розмірності 2*3 одна із змішаних стратегій 1-го гравця має вигляд (0.3, 0.7), а одна із змішаних стратегій 2-го гравця має вигляд (0.2, x, x). Чому дорівнює число x?
