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

Теорема 1 (Викри-Кларка-Гровса, ВКГ). Зафиксируем любое множество альтернатив A и любую область V и предположим, что f: V ! A максимизирует общественное благосостояние. Тогда существуют цены p, такие, что механизм (f,p) является правдивым.

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

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

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