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

Принцип откровения - это основополагающий принцип в конструкции механизмов . В нем говорится, что если функция социального выбора может быть реализована с помощью произвольного механизма (т. Е. Если этот механизм имеет равновесный результат, соответствующий результату функции социального выбора), то та же функция может быть реализована с помощью совместимого со стимулами прямого -механизм (т.е. когда игроки правдиво сообщают о типе) с одинаковым исходом равновесия (выплатами). [1] : 224–225

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

Этот принцип существует в двух вариантах, соответствующих двум разновидностям совместимости по стимулам :

Пример [ править ]

Рассмотрим следующий пример. Есть определенный элемент, который Алиса оценивает как, а Боб - как . Правительству необходимо решить, кто и на каких условиях получит этот товар.

  • Функция социального выбора - это функция, которая сопоставляет набор индивидуальных предпочтений с социальным результатом. Примером функции является утилитарная функция, которая гласит: «отдайте предмет тому, кто его больше всего ценит». Мы обозначаем функцию социального выбора через Soc, а рекомендуемый результат с учетом набора предпочтений - через Soc (Prefs) .
  • Механизм представляет собой правило , которое отображает набор отдельных действий к социальному результату. Механизм Mech вызывает игру, которую мы обозначаем Game (Mech) .
  • Говорят, что механизм Mech реализует функцию социального выбора Soc, если для каждой комбинации индивидуальных предпочтений существует равновесие по Нэшу в игре (Mech), в котором результатом является Soc (Prefs) . Вот два примера механизмов:
    • «Каждый человек говорит число от 1 до 10. Предмет дается тому человеку, который говорит наименьшее число; если оба говорят одно и то же число, то предмет отдается Алисе». Этот механизм НЕ реализует утилитарную функцию, поскольку для каждого человека, который хочет предмет, является доминирующей стратегией сказать «1» независимо от его / ее истинной ценности. Это означает, что в равновесии предмет всегда передается Алисе, даже если Боб ценит его больше.
    • Аукцион первой цены с закрытой заявкой - это механизм, реализующий утилитарную функцию. Например, если , то любой профиль действия, в котором Боб предлагает больше, чем Алиса, и обе ставки находятся в диапазоне, является равновесием Нэша, в котором элемент переходит к Бобу. Кроме того, если оценки Алисы и Боба являются случайными величинами, полученными независимо от одного и того же распределения, то существует байесовское равновесие по Нэшу, при котором предмет переходит к участнику торгов с наибольшей стоимостью.
  • Прямой механизм представляет собой механизм , в котором набор действий , доступных для каждого игрока только множество возможных предпочтений игрока.
  • Непосредственный механизм Мех называется байесовский-Nash- Стимул-совместимый (BNIC) , если существует байесовское равновесие Нэша в игре (Mech) , в котором все игроки показывают свои истинные предпочтения. Вот некоторые примеры прямых механизмов:
    • «Каждый человек говорит, насколько он ценит предмет. Предмет дается тому человеку, который сказал наибольшую ценность. В случае ничьей предмет передается Алисе». Этот механизм НЕ ЯВЛЯЕТСЯ BNIC, так как игрок, который хочет предмет, будет лучше, если скажет максимально возможное значение, независимо от его истинного значения.
    • Аукцион с запечатанными предложениями первой цены также НЕ ЯВЛЯЕТСЯ BNIC, поскольку победитель всегда выигрывает, предлагая наименьшее значение, которое немного выше ставки проигравшего.
    • Однако, если известно распределение оценок игроков, то существует вариант, который является BNIC и реализует утилитарную функцию.
    • Более того, известно, что аукцион второй цены - это BNIC (это даже IC в более сильном смысле - IC с доминирующей стратегией). Дополнительно он выполняет утилитарную функцию.

Доказательство [ править ]

Предположим, у нас есть произвольный механизм Mech , реализующий Soc .

Мы конструируем прямой механизм Mech ', который является правдивым и реализует Soc .

Mech ' просто имитирует стратегии равновесия игроков в игре ( Mech ). Т.е.:

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

Сообщение об истинных оценках в Mech ' похоже на игру в стратегии равновесия в Mech . Следовательно, сообщение истинных оценок является равновесием по Нэшу в механизме , как и желательно. Более того, равновесные выплаты такие же, как и хотелось бы.

В коррелированном равновесии [ править ]

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

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

  • Конструкция механизма
  • Поощрительная совместимость
  • Рынок лимонов
  • равновесие по Нэшу
  • Теория игры
  • Ограниченная эффективность Парето
  • Теорема Майерсона – Саттертуэйта

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

  1. ^ Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
  2. ^ Гиббард, А. 1973. Манипулирование схемами голосования: общий результат. Econometrica 41, 587–601.
  3. ^ Дасгупта, П., Хаммонд, П. и Маскин, Э. 1979. Реализация правил социального выбора: некоторые результаты по совместимости стимулов. Обзор экономических исследований 46, 185–216.
  4. ^ Holmstrom, B. 1977. О стимулах и контроле в организациях. Кандидат наук. дипломная работа Стэнфордского университета.
  5. ^ Майерсон, Р. 1979. Стимулирующая совместимость и проблема торга. Econometrica 47, 61–73.