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