Алгоритмическая теория игр ( AGT ) — это область на стыке теории игр и компьютерных наук , целью которой является понимание и разработка алгоритмов в стратегических средах.
Обычно в задачах Алгоритмической теории игр входные данные для данного алгоритма распределяются между многими игроками, которые имеют личный интерес в выходных данных. В таких ситуациях агенты могут не сообщать о входных данных правдиво из-за своих личных интересов. Мы можем рассматривать Алгоритмическую теорию игр с двух точек зрения:
Помимо обычных требований при проектировании классических алгоритмов (например, полиномиальное время выполнения , хороший коэффициент аппроксимации), разработчик также должен заботиться об ограничениях стимулов.
В 1999 году основополагающая работа Ноама Нисана и Амира Ронена [1] привлекла внимание сообщества теоретической информатики к разработке алгоритмов для эгоистичных (стратегических) пользователей. Как они утверждают в аннотации:
Мы рассматриваем алгоритмические проблемы в распределенной среде, где участники не могут предполагать, что будут следовать алгоритму, а скорее их собственным интересам. Поскольку такие участники, называемые агентами, способны манипулировать алгоритмом, разработчик алгоритма должен заранее убедиться, что интересы агентов наилучшим образом удовлетворяются путем правильного поведения. Следуя понятиям из области проектирования механизмов, мы предлагаем структуру для изучения таких алгоритмов. В этой модели алгоритмическое решение украшено выплатами участникам и называется механизмом. Выплаты должны быть тщательно подобраны, чтобы мотивировать всех участников действовать так, как желает разработчик алгоритма. Мы применяем стандартные инструменты проектирования механизмов к алгоритмическим проблемам и, в частности, к задаче о кратчайшем пути.
В этой статье впервые был введен термин « проектирование алгоритмических механизмов» , и комитет по присуждению премии Гёделя 2012 года признал ее одной из «трех статей, заложивших основу развития алгоритмической теории игр» [2] .
Другие две статьи, цитируемые в премии Гёделя 2012 года за фундаментальный вклад в алгоритмическую теорию игр, ввели и развили концепцию «Цены анархии». В своей статье 1999 года «Равновесия в худшем случае» [3] Куцупиас и Пападимитриу предложили новую меру деградации эффективности системы из-за эгоистичного поведения ее агентов: соотношение между эффективностью системы в оптимальной конфигурации и ее эффективностью в наихудшем равновесии Нэша. (Термин «Цена анархии» появился только пару лет спустя. [4] )
Интернет создал новую экономику — как основу для обмена и коммерции, так и сам по себе. Вычислительная природа Интернета позволила использовать вычислительные инструменты в этой новой развивающейся экономике. С другой стороны, сам Интернет является результатом действий многих. Это было новым для классического подхода к вычислениям «сверху вниз», который существовал до того времени. Таким образом, теория игр — это естественный способ рассматривать Интернет и взаимодействия в нем, как человеческие, так и механические.
Теория игр изучает равновесия (например, равновесие Нэша ). Равновесие обычно определяется как состояние, в котором ни один игрок не имеет стимула менять свою стратегию. Равновесия встречаются в нескольких областях, связанных с Интернетом, например, в финансовых взаимодействиях и балансировке нагрузки связи [ требуется ссылка ] . Теория игр предоставляет инструменты для анализа равновесий, и общий подход заключается в том, чтобы «найти игру», то есть формализовать определенные интернет-взаимодействия как игру и вывести связанные с ними равновесия.
Перефразирование проблем в терминах игр позволяет анализировать интернет-взаимодействия и строить механизмы для удовлетворения определенных требований. Если можно показать, что равновесия существуют, необходимо ответить на следующий вопрос: можно ли найти равновесие, причем за разумное время? Это приводит к анализу алгоритмов поиска равновесий. Особое значение имеет класс сложности PPAD , который включает в себя множество задач в алгоритмической теории игр.
Проектирование механизмов — это подраздел экономики, который занимается оптимизацией в условиях ограничений стимулирования. Проектирование алгоритмических механизмов рассматривает оптимизацию экономических систем в условиях требований вычислительной эффективности. Типичные изучаемые цели включают максимизацию доходов и максимизацию общественного благосостояния.
Понятия цены анархии и цены стабильности были введены для того, чтобы охватить потерю производительности системы из-за эгоистичного поведения ее участников. Цена анархии охватывает наихудшую производительность системы в равновесии относительно оптимальной возможной производительности. [5] Цена стабильности , с другой стороны, охватывает относительную производительность наилучшего равновесия системы. [6] Эти концепции являются аналогами понятия коэффициента аппроксимации в разработке алгоритмов.
Существование равновесия в игре обычно устанавливается с помощью неконструктивных теорем о неподвижной точке . Эффективных алгоритмов для вычисления равновесий Нэша не известно . Задача является полной для класса сложности PPAD даже в играх с двумя игроками. [7] Напротив, коррелированные равновесия могут быть эффективно вычислены с помощью линейного программирования, [8] а также изучены с помощью беспроигрышных стратегий. [9]
Вычислительный социальный выбор изучает вычислительные аспекты социального выбора , агрегацию предпочтений отдельных агентов. Примерами служат алгоритмы и вычислительная сложность правил голосования и формирования коалиций. [10]
Другие темы включают:
И площадь имеет разнообразное практическое применение: [11] [12]
Статьи по алгоритмической теории игр часто публикуются в журналах по теории игр, таких как GEB , [15] в экономических журналах, таких как Econometrica , и в журналах по компьютерным наукам, таких как SICOMP . [16]