4430
правок
Приближенные решения для биматричного равновесия Нэша: различия между версиями
Материал из WEGA
Приближенные решения для биматричного равновесия Нэша (посмотреть исходный код)
Версия от 17:42, 8 марта 2012
, 8 марта 2012→Биматричные игры
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
''Биматричные игры'' [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами <math>n \times m</math> – A и B. n строк матриц A и B представляют множество действий первого игрока (''игрока по строкам''), m столбцов представляют множество действий второго игрока (''игрока по столбцам''). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш <math>a_{ij} \, </math>, а второй – выигрыш <math>b_{ij} \, </math>. В силу этого биматричные игры обозначаются как <math>\Gamma = \langle A,B \rangle</math>. | ''Биматричные игры'' [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами <math>n \times m</math> – A и B. n строк матриц A и B представляют множество действий первого игрока (''игрока по строкам''), m столбцов представляют множество действий второго игрока (''игрока по столбцам''). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш <math>a_{ij} \, </math>, а второй – выигрыш <math>b_{ij} \, </math>. В силу этого биматричные игры обозначаются как <math>\Gamma = \langle A,B \rangle</math>. | ||
''Стратегия'' для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности <math>\mathbf{x} \in \mathbb{P}^n</math>, а стратегия для игрока по столбцам – в виде вектора вероятности <math>\mathbf{y} \in \mathbb{P}^m</math>. Каждая точка экстремума <math>\mathbf{e_i} \in \mathbb{P}_n</math> (<math>\mathbf{e_j} \in \mathbb{P}^m</math>), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется ''чистой стратегией'' для игрока по строке (столбцу). ''Профиль стратегии'' (<math>\mathbf{x}, \mathbf{y}</math>) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии (<math>\mathbf{x}, \mathbf{y}</math>), игроки получают ''ожидаемый выигрыш'' <math>\mathbf{x}^T | ''Стратегия'' для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности <math>\mathbf{x} \in \mathbb{P}^n</math>, а стратегия для игрока по столбцам – в виде вектора вероятности <math>\mathbf{y} \in \mathbb{P}^m</math>. Каждая точка экстремума <math>\mathbf{e_i} \in \mathbb{P}_n</math> (<math>\mathbf{e_j} \in \mathbb{P}^m</math>), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется ''чистой стратегией'' для игрока по строке (столбцу). ''Профиль стратегии'' (<math>\mathbf{x}, \mathbf{y}</math>) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии (<math>\mathbf{x}, \mathbf{y}</math>), игроки получают ''ожидаемый выигрыш'' <math>\mathbf{x}^T A \mathbf{y}</math> (игрок по строкам) и <math>\mathbf{x}^T B \mathbf{y}</math> (игрок по столбцам). | ||
Если обе матрицы выигрышей принадлежат пространству [0, 1]<sup>m × n</sup>, то игра называется [0, 1]-биматричной, или положительно нормализованной, игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с ''выигравшими и проигравшими''. Биматричная игра <math>\langle | Если обе матрицы выигрышей принадлежат пространству [0, 1]<sup>m × n</sup>, то игра называется [0, 1]-биматричной, или ''положительно нормализованной'', игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с ''выигравшими и проигравшими''. Биматричная игра <math>\langle A, B \rangle</math> называется игрой с ''нулевой суммой'', если B = –А. | ||
== Приближенное равновесие Нэша == | == Приближенное равновесие Нэша == | ||
