4551
правка
Сложность биматричного равновесия Нэша: различия между версиями
Перейти к навигации
Перейти к поиску
Сложность биматричного равновесия Нэша (посмотреть исходный код)
Версия от 23:38, 28 августа 2021
, 28 августа 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за <math>\mathbf{A}_i</math> вектор i-й строки матрицы <math>\mathbf{A}</math>, а за <math>\mathbf{B}_i</math> – вектор i-го столбца матрицы <math>\mathbf{B}</math>. <math>\epsilon</math>-поддерживаемое равновесие Нэша для игры <math>(\mathbf{A}, \mathbf{B})</math> представляет собой пару смешанных стратегий <math>(\mathbf{x}^*, \mathbf{y}^*)</math>, такую, что | С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за <math>\mathbf{A}_i</math> вектор i-й строки матрицы <math>\mathbf{A}</math>, а за <math>\mathbf{B}_i</math> – вектор i-го столбца матрицы <math>\mathbf{B}</math>. <math>\epsilon</math>-поддерживаемое равновесие Нэша для игры <math>(\mathbf{A}, \mathbf{B})</math> представляет собой пару смешанных стратегий <math>(\mathbf{x}^*, \mathbf{y}^*)</math>, такую, что: | ||
<math>\mathbf{A}_i \mathbf{y}^* > \mathbf{A}_j \mathbf{y}^* + \epsilon \implies x_j^* = 0, \forall i, j : 1 \le i, j \le m</math>; | |||
Определение 1 (2-NASH и NASH). | <math>(\mathbf{x}^*)^T \mathbf{B}_i > (\mathbf{x}^*)^T \mathbf{B}_j + \epsilon \implies y_j^* = 0, \forall i, j : 1 \le i, j \le n</math>. | ||
'''Определение 1 (2-NASH и NASH)'''. Входом задачи 2-NASH является пара <math>(\mathcal{G}, 0^k)</math>, где <math>\mathcal{G}</math> – биматричная игра, а выходом – </math>2^{-k}</math>-поддерживаемое равновесие Нэша для игры <math>\mathcal{G}</math>. Входом задачи NASH является биматричная игра <math>\mathcal{G}</math>, выходом – точное равновесие Нэша для <math>\mathcal{G}</math>. | |||
== Основные результаты == | == Основные результаты == | ||