Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Механизм называется стимул-совместимый ( IC ) , если каждый участник может достичь лучшего результата для себя только действуя в соответствии с их истинных предпочтений. [1] : 225 [2]

Есть несколько различных степеней совместимости стимулов: [3]

  • Более сильная степень - это совместимость по стимулам доминирующей стратегии ( DSIC ). [1] : 415 Это означает, что установление правды - это слабо доминирующая стратегия , т.е. вам лучше или, по крайней мере, не хуже, если вы будете правдивы, независимо от того, что делают другие. В механизме DSIC стратегические соображения не могут помочь любому агенту достичь лучших результатов, чем правда; следовательно, такие механизмы также называют стратегически устойчивыми [1] : 244,752 или правдивыми . [1] : 415 (См. Стратегия защиты )
  • Более слабая степень - это совместимость по стимулам Байеса-Нэша ( BNIC ). [1] : 416 Это означает, что существует байесовское равновесие по Нэшу, в котором все участники раскрывают свои истинные предпочтения. Т.е., если все остальные действуют правдиво, то для вас тоже лучше или, по крайней мере, не хуже, быть правдивым. [1] : 234

Каждый механизм DSIC также является BNIC, но механизм BNIC может существовать, даже если механизма DSIC не существует.

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

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

В рандомизированных механизмах [ править ]

Рандомизированный механизм - это распределение вероятностей по детерминированным механизмам. Есть два способа определить стимулирующую совместимость рандомизированных механизмов: [1] : 231–232

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

Принципы откровения [ править ]

Основная статья: Принцип откровения

Известный принцип Откровения существует в двух вариантах, соответствующих двум разновидностям совместимости по стимулам:

  • Принцип раскрытия доминирующей стратегии гласит, что каждая функция социального выбора, которая может быть реализована в доминирующих стратегиях, может быть реализована с помощью механизма DSIC.
  • Принцип откровения Байеса-Нэша гласит, что каждая функция социального выбора, которая может быть реализована в равновесии Байеса-Нэша ( байесовская игра , т.е. игра неполной информации), может быть реализована с помощью механизма BNIC.

См. Также [ править ]

Ссылки [ править ]

  1. ^ a b c d e f g Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
  2. ^ «Поощрительная совместимость | теория игр» . Британская энциклопедия . Проверено 25 мая 2020 .
  3. ↑ Джексон, Мэтью (8 декабря 2003 г.). «Теория механизмов» (PDF) . Оптимизация и исследование операций .