WikiDer > Принцип откровения

Revelation principle

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

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

Принцип представлен в двух вариантах, соответствующих двум вкусам совместимость по стимулам:

Пример

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

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

Доказательство

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

Строим прямой механизм Мех ' это правдиво и реализует Soc.

Мех ' просто моделирует равновесные стратегии игроков в игре (Мех). То есть:

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

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

В коррелированном равновесии

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

Смотрите также

Рекомендации

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