Сложность биматричного равновесия Нэша

Ключевые слова и синонимы

Равновесие Нэша в игре для двух игроков; игра для двух игроков; биматричная игра

Постановка задачи

В середине прошлого века Джон Нэш, изучая некооперативные игры общего вида [8], доказал, что существует набор смешанных стратегий, который сейчас принято называть равновесием Нэша, по одной для каждого игрока – такой, что ни один игрок не может получить преимущество, если изменит собственную стратегию в одностороннем порядке. С момента публикации теоремы Нэша исследователи работали над способами эффективного вычисления равновесия Нэша. Несмотря на то, что в последние полвека в этом направлении прилагались значительные усилия, не было достигнуто существенного прогресса в определении алгоритмической сложности, хотя для различных модифицированных версий были получены данные о сложности и разработаны алгоритмы.

Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является PPAD-полной (аргументы полиномиальной четности на ориентированных графах – polynomial parity argument, directed version) – этот класс сложности был введен Пападимитриу в работе [9]. Результаты в [4] основываются на технике, разработанной в [6]. Затем эта оценка сложности была улучшена для случая трех игроков Ченом и Денгом [1], а также Даскалакисом и Пападимитриу [5] – независимо друг от друга и с использованием разных доказательств. Наконец, Чен и Денг [2] доказали, что NASH – задача нахождения равновесия Нэша в биматричной игре (или игре для двух игроков) – является PPAD-полной.

Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера [math]\displaystyle{ m \times n }[/math], [math]\displaystyle{ \mathbf{A} = \big( a_{i, j} \big) }[/math] и [math]\displaystyle{ \mathbf{B} = \big( b_{i, j} \big) }[/math]. Если первый игрок выбирает действие i, а второй игрок – действие j, то их выигрыш составляет [math]\displaystyle{ a_{i, j} }[/math] и [math]\displaystyle{ b_{i, j} }[/math], соответственно. Смешанная стратегия игрока представляет собой распределение вероятностей над его выборами. Обозначим за [math]\displaystyle{ \mathbb{P}^n }[/math] множество всех векторов вероятностей в [math]\displaystyle{ \mathbb{R}^n }[/math], то есть неотрицательных векторов, сумма элементов которых равна 1. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры [math]\displaystyle{ \mathcal{G} = (\mathbf{A}, \mathbf{B}) }[/math] существует пара смешанных стратегий [math]\displaystyle{ (\mathbf{x}^* \in \mathbb{P}^m, \mathbf{y}^* \in \mathbb{P}^n) }[/math], называемая равновесием Нэша, такая, что для всех [math]\displaystyle{ \mathbf{x}^* \in \mathbb{P}^m }[/math] и [math]\displaystyle{ \mathbf{y}^* \in \mathbb{P}^n }[/math] выполняются соотношения [math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{A} \mathbf{y}^* \ge \mathbf{x}^T \mathbf{A} \mathbf{y}^* }[/math] и [math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^* \ge (\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^* }[/math].

С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за [math]\displaystyle{ \mathbf{A}_i }[/math] вектор i-й строки матрицы [math]\displaystyle{ \mathbf{A} }[/math], а за [math]\displaystyle{ \mathbf{B}_i }[/math] – вектор i-го столбца матрицы [math]\displaystyle{ \mathbf{B} }[/math]. [math]\displaystyle{ \epsilon }[/math]-поддерживаемое равновесие Нэша для игры [math]\displaystyle{ (\mathbf{A}, \mathbf{B}) }[/math] представляет собой пару смешанных стратегий [math]\displaystyle{ (\mathbf{x}^*, \mathbf{y}^*) }[/math], такую, что:

[math]\displaystyle{ \mathbf{A}_i \mathbf{y}^* \gt \mathbf{A}_j \mathbf{y}^* + \epsilon \implies x_j^* = 0, \forall i, j : 1 \le i, j \le m }[/math];

[math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{B}_i \gt (\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]\displaystyle{ (\mathcal{G}, 0^k) }[/math], где [math]\displaystyle{ \mathcal{G} }[/math] – биматричная игра, а выходом – [math]\displaystyle{ 2^{-k} }[/math]-поддерживаемое равновесие Нэша для игры [math]\displaystyle{ \mathcal{G} }[/math]. Входом задачи NASH является биматричная игра [math]\displaystyle{ \mathcal{G} }[/math], выходом – точное равновесие Нэша для [math]\displaystyle{ \mathcal{G} }[/math].

Основные результаты

Бинарное отношение R С f0; 1g x {0,1}* является полиномиально сбалансированным, если существует полином p такой, что для всех пар (x;y) 2 R верно jyj < p(jxj). Это отношение вычислимо за полиномиальное время, если для каждой пары (x,y) можно решить, верно ли (x; y) 2 R, за время, полиномиальное относительно jxj + jyj. NP-полная задача поиска QR, заданная R, определяется следующим образом: пустьдано x 2 f0;1}*. Если существует y, такое, что (x; y) 2 R, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет».

Отношение R является полным, если для каждого x 2 f0;1}* существует y такое, что (x;y) 2 R. Следуя [ ], обозначим за TFNP класс всех NP-полных задач поиска, заданных полными отношениями. Задача поиска QR1 2 TFNP полиномиально сводима к задаче QR2 2 TFNP, если существует пара полиномиально вычислимых функций (f,g) таких, что для каждого x из R1, если y удовлетворяет условию (f(x);y) 2 R2, верно (x;g(y)) 2 R1. Более того, QR1 и QR2 полиномиально эквивалентны, если QR2 также сводится к QR1.

Класс сложности PPAD является подклассом TFNP, содержащим все задачи поиска, которые полиномиально сводимы к:

Определение 2 (задача LEAFD). Входными данными задачи LEAFD является пара (M; 0n), где M определяет машину Тьюринга с полиномиальным временем работы, удовлетворяющую следующим условиям: 1. для каждого v 2 f0; 1gn, M(v) является упорядоченной парой (U1; U2) с мь м2 2 f0;1g U {«нет»}; 2. M(0n) = («нет»; 1n), и первая компонента M(1n) равна 0n.

Этот экземпляр определяет ориентированный граф G = (V, E) с V = f0; 1gn. Дуга (U; V) 2 E в том и только том случае, если vis – вторая компонента M(U), а u – первая компонента M(v).

Результатом решения задачи LEAFD является ориентированный лист G, отличный от 0n. Здесь вершина называется ориентированным листом, если сумма ее полустепени исхода и полустепени захода равна единице.

Задача поиска в PPAD называется полной в PPAD (или PPAD-полной), если существует редукция от LEAFD до нее за полиномиальное время.

Теорема [2]. Задачи 2-Nash и Nash являются PPAD-полными.

Применение

Концепция равновесия Нэша традиционно является одним из наиболее влиятельных инструментов в изучении многих дисциплин, связанных со стратегиями, таких как политология и экономическая теория. Распространение Интернета и изучение его анархической среды сделали равновесие Нэша неотъемлемой частью компьютерных наук. За последние десятилетия сообщество специалистов в области компьютерных наук внесло большой вклад в разработку эффективных алгоритмов для решения соответствующих задач. Полученная последовательность результатов [1, 2, 3, 4, 5, 6] впервые дает некоторые доказательства того, что задача нахождения равновесия Нэша, вероятно, является P-сложной. Эти результаты очень важны для активно развивающейся дисциплины – алгоритмической теории игр.

Открытые вопросы

Упомянутая последовательность работ показывает, что игры с (r + 1) игроками полиномиально сводимы к играм с r игроками для любого r > 2, но редукция осуществляется путем сведения игр с (r + 1) игроками сначала к задаче с фиксированной точкой, а затем к играм с r игроками. Существует ли естественная редукция, которая переходит непосредственно от игр с (r + 1)игроками к играм с r игроками? Подобная редукция могла бы обеспечить лучшее понимание поведения в многопользовательских играх.

Хотя многие считают, что PPAD является трудным для P, однако веских доказательств или интуитивных соображений в пользу этого мнения нет. Остается открытым естественный вопрос: можно ли строго доказать, что класс PPAD является трудным, при одном из общепринятых в теоретической информатике предположений, таких как «NP не находится в P» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для теории алгоритмических игр.

См. также

• Равновесие в общем случае
• Экономическое равновесие Леонтьева
• Неаппроксимируемость биматричного равновесия Нэша

Литература

1. Chen, X., Deng, X.: 3-Nash is ppad-complete. ECCC,TR05-134 (2005)

2. Chen, X., Deng, X.: Settling the complexity of two-player Nash-equilibrium. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 261-272

3. Chen, X., Deng, X., Teng, S.H.: Computing Nash equilibria: approximation and smoothed complexity. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 603-612

4. Daskalakis, C., Goldberg, P.W. Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC'06, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 71-78

5. Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC,TR05-139 (2005)

6. Goldberg, P.W., Papadimitriou, C.H.: Reducibility among equilibrium problems. In: STOC'06, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 61-70

7. Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comp. Sci. 81,317-324(1991)

8. Nash, J.F.: Equilibrium point in n-person games. In: Proceedings of the National Academy of the USA, vol. 36, issue 1, pp. 48^9 (1950)

9. Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comp. Syst. Sci. 48, 498-532(1994)