Некооперативна гра

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Некооперативна гра в нормальній формі[ред.ред. код]

Некооперативною грою в нормальній формі називається трійка \Gamma = \langle I, \ S_i, \ H_i\rangle, де  \ I  — множина учасників гри (сторін, гравців); \ S_i — множина стратегій учасника  \ i \in  I ; \ H_i — функція виграшу учасника \ i, визначена на множині ситуацій \ S = \prod\nolimits_{i \in I} S_i та відображає його в множину дійсних чисел.

Некооперативна гра в нормальній формі передбачає такий порядок розігрування.

1. Гравці одночасно та незалежно один від одного вибирають з множин \ S_i свої стратегії. Вектор стратегій  \ s= (s_1, s_2,..., s_n) всіх гравців являє собою ситуацію в грі.

2. Кожний гравець отримує виграш, який визначається значенням функції \ H_i(s) , на цьому взаємодія між ними припиняється.

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

Некооперативна гра в розгорнутій формі[ред.ред. код]

Некооперативна гра в розгорнутій формі з безліччю гравців  \ I представляється з використанням орієнтованого дерева (дерева гри) наступним чином.

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

  • початкова , яка є корнем дерева (вершиною, яка не має вхідних ребер);
  • проміжні , що мають вхідні та вихідні ребра;
  • термінальні , що мають лише вхідні ребра.

Початкова та проміжні позиції утворюють безліч нетермінальних позицій.

Для кожної вершини дерева  \ v , відповідної нетермінальний позиції, визначений гравець \ i, який здійснює в ній хід і безліч ходів цього гравця \ S_v. Кожному ходу \ s \in S_v відповідає ребро, що виходить з вершини \ v.

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

Для кожної вершини \ v, відповідної термінальної позиції, визначені функції виграшу всіх гравців \ H_i(v) .

Гра передбачає такий порядок розігрування:

1. Гра починається з початкової позиції.

2. У будь-якій нетермінальний позиції \ v гравець, що має в ній право ходу, вибирає хід \ s \in S_v, внаслідок чого гра потрапляє в наступну позицію, в яку входить ребро, відповідне ходу \ s. Якщо ця позиція є нетермінальною, то повторюється п. 2.

3. Якщо гра потрапляє у термінальну позицію \ v, то всі гравці отримують виграші \ H_i(v) , і гра завершується.

Принципи оптимальності[ред.ред. код]

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

Менш універсальними, використовуваними в окремих класах некооперативних ігор, є такі принципи:

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

Приклади[ред.ред. код]

Див. також[ред.ред. код]


Посилання[ред.ред. код]

  • [1] Некооперативна гра(рос.)
  • [2] Теорія некооперативних ігор(рос.)

Джерела[ред.ред. код]

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


Теорія ігор

Типи ігор

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

Ситуації

Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги 

Стратегія

змішана · оптимальна · поведінки · чиста 

Теореми

Максіміна принцип · Мінімаксу теорема

Ігри

Дилема в'язня · РВ-ПП