Прикладні аспекти теорії ігор

                    Тема: «Прикладні аспекти теорії ігор»

Зміст

1. Вступ

2. Історія винекнення теорії ігор

3.  Основні означення і положення  теорії ігор

           3.1.  Учасники гри, гравці, стратегії, виграші

           3.2.   Класифікація ігор і загальні відомості про методи їх розвязування

     4.  Заключення

     5.  Література

1.Вступ

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

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

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

                   2. ІСТОРІЯ ВИНЕКНЕННЯ ТЕОРІЇ ІГОР

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

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

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

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

Хто і коли вперше проробив експеримент з монетою, невідомо. Французький натураліст Ж.Бюффон (1707-1788) у  вісімнадцятому сторіччі 4040 разів підкидав монету - герб випав 2048 разів. Англійський статистик К.Пірсон на початку двадцятого сторіччя з 1200 підкидань монети одержав 602 випадіння герба, а з 24000 – 12120 випадінь. Років 35 назад американські експериментатори повторили досвід. При 10000 підкидань герб випав 4979 разів. Вчені помітили, що при багаторазовому підкиданні монети кількість випадань герба або решки приблизно однакова. Отже, результати кидань монети, хоча кожний з них і є випадковою подією, при декількаразовому повторенні задовольняють об'єктивному закону.

   У таблиці 1.1 наведені результати серії іспитів, при яких монети кидали 10000 разів. При цьому розглядалися окремо серії з п-експериментів, і в кожній серії фіксували кількість появи гербів.

Таблиця 1.1

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

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

   Виникнення теорії ігор як науки пов'язано з потребами практики, демографії, страхової справи, азартних ігор і т.п. Перші роботи, у яких зароджувалися основні поняття теорії ігр, з'явилися в XVІ-XVІІ ст. і належали Д.Кардано (1501-1576), Б.Паскалю (1623-1662), П.Ферма (1601-1665) і Х.Гюйгенсу (1629-1695). У них робилася спроба створити теорію азартних ігр з метою надання рекомендацій гравцям, передбачення результату ігр. Приклади таких передбачень дає історія азартних ігр, що були поширені вже в XVІІ ст. Одна з них - гра в кістки - полягає в тому, що кожен гравець по черзі кидає на стіл два або три гральних кубики і підраховує суму очок, що випала на верхніх гранях на кожному при визначеній кількості кидань. Умови виграшу були різними. Наприклад, домовлялися, що всю ставку одержує той, у кого загальна сума очок раніше досягне визначеного числа.

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

    Перші відомі підрахунки числа різних можливих ісходів при киданні трьох гральних кісток відносяться до X-XІ ст. Ще до XVст. зустрічалися поеми, у яких кожному результатові при киданні трьох гральних кісток відповідав визначений вірш. Таких віршів було 56. Дійсно, 56 - це число всіх можливих ісходів при киданні, якщо не враховувати порядок появи чисел на кістках.

Сама рання відома нам спроба підрахувати число можливих ісходів при киданні трьох гральних кісток, включаючи і перестановки, зустрічається в XІІІст. Але і значно пізніше багато авторів робили аналогічні підрахунки невірно.

  3. ОСНОВНІ ОЗНАЧЕННЯ І ПОЛОЖЕННЯ ТЕОРІЇ ІГОР

       3.1. Учасники гри, гравці, стратегії, виграші

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

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

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

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

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

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

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

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

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

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

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

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

2. Класифікація ігр і загальні відомості про методи їх розв'язування

    Реальні конфліктні ситуації приводять до різних видів ігор. У залежності від виду гри розробляється і метод її розв'язування. На даний час немає цілком чітко сформованої класифікації ігор. Однак можливо відзначити основні напрямки (табл.2.1).

Таблиця. 2.1

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

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

   По характеру взаємодії ігри поділяються на:

1) бескоаліційні: гравці не мають права вступати в угоди, утворювати коаліції;

2) коаліційні (кооперативні): гравці  можуть вступати в угоди, утворювати коаліції.

У кооперативних іграх коаліції наперед визначені.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.  Заключення

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

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

5.  Література

1. Е. С. Вентуель «Элементы теории игр» М., 1959
2. Э. Г. Давыдов «Исследование операций»  М.; «Высшая школа», 1990
3. О.О. Замков, А. В. Толстопятенко, Ю. Н. Черемных «Математические методы» М.; МГУ им. М. В. Ломоносова
4. А. В. Крушевский «Теория игр» К., «Вища школа», 1997.
5. С.Н.Иванов.Математические методы исследования операций:Учеб. пособие. Донецк:Донецкий национальный университет,2003.