Приближенные решения для биматричного равновесия Нэша: различия между версиями
Перейти к навигации
Перейти к поиску
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 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 A, B \rangle</math> называется игрой с ''нулевой суммой'', если B = –А. | Если обе матрицы выигрышей принадлежат пространству [0, 1]<sup>m × n</sup>, то игра называется [0, 1]-биматричной, или ''положительно нормализованной'', игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с ''выигравшими и проигравшими''. Биматричная игра <math>\langle A, B \rangle</math> называется игрой с ''нулевой суммой'', если B = –А. | ||
| Строка 21: | Строка 21: | ||
===Определение 1 (<math>\epsilon \, </math>-равновесие Нэша)=== | ===Определение 1 (<math>\epsilon \, </math>-равновесие Нэша)=== | ||
Для любого <math>\epsilon \, </math> > 0 | Для любого <math>\epsilon \, </math> > 0 профиль стратегии (<math>\mathbf{x}, \mathbf{y}</math>) является <math>\epsilon \, </math>-''равновесием Нэша'' для биматричной игры <math>\Gamma = \langle A,B \rangle</math> с матрицами <math>n</math> × <math>m</math>, если | ||
# Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>\mathbf{e_i}^T A \mathbf{_y} \le \mathbf{x}^T A \mathbf{_y}</math> + <math>\epsilon \, </math>; | # Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>\mathbf{e_i}^T A \mathbf{_y} \le \mathbf{x}^T A \mathbf{_y}</math> + <math>\epsilon \, </math>; | ||
# Для всех чистых стратегий <math> i \in \{1,\!...,m\}</math> игрока по столбцам <math>\mathbf{x}^T B \mathbf{_{ej}}\le \mathbf{x}^T B \mathbf{_y}</math> + <math>\epsilon \, </math>. | # Для всех чистых стратегий <math> i \in \{1,\!...,m\}</math> игрока по столбцам <math>\mathbf{x}^T B \mathbf{_{ej}}\le \mathbf{x}^T B \mathbf{_y}</math> + <math>\epsilon \, </math>. | ||
===Определение 2 (<math>\epsilon \, </math>-поддерживаемое равновесие Нэша)=== | ===Определение 2 (<math>\epsilon \, </math>-поддерживаемое равновесие Нэша)=== | ||
Для любого <math>\epsilon \, </math> > 0 | Для любого <math>\epsilon \, </math> > 0 профиль стратегии (<math>\mathbf{x}, \mathbf{y}</math>) является <math>\epsilon \, </math>''-поддерживаемым равновесием Нэша'' для биматричной игры <math>\Gamma= \langle A,B \rangle</math> с матрицами <math>n</math> × <math>m</math>, если | ||
# Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>x_i >\ 0 \rightarrow \mathbf{e_i}^T A \mathbf{_y} \ge \mathbf{e_k} A \mathbf{_k} - \epsilon</math> <math>\forall k \in \{1,\!...,n\}</math> | # Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>x_i >\ 0 \rightarrow \mathbf{e_i}^T A \mathbf{_y} \ge \mathbf{e_k} A \mathbf{_k} - \epsilon</math> <math>\forall k \in \{1,\!...,n\}</math> | ||
# Для всех чистых стратегий <math> j \in \{1,\!...,m\}</math> игрока по столбцам <math>y_i >\ 0 \rightarrow \mathbf{x_i}^T B \mathbf{_{ej}} \ge \mathbf{x}^T B \mathbf{_{ek}} - \epsilon</math> <math>\forall k \in \{1,\!...,m\}</math> | # Для всех чистых стратегий <math> j \in \{1,\!...,m\}</math> игрока по столбцам <math>y_i >\ 0 \rightarrow \mathbf{x_i}^T B \mathbf{_{ej}} \ge \mathbf{x}^T B \mathbf{_{ek}} - \epsilon</math> <math>\forall k \in \{1,\!...,m\}</math> | ||