Гра опукла

Матеріал з Вікіпедії — вільної енциклопедії.

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

Зміст

[ред.] Властивості опуклих ігор

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

Опукла гра називається скінченною, якщо для кожного гравця множина його чистих стратегій є компактною підмножиною деякого скінченновимірного лінійного простору, а функції виграшу всіх гравців полілінійні. Зокрема, скінченна антагоністична опукла гра задається трійкою <A, B, H>, де AEm, BEn, а функція H має вигляд:

H(r, s) = \sum_{i=1}^m \sum_{j=1}^n a_{ij} r_i s_j,\quad r \in A, s \in B.

Якщо μ та ν — розмірності множини оптимальних стратегій гравців A та B, а ρ — ранг матриці ||aij||, то μ + ν ≤ m + n - ρ.

[ред.] Приклад опуклої гри

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

[ред.] Джерела інформації

[ред.] Дивіться також


Статті теорії ігор

Типи ігор

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

Ситуації

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

Стратегія

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

Теореми

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

Ігри

Дилема в'язня