Алгоритмический дизайн механизмов: различия между версиями

(3) Различные алгоритмические модели: распространенные модели вычислительных наук изменяют «базовую установку», что приводит к неожиданным трудностям при попытке использовать подход ВКГ (например, онлайн-модель, где входные данные раскрываются со временем; это распространено в вычислительных науках, но изменяет неявную установку, лежащую в основе механизма ВКГ). Это актуально даже в том случае, если целью остается максимизация благосостояния.

Для разрешения любой из этих трудностей требуется разработка механизма, отличного от ВКГ. Какие инструменты анализа следует использовать для этой цели? В экономике и классических подходах к дизайну механизмов стандартом является анализ среднего случая, который опирается на знание исходного распределения. С другой стороны, вычислительные науки обычно предпочитают избегать сильных предположений о распределении и использовать анализ для наихудшего случая. Это различие является еще одной причиной уникальности ответов, которые дает алгоритмический дизайн механизмов. Далее описываются некоторые новые результаты, появившиеся в результате интеграции вычислительных наук и экономики. Многие другие направления исследований, использующие инструменты алгоритмического дизайна механизмов, описаны в следующих статьях: [[Ценообразование рекламных объявлений]], [[Конкурентные аукционы]], [[Аукционы с доказанным присутствием фиктивных участников]], [[Обобщенный аукцион Викри]], [[Ранжирование совместимых стимулов]], [[Механизм для однопараметрических агентов с одним покупателем/продавцом]], [[Многотоварные аукционы]], [[Позиционные аукционы]], [[Правдивая многоадресная рассылка]].

Существуют два разных, но тесно связанных направления исследований. Первое представляет собой серию работ, изучающих «цену анархии» заданной системы. Эти работы анализируют ''существующие'' системы, пытаясь количественно оценить потерю социальной эффективности из-за эгоистичного характера участников, в то время как подход алгоритмического дизайна механизмов заключается в том, чтобы понять, как следует проектировать новые системы. Подробнее об этом см. статью «Цена анархии». Второе касается алгоритмического исследования различных способов вычисления равновесий. Эти работы привносят вычислительные аспекты в экономику и теорию игр, поскольку задаются вопросом, какие представления о равновесии разумно принять, если требуется вычислительная эффективность; а работы, описанные здесь, привносят теорию игр и экономику в вычислительные науки и теорию алгоритмов, поскольку задаются вопросом, какие алгоритмы разумно разработать, если требуется устойчивость к эгоистичному поведению. Подробнее об этом см., например, статьи [[Алгоритмы для равновесия Нэша]] и [[Равновесие в общем случае]].