Войти
Алгоритмическая теория игр - область пересечения теории игр и компьютера наука, с целью понимания и разработки алгоритмов в стратегической среде.
Обычно в задачах алгоритмической теории игр входные данные для данного алгоритма распределяются между многими игроками, которые лично заинтересованы в выходе. В таких ситуациях агенты могут не сообщать правду о вводе из-за своих личных интересов. Мы можем рассматривать алгоритмическую теорию игр с двух точек зрения:
В дополнение к обычным требованиям классической разработки алгоритмов, например, полиномиальному времени выполнения, хорошему коэффициенту аппроксимации... разработчик также должен заботиться об ограничениях стимулов.
В 1999 году основополагающая статья Нисана и Ронена привлекла внимание сообщества теоретиков информатики. разработке алгоритмов для эгоистичных (стратегических) пользователей. Как они утверждают в аннотации:
Мы рассматриваем алгоритмические проблемы в распределенной среде, где участники не могут предположить, что следуют алгоритму, а скорее следуют своим собственным интересам. Поскольку такие участники, называемые агентами, способны манипулировать алгоритмом, разработчик алгоритма должен заранее убедиться, что интересы агентов наилучшим образом удовлетворяются за счет правильного поведения. Следуя представлениям из области проектирования механизмов, мы предлагаем основу для изучения таких алгоритмов. В этой модели алгоритмическое решение украшается выплатами участникам и называется механизмом. Платежи следует тщательно выбирать, чтобы мотивировать всех участников действовать так, как желает разработчик алгоритма. Мы применяем стандартные инструменты проектирования механизмов к алгоритмическим проблемам и, в частности, к задаче поиска кратчайшего пути.
В этой статье был введен термин разработка алгоритмических механизмов и он был отмечен премией Гёделя 2012 года как один из «трех документов, закладывающих фундамент роста в теории алгоритмических игр».
Две другие статьи, упомянутые в Премии Гёделя 2012 года за фундаментальный вклад в теорию алгоритмических игр представил и развил концепцию «Цена анархии». В своей статье 1999 года «Равновесие наихудшего случая» Кутсупиас и Пападимитриу предложили новую меру снижения эффективности системы из-за эгоистичного поведения ее агентов: соотношение между эффективностью системы при оптимальной конфигурации, и его эффективность при наихудшем равновесии по Нэшу. (Термин «Цена анархии» появился только пару лет спустя.)
Интернет создал новую экономику - как основу для обмена и торговли, и сам по себе. Вычислительная природа Интернета позволила использовать вычислительные инструменты в этой новой развивающейся экономике. С другой стороны, сам Интернет - результат действий многих. Это было новым для классического подхода к вычислениям «сверху вниз», который применялся до сих пор. Таким образом, теория игр - это естественный способ взглянуть на Интернет и взаимодействия в нем, как человеческие, так и механические.
Теория игр изучает равновесия (например, равновесие Нэша ). Равновесие обычно определяется как состояние, в котором ни у одного игрока нет стимула изменить свою стратегию. Равновесия можно найти в нескольких областях, связанных с Интернетом, например, в финансовых взаимодействиях и балансировке коммуникационной нагрузки. Теория игр предоставляет инструменты для анализа равновесий, и тогда общий подход состоит в том, чтобы «найти игру», то есть формализовать определенные взаимодействия в Интернете как игру и вывести связанные с ними равновесия.
Перефразирование проблем в терминах игр позволяет анализировать Интернет-взаимодействия и создавать механизмы для удовлетворения заданных требований. Если можно доказать, что существует равновесие, необходимо ответить на следующий вопрос: можно ли найти равновесие в разумные сроки? Это приводит к анализу алгоритмов нахождения равновесий. Особое значение имеет класс сложности PPAD, который включает множество проблем алгоритмической теории игр.
Разработка механизмов - это раздел экономики, который занимается оптимизацией при ограничениях стимулов. Разработка алгоритмического механизма рассматривает оптимизацию экономических систем в соответствии с требованиями вычислительной эффективности. Типичные изучаемые цели включают максимизацию доходов и максимизацию общественного благосостояния.
Понятия цена анархии и цена стабильности были введены для определения потери производительности системы из-за эгоистичное поведение его участников. Цена анархии отражает наихудшую производительность системы в состоянии равновесия по сравнению с возможной оптимальной производительностью. цена стабильности, с другой стороны, отражает относительную производительность наилучшего равновесия системы. Эти концепции аналогичны понятию коэффициента аппроксимации в разработке алгоритмов.
Существование равновесия в игре обычно устанавливается с помощью неконструктивных теорем о фиксированной точке. Нет известных эффективных алгоритмов для вычисления равновесия Нэша. Проблема завершена для класса сложности PPAD даже в играх для двух игроков. Напротив, коррелированные равновесия могут быть эффективно вычислены с помощью линейного программирования, а также изучены с помощью беспроигрышных стратегий.
Вычислительный социальный выбор изучает вычислительные аспекты социального выбора, совокупность индивидуальных предпочтений агентов. Примеры включают алгоритмы и вычислительную сложность правил голосования и формирования коалиций.
Другие темы включают:
И область имеет различные практические применения:
Статьи по теории алгоритмических игр часто публикуются в Журналы по теории игр, такие как GEB, экономические журналы, такие как Econometrica, и журналы по компьютерным наукам, такие как SICOMP.
