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

Бинарное отношение <math>R \subset \{ 0, 1 \}^* \times \{0, 1 \}^*</math> является ''полиномиально сбалансированным'', если существует полином ''p'', такой, что для всех пар <math>(x, y) \in R</math> верно <math>|y| \le p(|x|)</math>. Это отношение ''вычислимо за полиномиальное время'', если для каждой пары (x,y) можно решить, верно ли <math>(x, y) \in R</math>, за время, полиномиальное относительно |x| + |y|. <math>\mathcal NP</math>-полная задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом:

пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет».

Отношение R является ''полным'', если для каждого <math>x \in \{0, 1 \}^*</math> существует y, такое, что <math>(x, y) \in R</math>. Следуя [7], обозначим за <math>\mathcal TFNP</math> класс всех <math>\mathcal NP</math>-полных задач поиска, заданных полными отношениями. Задача поиска <math>Q_{R_1} \in \mathcal{TFNP}</math> ''полиномиально сводима'' к задаче <math>Q_{R_2} \in \mathcal{TFNP}</math>, если существует пара полиномиально вычислимых функций (f, g), таких, что для каждого x из <math>R_1</math> в случае, если y удовлетворяет условию <math>(f(x), y) \in R_2</math>, верно <math>(x, g(y)) \in R_1</math>. Более того, <math>Q_{R_1}</math> и <math>Q_{R_2}</math> полиномиально эквивалентны, если <math>Q_{R_2}</math> также сводима к <math>Q_{R_1}</math>.

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

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

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