Алгоритмическая теория игр - Algorithmic game theory

Алгоритмическая теория игр это область на пересечении теория игры и Информатика, с целью понимания и разработки алгоритмов в стратегический среды.

Как правило, в задачах алгоритмической теории игр входные данные для данного алгоритма распределяются между многими игроками, которые лично заинтересованы в выходе. В таких ситуациях агенты могут не правдиво сообщать о вводе из-за своих личных интересов. Мы можем рассматривать алгоритмическую теорию игр с двух точек зрения:

  • Анализ: посмотреть на текущие реализованные алгоритмы и проанализировать их с помощью инструментов теории игр: вычислить и доказать свойства на их Равновесия Нэша, цена анархии, динамика наилучшего отклика ...
  • дизайн: разрабатывать игры, обладающие хорошими теоретико-игровыми и алгоритмическими свойствами. Эта область называется алгоритмический механизм проектирования.

Помимо обычных требований при разработке классических алгоритмов, скажем, время работы с полиномиальным временем, хороший коэффициент приближения, ... дизайнер также должен заботиться об ограничениях стимулов.

История

Нисан-Ронен: новый фреймворк для изучения алгоритмов

В 1999 г. была опубликована основополагающая статья Нисан и Ронен [1] обратил внимание сообщества теоретиков информатики на разработку алгоритмов для эгоистичных (стратегических) пользователей. Как они утверждают в аннотации:

Мы рассматриваем алгоритмические проблемы в распределенной обстановке, когда не предполагается, что участники следуют алгоритму, а скорее следуют своим собственным интересам. Поскольку такие участники, называемые агентами, способны манипулировать алгоритмом, разработчик алгоритма должен заранее убедиться, что интересы агентов наилучшим образом удовлетворяются за счет правильного поведения. Следуя представлениям из области проектирования механизмов, мы предлагаем структуру для изучения таких алгоритмов. . В этой модели алгоритмическое решение украшается выплатами участникам и называется механизмом. Платежи следует выбирать тщательно, чтобы мотивировать всех участников действовать так, как желает разработчик алгоритма. Мы применяем стандартные инструменты проектирования механизмов к алгоритмическим задачам и, в частности, к задаче кратчайшего пути.

В этой статье был введен термин алгоритмический механизм проектирования и был признан 2012 Премия Гёделя комитет как один из «трех документов, закладывающих фундамент развития теории алгоритмических игр».[2]

Цена анархии

Основная статья: Цена анархии

Две другие статьи, упомянутые в Премии Геделя 2012 года за фундаментальный вклад в теорию алгоритмических игр, представили и развили концепцию «цены анархии». В своей статье 1999 г. "Равновесия наихудшего случая"[3] Кутсупиас и Пападимитриу предложила новую меру деградации эффективности системы из-за эгоистичного поведения ее агентов: соотношение между эффективностью системы при оптимальной конфигурации и ее эффективностью при наихудшем равновесии по Нэшу. (Термин «Цена анархии» появился всего пару лет спустя.[4])

Интернет как катализатор

Интернет создал новую экономику - как фундамент для обмена и торговли, так и сам по себе. Вычислительная природа Интернета позволила использовать вычислительные инструменты в этой новой развивающейся экономике. С другой стороны, сам Интернет - результат действий многих. Это было новым для классического подхода к вычислениям «сверху вниз», который применялся до сих пор. Таким образом, теория игр - это естественный способ взглянуть на Интернет и взаимодействия в нем, как человеческие, так и механические.

Теория игр изучает равновесия (такие как равновесие по Нэшу ). Равновесие обычно определяется как состояние, в котором ни у одного игрока нет стимула изменить свою стратегию. Равновесия можно найти в нескольких областях, связанных с Интернетом, например, в финансовых взаимодействиях и балансировке коммуникационной нагрузки.[нужна цитата ]. Теория игр предоставляет инструменты для анализа равновесий, и тогда общий подход состоит в том, чтобы «найти игру», то есть формализовать определенные взаимодействия в Интернете как игру и вывести связанные с ними равновесия.

Перефразируя проблемы в терминах игр, можно анализировать взаимодействие в Интернете и создавать механизмы для удовлетворения заданных требований. Если можно доказать, что существует равновесие, необходимо ответить на следующий вопрос: можно ли найти равновесие в разумные сроки? Это приводит к анализ алгоритмов для поиска равновесий. Особое значение имеет класс сложности. PPAD, включающий множество задач алгоритмической теории игр.

Направления исследований

Разработка алгоритмического механизма

Основная статья: Разработка алгоритмического механизма

Конструкция механизма это раздел экономики, который занимается оптимизацией при ограничениях по стимулам. Разработка алгоритмического механизма рассматривает оптимизацию экономических систем в соответствии с требованиями вычислительной эффективности. Типичные изучаемые цели включают максимизацию доходов и максимизацию общественного благосостояния.

Неэффективность равновесий

Концепции цена анархии и цена стабильности были введены, чтобы зафиксировать потерю производительности системы из-за эгоистичного поведения ее участников. В цена анархии фиксирует наихудшую производительность системы в состоянии равновесия относительно максимально возможной производительности.[5] В цена стабильности, с другой стороны, отражает относительную эффективность наилучшего равновесия системы.[6] Эти концепции являются аналогами понятия коэффициент аппроксимации в разработке алгоритмов.

Сложность поиска равновесия

Существование равновесия в игре обычно устанавливается с помощью неконструктивных теоремы о неподвижной точке. Нет известных эффективных алгоритмов вычислений Равновесия Нэша. Проблема завершена для класс сложности PPAD даже в играх на двоих.[7] Напротив, коррелированные равновесия можно эффективно вычислить с помощью линейного программирования,[8] а также узнал с помощью беспроигрышных стратегий.[9]

Вычислительный социальный выбор

Основная статья: Вычислительный социальный выбор

Вычислительные исследования социального выбора вычислительные аспекты социальный выбор, совокупность индивидуальных предпочтений агентов. Примеры включают алгоритмы и вычислительную сложность правил голосования и формирования коалиции.[10]

Другие темы включают:

Эта область имеет множество практических применений:[11][12]

Журналы и информационные бюллетени

  • ACM Сделки по экономике и вычислениям (TEAC) [13]
  • Биржи SIGEcom [14]

Статьи по теории алгоритмических игр часто также публикуются в журналах по теории игр, таких как GEB,[15] Экономические журналы, такие как Econometrica и журналы по компьютерным наукам, такие как SICOMP.[16]

Смотрите также

использованная литература

  1. ^ Нисан, Ноам; Ронен, Амир (1999), «Дизайн алгоритмического механизма», Материалы 31-го симпозиума ACM по теории вычислений (STOC '99), стр. 129–140, Дои:10.1145/301250.301287, ISBN  978-1581130676, S2CID  8316937
  2. ^ «ACM SIGACT вручает премию Гёделя за исследования, проливающие свет на последствия эгоистичного использования Интернета» (Пресс-релиз). Нью-Йорк. Ассоциация вычислительной техники. 2012-05-16. Архивировано из оригинал на 2013-07-18. Получено 2018-01-08.
  3. ^ Кутсупиас, Элиас; Пападимитриу, Христос (май 2009 г.). «Худшее равновесие». Обзор компьютерных наук. 3 (2): 65–69. Дои:10.1016 / j.cosrev.2009.04.003. Архивировано из оригинал на 2016-03-13. Получено 2018-01-08.
  4. ^ Пападимитриу, Христос (2001), «Алгоритмы, игры и Интернет», Материалы 33-го симпозиума ACM по теории вычислений (STOC '01), стр. 749–753, CiteSeerX  10.1.1.70.8836, Дои:10.1145/380752.380883, ISBN  978-1581133493, S2CID  207594967
  5. ^ Тим Рафгарден (2005). Эгоистичный путь и цена анархии. MIT Press. ISBN  0-262-18243-2.
  6. ^ *Аншелевич, Эллиот; Дасгупта, Анирбан; Клейнберг, Джон; Тардос, Ива; Векслер, Том; Roughgarden, Тим (2008). «Цена стабильности для проектирования сети с справедливым распределением затрат». SIAM J. Comput. 38 (4): 1602–1623. Дои:10.1137/070680096. S2CID  2839399.
  7. ^ *Чен, Си; Дэн, Сяотэ (2006). Урегулирование сложности равновесия по Нэшу для двух игроков. Proc. 47-й симпозиум. Основы компьютерных наук. С. 261–271. Дои:10.1109 / FOCS.2006.69. ECCC  TR05-140..
  8. ^ Papadimitriou, Christos H .; Roughgarden, Тим (2008). «Вычисление коррелированных равновесий в многопользовательских играх». J. ACM. 55 (3): 14:1–14:29. CiteSeerX  10.1.1.335.2634. Дои:10.1145/1379759.1379762. S2CID  53224027.
  9. ^ Фостер, Дин П .; Вохра, Ракеш В. (1996). «Калиброванное обучение и коррелированное равновесие». Игры и экономическое поведение.
  10. ^ Феликс Брандт; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча, ред. (2016), Справочник по вычислительному социальному выбору (PDF)
  11. ^ Тим Рафгарден (2016). Двадцать лекций по алгоритмической теории игр. Издательство Кембриджского университета. ISBN  9781316624791.
  12. ^ "EC'19 || 20-я конференция ACM по экономике и вычислениям".
  13. ^ TEAC
  14. ^ Биржи SIGEcom
  15. ^ Чавла, Шучи; Флейшер, Лиза; Хартлайн, Джейсон; Тим Рафгарден (2015), «Введение в специальный выпуск - теория алгоритмических игр - STOC / FOCS / SODA 2011», Игры и экономическое поведение, 92: 228–231, Дои:10.1016 / j.geb.2015.02.011
  16. ^ SICOMP

внешние ссылки

  • gambit.sourceforge.net - библиотека программного обеспечения теории игр и инструментов для построения и анализа конечных обширных и стратегических игр.
  • gamut.stanford.edu - набор игровых генераторов, предназначенных для тестирования теоретико-игровых алгоритмов.