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

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

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

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

Примеры

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

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

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

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

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

Mech' просто моделирует равновесные стратегии игроков в Game( Mech ). т.е.

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

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

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

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

Варианты

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

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

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

См. также

Ссылки

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

[:0-1] Перейти обратно: ^а ^б Гиббард, А. 1973. Манипулирование схемами голосования: общий результат. Эконометрика 41, 587–601.

[AGT-2] Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .

[:1-3] Перейти обратно: ^а ^б Дасгупта П., Хаммонд П. и Маскин Э. 1979. Реализация правил социального выбора: некоторые результаты по совместимости стимулов. Обзор экономических исследований 46, 185–216.

[:2-4] Перейти обратно: ^а ^б Майерсон, Р. 1979. Совместимость стимулов и проблема переговоров. Эконометрика 47, 61–73.

[5] Хольмстрем, Б. 1977. О стимулах и контроле в организациях. доктор философии диссертация, Стэнфордский университет.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

v т и Темы теории игр
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Search optimizations	Alpha–beta pruning Aspiration window Principal variation search max^n algorithm Paranoid algorithm Lazy SMP
Miscellaneous	Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons