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

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