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

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

'''Определение 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>.

Бинарное отношение 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, в противном случае он возвращает специальную строку «нет».

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

Теорема [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» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для теории алгоритмических игр.