Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Теорія ігор



План:


Введення

Ця стаття про математичної теорії; інші значення: Психологія гри.

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

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


1. Історія

Оптимальні рішення або стратегії в математичному моделюванні пропонувалися ще в XVIII ст. Завдання провадження і ціноутворення в умовах олігополії, які стали хрестоматійними прикладами пізніше теорії ігор, розглядалися в XIX в. А. Курно і Ж. Бертраном. На початку XX ст. Е. Ласкер, Е. Цермело, Е. Борель висувають ідею математичної теорії конфлікту інтересів.

Математична теорія ігор бере свій початок з неокласичної економіки. Вперше математичні аспекти та застосування теорії були викладені у класичній книзі 1944 Джона фон Неймана і Оскара Моргенштерна "Теорія ігор і економічна поведінка" [2] ( англ. Theory of Games and Economic Behavior ).

Ця область математики знайшла певне відображення в суспільній культурі. В 1998 американська письменниця і журналістка Сільвія Назар видала книгу [3] про долю Джона Неша, нобелівського лауреата з економіки і вченого в галузі теорії ігор; а в 2001 за мотивами книги був знятий фільм " Ігри розуму ". Деякі американські телевізійні шоу, наприклад," Friend or Foe "," Alias ​​"або" NUMB3RS ", періодично посилаються на теорію у своїх епізодах.

Дж. Неш в 1949 році пише дисертацію з теорії ігор, через 45 років він отримує Нобелівську премію з економіки. Дж. Неш після закінчення Політехнічного інституту Карнегі з двома дипломами - бакалавра і магістра - вступив до Прінстонський університет, де відвідував лекції Джона фон Неймана. У своїх працях Дж. Неш розробив принципи "управлінської динаміки". Перші концепції теорії ігор аналізували антагоністичні ігри, коли є переможені і виграли за їх рахунок гравці. Неш розробляє методи аналізу, в яких всі учасники або виграють, або терплять поразку. Ці ситуації отримали назви "Рівновага по Нешу", або "некооперативного рівновагу", в ситуації сторони використовують оптимальну стратегію, що і призводить до створення стійкої рівноваги. Гравцям вигідно зберігати цю рівновагу, оскільки будь-яка зміна погіршить їхнє становище. Ці роботи Дж. Неша зробили серйозний внесок у розвиток теорії ігор, були переглянуті математичні інструменти економічного моделювання. Дж. Неш показує, що класичний підхід до конкуренції А. Сміта, коли кожен сам за себе, неоптимальний. Більш оптимальні стратегії, коли кожен намагається зробити краще для себе, роблячи краще для інших.

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

У 1960 - 1970 рр.. інтерес до теорії ігор згасає, незважаючи на значні математичні результати, отримані на той час. З середини 1980-х рр.. починається активне практичне використання теорії ігор, особливо в економіці та менеджменті. За останні 20 - 30 років значення теорії ігор і інтерес значно зростає, деякі напрямки сучасної економічної теорії неможливо викласти без застосування теорії ігор.

Великим внеском у застосування теорії ігор стала робота Томаса Шеллінга, нобелівського лауреата з економіки 2005 р. "Стратегія конфлікту". Т. Шеллінг розглядає різні "стратегії" поведінки учасників конфлікту. Ці стратегії збігаються з тактиками управління конфліктами і принципами аналізу конфліктів в конфліктології (це психологічна дисципліна) і в управлінні конфліктами в організації (теорія менеджменту). У психології та інших науках використовують слово "гра" в інших сенсах, ніж чим у математиці. Деякі психологи і математики скептично ставляться до використання цього терміна в інших сенсах, що склалися раніше. Культурологічне поняття гри було дано в роботі Йохана Хейзінга Homo Ludens (статті з історії культури), автор говорить про використання ігор у правосудді, культурі, етики .. говорить про те, що гра старше самої людини, так як тварини теж грають. Поняття гри зустрічається в концепції Еріка Берна "Ігри, в які грають люди, люди, які грають в ігри". Це суто психологічні ігри, засновані на трансакционном аналізі. Поняття гри у Й. Хезінга відрізняється від інтерпретації гри в теорії конфліктів та математичної теорії ігор. Ігри також використовуються для навчання в бізнес-кейсах, семінарах Г. П. Щедровицького, основоположника організаційно-діяльнісного підходу. Під час Перебудови в СРСР Г. П. Щедровицький провів безліч ігор з радянськими керівниками. За психологічним напруженням ОДГ (організаційно-діяльні ігри) були такі сильні, що служили потужним каталізатором змін в СРСР. Зараз у Росії склався цілий рух ОДГ. Критики відзначають штучну унікальність ОДГ. Основою ОДГ став Московський методологічний гурток (ММК).

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

Нобелівськими лауреатами з економіки за досягнення в галузі теорії ігор та економічної теорії стали: Роберт Ауманн, Райнхард Зелтен, Джон Неш, Джон Харсаньі, Вільям Викра, Джеймс Міррліс, Томас Шеллінг, Джордж Акерлоф, Майкл Спенс, Джозеф Стігліц, Леонід Гурвіц, Ерік Мескін, Роджер Майерсон.


2. Подання ігор

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

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

2.1. Екстенсивна форма

Гра "Ультиматум" в екстенсивної формі

Ігри в екстенсивної, або розширеної, формі [5] представляються у вигляді орієнтованого дерева, де кожна вершина відповідає ситуації вибору гравцем своєї стратегії. Кожному гравцеві сопоставлен цілий рівень вершин. Платежі записуються внизу дерева, під кожною листової вершиною.

На малюнку ліворуч - гра для двох гравців. Гравець 1 ходить першим і вибирає стратегію F або U. Гравець 2 аналізує свою позицію і вирішує - вибрати стратегію A або R. Швидше за все перший гравець вибере U, а другий - A (для кожного з них це оптимальні стратегії); тоді вони отримають відповідно 8 і 2 очки.

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


2.2. Нормальна форма

Гравець 2
стратегія 1
Гравець 2
стратегія 2
Гравець 1
стратегія 1
4, 3 -1, -1
Гравець 1
стратегія 2
0, 0 3, 4
Нормальна форма для гри з 2 гравцями, у кожного з яких по 2 стратегії.

У нормальній, або стратегічної, формі гра описується платіжної матрицею. [6] Кожна сторона (точніше, вимірювання) матриці - це гравець, рядки визначають стратегії першого гравця, а стовпці - другого. На перетині двох стратегій можна побачити виграші, які отримають гравці. У прикладі праворуч, якщо гравець 1 вибирає першу стратегію, а другий гравець - другу стратегію, то на перетині ми бачимо (-1, -1), це означає, що в результаті ходу обидва гравці втратили по одному очку.

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


2.3. Характеристична функція

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

Підстави такого підходу можна знайти ще в книзі фон Неймана і Моргенштерна. Вивчаючи нормальну форму для коаліційних ігор, вони розсудили, що якщо в грі з двома сторонами утворюється коаліція C, то проти неї виступає коаліція N \ C. Утворюється як би гра для двох гравців. Але так як варіантів можливих коаліцій багато (а саме 2 N, де N - кількість гравців), то виграш для C буде деякою характеристичною величиною, яка від складу коаліції. Формально игра в такой форме (также называемая TU-игрой [7]) представляется парой (N, v), где N - множество всех игроков, а v : 2 NR - это характеристическая функция.

Подобная форма представления может быть применена для всех игр, в том числе без трансферабельной полезности. В настоящее время существуют способы перевести любую игру из нормальной формы в характеристическую, но преобразование в обратную сторону возможно не во всех случаях.


3. Применение теории игр

Теория игр, как один из подходов в прикладной математике, применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин "теория игр". Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге "Эволюция и теория игр". Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения. Вообще говоря, первые теоретико-игровые аргументы, объясняющие правильное поведения, высказывались еще Платоном.


3.1. Описание и моделирование

Первоначально теория игр использовалась для описания и моделирования поведения человеческих популяций. Некоторые исследователи считают, что с помощью определения равновесия в соответствующих играх они могут предсказать поведение человеческих популяций в ситуации реальной конфронтации. Такой подход к теории игр в последнее время подвергается критике по нескольким причинам. Во-первых, предположения, используемые при моделировании, зачастую нарушаются в реальной жизни. Исследователи могут предполагать, что игроки выбирают поведения, максимизирующее их суммарную выгоду (модель экономического человека), однако на практике человеческое поведение часто не соответствует этой предпосылке. Существует множество объяснений этого феномена - нерациональность, моделирование обсуждения, и даже различные мотивы игроков (включая альтруизм). Авторы теоретико-игровых моделей возражают на это, говоря, что их предположения аналогичны подобным предположениям в физике. Поэтому даже если их предположения не всегда выполняются, теория игр может использовать как разумная идеальная модель, по аналогии с такими же моделями в физике. Однако, на теорию игр обрушился новый вал критики, когда в результате экспериментов было выявлено, что люди не следуют равновесным стратегиям на практике. Например, в играх "Сороконожка", "Диктатор" участники часто не используют профиль стратегий, составляющий равновесие по Нешу. Продолжаются споры о значении подобных экспериментов. Согласно другой точке зрения, равновесие по Нешу не является предсказанием ожидаемого поведения, но лишь объясняет, почему популяции, уже находящиеся в равновесии по Нешу, остаются в этом состоянии. Однако вопрос о том, как эти популяции приходят к равновесию Неша, остается открытым. Некоторые исследователи в поисках ответа на этот вопрос переключились на изучение эволюционной теории игр. Модели эволюционной теории игр предполагают ограниченную рациональность или нерациональность игроков. Несмотря на название, эволюционная теория игр занимается не только и не столько вопросами естественного отбора биологических видов. Этот раздел теории игр изучает модели биологической и культурной эволюции, а также модели процесса обучения.


3.2. Нормативный анализ (выявление наилучшего поведения)

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


4. Типы игр

4.1. Кооперативные и некооперативные

Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни.

Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот.

Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр.

Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.


4.2. Симметричные и несимметричные

А Б
А 1, 2 0, 0
Б 0, 0 1, 2
Несимметричная игра

Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков - симметричные. В частности, таковыми являются: " Дилемма заключённого ", " Охота на оленя ", " Ястребы и голуби ". [8] В качестве несимметричных игр можно привести "Ультиматум" или "Диктатор".

В примере справа игра на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так - ведь выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.


4.3. С нулевой суммой и с ненулевой суммой

А Б
А −1, 1 3, −3
Б 0, 0 −2, 2
Игра с нулевой суммой

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

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

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


4.4. Паралельні і послідовні

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

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


4.5. З повною або неповною інформацією

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

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

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


4.6. Ігри з нескінченним числом кроків

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

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


4.7. Дискретні та безперервні ігри

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


4.8. Метаігри

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

Примітки

  1. Цим вона відрізняється від теорії прийняття рішень
  2. Одне з видань російською мовою - institutiones.com/download/books/806-teoriya-igr-economichescoe-povedenie.html
  3. A Beautiful Mind: A Biography of John Forbes Nash, Jr., Winner of the Nobel Prize in Economics Simon & Schuster, 1994. ISBN 0-684-81906-6
  4. С. 10. Дубина І. М. Основи теорії економічних ігор: навчальний посібник .- М.: КноРус, 2010
  5. Не ототожнювати з позиційними іграми, які просто часто в такій формі представляють.
  6. У загальному випадку, по-перше, матриця не плоска, а n-мірна по числу гравців, а по-друге, гру в нормальній формі гру можна перевести у функцію, що обчислює виграші від обраних стратегій.
  7. від англ. trade union - професійна спілка..
  8. Правда, для цих ігор можна змінити платіжні матриці так, щоб ті стали несиметричними, але зазвичай цього не робиться.
  9. Таким чином, буде вважатися гра з "нульовою" або "ненульовий" сумою - залежить насправді від її формалізації.

Література

  • Петросян Л.А., Зенкевич Н.А., Сьоміна Є. А. Теорія ігор: Учеб. посібник для ун-тов - М .: Вища. шк., Книжковий будинок "Університет", 1998. - С. 304. - ISBN 5-06-001005-8, 5-8013-0007-4.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Стратегія (теорія ігор)
Гравець (теорія ігор)
Домінування (теорія ігор)
Ігор
Теорія
Теорія
М-теорія
Теорія 4P
Григор'єв, Ігор
© Усі права захищені
написати до нас
Рейтинг@Mail.ru