Разработка механизмов

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

Definition

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

Scope

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

Core questions

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

Key concepts

• общественный выбор и агрегирование предпочтений
• совместимость стимулов (правдивость)
• реализация доминирующей стратегии
• принцип выявления
• аукционы
• аукцион Викри со второй ценой
• механизм Викри-Кларка-Гроувса (VCG)
• эффективность и индивидуальная рациональность

Key theories

Совместимость стимулов и аукцион со второй ценой

Аукцион Викри со второй ценой (с закрытыми ставками), где победитель платит вторую по величине ставку, делает правдивое предложение доминирующей стратегией, демонстрируя, как тщательная разработка правил может вызвать честное поведение у эгоистичных агентов.

Механизмы Викри-Кларка-Гроувса

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

Принцип выявления

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

Clinical relevance

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

History

Разработка механизмов выросла из экономической теории, при этом анализ аукционов Викри (1961) и более поздние вклады Кларка и Гроувса сформировали семейство VCG. С конца 1990-х годов информатика добавила изучение вычислительной разрешимости и аппроксимации, что привело к алгоритмической разработке механизмов, изложенной в таких текстах, как «Алгоритмическая теория игр» (2007).

Key figures

• William Vickrey
• Edward H. Clarke
• Theodore Groves
• Noam Nisan
• Tim Roughgarden

Seminal works

• vickrey1961
• shoham2009
• nisan2007

Frequently asked questions

Почему разработка механизмов называется обратной теорией игр?

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

Почему аукцион со второй ценой поощряет правдивое предложение?

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