Алгоритмическая теория игр

Алгоритмическая теория игр (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, doi : 10.1145/301250.301287 , ISBN 978-1581130676 , S2CID 8316937
^ «ACM SIGACT вручает премию Гёделя за исследования, освещающие последствия эгоистичного использования Интернета» (пресс-релиз). Нью-Йорк. Ассоциация вычислительной техники. 16 мая 2012 г. Архивировано из оригинала 18 июля 2013 г. Проверено 8 января 2018 г.
^ Куцупиас, Элиас; Пападимитриу, Христос (май 2009 г.). «Наихудшее равновесие» . Обзор компьютерных наук . 3 (2): 65–69. дои : 10.1016/j.cosrev.2009.04.003 . Архивировано из оригинала 13 марта 2016 г. Проверено 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). Эгоистичный маршрут и цена анархии . МТИ Пресс . ISBN 0-262-18243-2 .
^ * Аншелевич, Эллиот; Дасгупта, Анирбан; Кляйнберг, Джон; Тардос, Ева; Векслер, Том; Рафгарден, Тим (2008). «Цена стабильности проектирования сети со справедливым распределением затрат». СИАМ Дж. Компьютер . 38 (4): 1602–1623. дои : 10.1137/070680096 . S2CID 2839399 .
^ * Чен, Си; Дэн, Сяоте (2006). Урегулирование сложности равновесия Нэша для двух игроков . Учеб. 47-й симп. Основы информатики. стр. 261–271. дои : 10.1109/FOCS.2006.69 . ЕССС ТР05-140 . .
^ Пападимитриу, Христос Х.; Рафгарден, Тим (2008). «Вычисление коррелированных равновесий в многопользовательских играх». Дж. АКМ . 55 (3): 14:1–14:29. CiteSeerX 10.1.1.335.2634 . дои : 10.1145/1379759.1379762 . S2CID 53224027 .
^ Фостер, Дин П.; Вохра, Ракеш В. (1996). «Калиброванное обучение и коррелированное равновесие» . Игры и экономическое поведение .
^ Феликс Брандт; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча, ред. (2016), Справочник по вычислительному социальному выбору (PDF)
^ Тим Рафгарден (2016). Двадцать лекций по алгоритмической теории игр . Издательство Кембриджского университета . ISBN 9781316624791 .
^ «EC'19 || 20-я конференция ACM по экономике и вычислениям» .
^ ТЭАК
^ Биржи SIGEcom
^ Чавла, Сучи ; Флейшер, Лиза; Хартлайн, Джейсон; Тим Рафгарден (2015), «Введение в специальный выпуск – алгоритмическая теория игр – STOC/FOCS/SODA 2011», Games and Economic Behavior , 92 : 228–231, doi : 10.1016/j.geb.2015.02.011
^ СИКОМП

Джон фон Нейман , Оскар Моргенштерн (1944) Теория игр и экономического поведения . Принстонский университет. Нажимать. издание 2007 года: ISBN 978-0-691-13061-3
Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007), Алгоритмическая теория игр (PDF) , Кембридж, Великобритания: Издательство Кембриджского университета, ISBN 978-0-521-87282-9 .

Внешние ссылки [ править ]

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

[nr-1] Нисан, Ноам ; Ронен, Амир (1999), «Проектирование алгоритмических механизмов», Труды 31-го симпозиума ACM по теории вычислений (STOC '99) , стр. 129–140, doi : 10.1145/301250.301287 , ISBN 978-1581130676 , S2CID 8316937

[2] «ACM SIGACT вручает премию Гёделя за исследования, освещающие последствия эгоистичного использования Интернета» (пресс-релиз). Нью-Йорк. Ассоциация вычислительной техники. 16 мая 2012 г. Архивировано из оригинала 18 июля 2013 г. Проверено 8 января 2018 г.

[kp-3] Куцупиас, Элиас; Пападимитриу, Христос (май 2009 г.). «Наихудшее равновесие» . Обзор компьютерных наук . 3 (2): 65–69. дои : 10.1016/j.cosrev.2009.04.003 . Архивировано из оригинала 13 марта 2016 г. Проверено 8 января 2018 г.

[4] Пападимитриу, Христос (2001), «Алгоритмы, игры и Интернет», Труды 33-го симпозиума ACM по теории вычислений (STOC '01) , стр. 749–753, CiteSeerX 10.1.1.70.8836 , doi : 10.1145/ 380752.380883 , ISBN 978-1581133493 , S2CID 207594967

[5] Тим Рафгарден (2005). Эгоистичный маршрут и цена анархии . МТИ Пресс . ISBN 0-262-18243-2 .

[6] * Аншелевич, Эллиот; Дасгупта, Анирбан; Кляйнберг, Джон; Тардос, Ева; Векслер, Том; Рафгарден, Тим (2008). «Цена стабильности проектирования сети со справедливым распределением затрат». СИАМ Дж. Компьютер . 38 (4): 1602–1623. дои : 10.1137/070680096 . S2CID 2839399 .

[chen2005-7] * Чен, Си; Дэн, Сяоте (2006). Урегулирование сложности равновесия Нэша для двух игроков . Учеб. 47-й симп. Основы информатики. стр. 261–271. дои : 10.1109/FOCS.2006.69 . ЕССС ТР05-140 . .

[8] Пападимитриу, Христос Х.; Рафгарден, Тим (2008). «Вычисление коррелированных равновесий в многопользовательских играх». Дж. АКМ . 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 по экономике и вычислениям» .

[TEAC-13] ТЭАК

[14] Биржи SIGEcom

[15] Чавла, Сучи ; Флейшер, Лиза; Хартлайн, Джейсон; Тим Рафгарден (2015), «Введение в специальный выпуск – алгоритмическая теория игр – STOC/FOCS/SODA 2011», Games and Economic Behavior , 92 : 228–231, doi : 10.1016/j.geb.2015.02.011

[16] СИКОМП

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]