WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЕкономічна теорія → Теорія ігор, теорія графів і сіткове планування - Реферат

Теорія ігор, теорія графів і сіткове планування - Реферат


Реферат на тему:
Теорія ігор, теорія графів і сіткове планування
Зміст
1. Основні поняття та класифікація ігор
2. Застосування апарату теорії ігор в економіці
3. Теорія графів і сіткове планування
Список використаної літератури
Основні поняття та класифікація ігор
В оптимізаційних моделях вибір рішення здійснювався однією особою. В теорії ігор рішення приймаються кількома учасниками. Значення цільової функції для кожного з них залежить від рішень, що приймаються рештою учасників. Теорія ігор ще має назву теорії конфліктних ситуацій. Прикладами є ситуація "покупець-продавець", карткові та спортивні ігри, олігополістичні моделі. Конфлікт може бути результатом свідомих і стихійних дій різних учасників.
Гравці в теорії ігор - це учасники (суб'єкти) конфлікту. Вони відрізняються іменами або номерами. Можливі дії кожної зі сторін мають назву стратегії, або ходів.
Інтереси сторін представляються функціями виграшу (платежу)для кожного з гравців.
Гра - це модель, яка формалізує змістовний опис конфлікту.
Теорія ігор уперше була системно викладена Дж. фон Нейманом і О. Монгерштерном у 1944 р. В роки Другої світової війни і після неї теорія ігор привернула увагу військових як апарат для дослідження стратегічних рішень. Проте основним застосуванням теорії ігор стала економіка. У 1994 р. Нобелівську премію з економіки одержалиДжон Неш (США), Джон Харсаньї (США), Рейнхард Зельтен (Німеч-чина) за праці у сфері теорії ігор.
Ігри класифікують залежно від обраного критерію: за кількістю гравців, за кількістю стратегій, за властивостями функцій виграшу таза можливостями попередніх переговорів між гравцями.
Залежно від кількості гравців розрізняють ігри з двома, трьома і більше учасниками. Теорію оптимізації, наприклад, можна розглядати як теорію ігор з одним гравцем. Можна досліджувати також ігри з нескінченною кількістю гравців.
За кількістю стратегій розрізняють скінченні та нескінченні ігри. У скінченних іграх кількість можливих стратегій є числом скінченним (підкидання монети - дві стратегії, підкидання кубика - шість стратегій). Стратегії у скінченних іграх називають чистими стратегіями. В нескінченних іграх кількість стратегій є нескінченною.
За властивостями функцій виграшу (платіжних функцій) теорію ігор поділяють на три види. Гра, в якій виграш одного з гравців дорівнює програшу другого, має назву гри з нульовою сумою, або антагоністичної гри. Якщо гравці виграють і програють одночасно та їм вигідно діяти разом, то такі ігри мають назву ігор з постійною різницею. Гра з ненульовою сумою - це гра, в якій наявні конфлікт та узгоджена дія гравців.
За можливістю попередніх переговорів між гравцями розрізняють кооперативні та некооперативні ігри. Кооперативна гра - це гра, в якій до її початку учасники утворюють коаліції і приймають угоди про свої стратегії. Некооперативна гра - гра, в якій гравці не можуть координувати свої стратегії. Прикладом кооперативної гри може стати ситуація лобіювання у парламенті прийняття рішення зацікавлених у ньому учасників шляхом голосування.
Розглянемо гру з двома учасниками, яка має скінченну кількість стратегій. Це дозволить зобразити гру за допомогою платіжної матриці.
Припустімо, кожен гравець має дві стратегії: "Так" або "Ні". Ці стратегії можуть являти економічний вибір, наприклад, підвищувати або знижувати ціну та політичний вибір, наприклад, приймати або не приймати закон. Кожному гравцю у кожній ситуації приписують число, яке виражає ступінь задоволення його інтересів. Це число називається виграшем гравця. Відповідність між набором ситуацій і виграшем гравця називається функцією виграшу. У випадку скінченої гри двох осіб функції виграшу кожного з гравців зручно представляти за допомогою матриці виграшів, де рядки зображують стратегії одного гравця, стовпці - стратегії другого гравця. В клітинках матриці вказують виграші кожного з гравців у кожній з утворених ситуацій. Платіжна матриця відображає виграш кожного гравця за кожної комбінації стратегій, що вибираються. Якщо гравці вибирають однакові стратегії, тобто говорять "Так" або "Ні", то виграш одного гравця дорівнює одиниці, а програш другого гравця дорівнює мінус одиниці.
Матриця виграшів першого гравця має вигляд:
Матриця виграшів другого гравця має вигляд:
Для наочності матрицю виграшів для обох гравців можна об'єднати в одну:
Розглянемо приклад задания матриці виграшів для гри з ненульовою сумою, яка має назву дилеми ув'язнених. Суть гри така: двох ув'язнених - співучасників злочину допитують в окремих кімнатах. У кожного з них є вибір: або зізнатись у злочині і тим самим вплутати іншого, або заперечувати свою причетність до злочину. Якщо зізнається лише один з ув'язнених, його звільнять, і звинуваченим буде другий, якого позбавлять волі на термін до 5 років. Якщо обидва злочинці будуть заперечувати свою причетність до злочину, обох протримають у в'язниці до одного року, якщо обидва зізнаються, обох ув'язнять на термін до 3 років.
Платіжна матриця цієї гри має вигляд:
Основним припущенням у теорії ігор є те, що кожен гравець праг-не забезпечити для себе максимально можливий виграш за будь-яких дій партнера. Припустімо, що є скінченна антагоністична гра з матрицею виграшів першого гравця А і, відповідно, матриця виграшу другого гравця мінус A. Гравець 1 вважає, що яку б стратегію він не обрав, гравець 2 обере стратегію, яка максимізує його виграш і тим самим мінімізує виграш гравця 1. Оптимальна стратегія гравця 1, яка забезпечить йому найбільший з можливих виграшів поза стратегією, яку обере суперник, буде полягати у виборі стратегії з найвищим з таких платежів. Таким чином, гравець 1 обирає І-ту стратегію, яка є розв'язанням задачі:
Гравець 2 так само прагне забезпечити для себе найвищий виграш(найменший програш) незалежно від стратегії, обраної суперником. Його оптимальною стратегією буде стовпець матриці А з найменшим значенням максимального платежу. Таким чином, гравець 2 обере; -ту стратегію, яка є розв'язанням задачі:
У підсумку, якщо гравець 1 дотримується обраної максимінної стратегії, його виграш у будь-якому разі буде не меншим за максимальне значення (нижня ціна гри), тобто:
Відповідно, якщо гравець 2 дотримується своєї мінімаксної стратегії, його програш буде не більший за мінімаксне значення (верхняціна гри), тобто:
Якщо верхня та нижня ціна гри збігаються:
обидва гравці одержують гарантовані платежі. Значення д.. називається
Loading...

 
 

Цікаве