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

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

Принцип откровения показывает, что, хотя теорема Гиббарда доказывает невозможность разработки системы, которая всегда будет полностью неуязвима для стратегии (если мы не знаем, как будут вести себя игроки), возможно разработать систему, которая поощряет честность, учитывая концепцию решения (если соответствующее равновесие уникально). ^{[3] [4]}

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

Примеры

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

• Функция социального выбора — это функция, которая отображает набор индивидуальных предпочтений в оптимальный социальный результат. Примером функции является утилитарное правило , которое гласит: «отдай предмет тому, кто ценит его больше всего». Мы обозначаем функцию социального выбора как Soc , а ее рекомендуемый результат с учетом набора предпочтений как Soc(Prefs) .
• Механизм — это правило, которое отображает набор индивидуальных действий в социальный результат. Механизм Mech вызывает игру , которую мы обозначаем как Game(Mech) .
• Говорят, что механизм Mech реализует функцию социального выбора Soc , если для каждой комбинации индивидуальных предпочтений существует равновесие Нэша в Game(Mech) , в котором результатом является Soc(Prefs) . Два примера механизмов:
  • "Каждый человек называет число от 1 до 10. Предмет отдается тому, кто называет наименьшее число; если оба называют одно и то же число, то предмет отдается Алисе". Этот механизм НЕ реализует утилитарную функцию, поскольку для каждого человека, который хочет предмет, доминирующей стратегией является сказать "1" независимо от его/ее истинной ценности. Это означает, что в равновесии предмет всегда отдается Алисе, даже если Боб ценит его больше.
  • Аукцион с закрытыми ставками первой цены — это механизм, реализующий утилитарную функцию. Например, если , то любой профиль действий, в котором Боб делает ставку больше, чем Алиса, и обе ставки находятся в диапазоне, является равновесием Нэша, в котором товар достается Бобу. Кроме того, если оценки Алисы и Боба являются случайными величинами, взятыми независимо из одного и того же распределения, то существует байесовское равновесие Нэша , в котором товар достается участнику торгов с самой высокой стоимостью. ${\displaystyle v_{B}>v_{A}}$ ${\displaystyle (v_{A},v_{B})}$
• Прямой механизм — это механизм, в котором набор действий, доступных каждому игроку, представляет собой просто набор возможных предпочтений игрока.
• Прямой механизм Mech называется совместимым с Bayesian-Nash -Incentive (BNIC), если существует байесовское равновесие Nash Game (Mech), в котором все игроки раскрывают свои истинные предпочтения. Вот некоторые примеры прямых механизмов:
  • «Каждый игрок называет, насколько он ценит предмет. Предмет отдается тому, кто назвал самую высокую стоимость. В случае ничьей предмет отдается Алисе». Этот механизм не является BNIC, поскольку игрок, который хочет предмет, выигрывает, называя максимально возможную стоимость, независимо от его истинной стоимости.
  • Аукцион с закрытыми ставками первой цены также не является аукционом BNIC, поскольку победитель всегда выигрывает, предлагая самую низкую цену, которая немного превышает ставку проигравшего.
  • Однако если распределение оценок игроков известно, то существует вариант , который является BNIC и реализует утилитарную функцию.
  • Более того, известно, что аукцион второй цены — это BNIC (он даже IC в более сильном смысле — IC доминирующей стратегии). Кроме того, он реализует утилитарную функцию.

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

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

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

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

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

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

Поиск решений

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

Варианты

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

• Принцип раскрытия доминирующей стратегии гласит, что каждая функция социального выбора, которая может быть реализована в доминирующих стратегиях , может быть реализована с помощью механизма, совместимого с доминирующей стратегией и стимулом (DSIC) . Этот вариант был впервые представлен Алланом Гиббардом . ^[1]
• Принцип откровения Байеса-Нэша гласит, что каждая функция социального выбора, которая может быть реализована в равновесии Байеса-Нэша ( игра Байеса , т.е. игра неполной информации), может быть реализована механизмом совместимости стимулов Байеса-Нэша (BNIC) . Эта более широкая концепция решения была введена Дасгуптой, Хаммондом и Маскиным ; ^[3] Хольмстрёмом ; ^[5] и Майерсоном . ^[4]

Принцип раскрытия также работает для коррелированных равновесий : ^{[ требуется ссылка ]} для каждого произвольного координирующего устройства , также известного как коррелирующее, существует другое прямое устройство, для которого пространство состояний равно пространству действий каждого игрока. ^{[ жаргон ]} Тогда координация осуществляется путем прямого информирования каждого игрока о его действии. ^{[ требуется пояснение ]}

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

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

Ссылки

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