Revelation principle

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs editing for compliance with Wikipedia's Manual of Style. Please help improve it if you can. (April 2016) (Learn how and when to remove this template message) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (April 2016) (Learn how and when to remove this template message) (Learn how and when to remove this template message)

The revelation principle is a fundamental principle in mechanism design. It states that if a social choice function can be implemented by an arbitrary mechanism (i.e. if that mechanism has an equilibrium outcome that corresponds to the outcome of the social choice function), then the same function can be implemented by an incentive-compatible-direct-mechanism (i.e. in which players truthfully report type) with the same equilibrium outcome (payoffs).^{[1]: 224–225}

In mechanism design, the revelation principle is of utmost importance in finding solutions. The researcher need only look at the set of equilibria characterized by incentive compatibility. That is, if the mechanism designer wants to implement some outcome or property, they can restrict their search to mechanisms in which agents are willing to reveal their private information to the mechanism designer that has that outcome or property. If no such direct and truthful mechanism exists, no mechanism can implement this outcome/property by contraposition. By narrowing the area needed to be searched, the problem of finding a mechanism becomes much easier.

The principle comes in two variants corresponding to the two flavors of incentive-compatibility:

• 지배 전략 계시-원칙은 지배 전략에서 구현될 수 있는 모든 사회 선택 기능은 지배 전략-인센트럴 호환(DSIC) 메커니즘에 의해 구현될 수 있다고 말한다(앨런 기바드 소개^[2]).
• 베이시안-나시 폭로 원칙은 베이시안-나시 평형(베이시안 게임, 즉 불완전한 정보의 게임)에서 구현될 수 있는 모든 사회 선택 기능은 베이시안-나시 인센티브 호환성(BNIC) 메커니즘에 의해 구현될 수 있다고 말한다. 이 보다 광범위한 솔루션 개념은 Dasgupta, Hammond and Maskin,^[3] Holmstrom,^[4] Myerson에 의해 도입되었다.^[5]

예

다음 예를 들어보자. 앨리스가 $v{\displaystyle {}_{}}$ ${\displaystyle A_{}}$ ${\$로, 밥이 ${\displaystyle v_{}}$ B ${\$로 값을 매기는 특정 항목이 있다$.$ 정부는 누가 어떤 조건으로 그 물건을 받을지 결정할 필요가 있다.

• 사회적 선택 기능은 일련의 개인 선호도를 사회적 결과에 매핑하는 기능이다. 예시함수는 "항목을 가장 중시하는 사람에게 주어라"는 공리함수다. 우리는 Soc의 사회적 선택 기능과 Soc(Prefs)의 선호도가 주어진 권장 결과를 나타낸다.
• 메커니즘은 일련의 개별적인 행동을 사회적 결과에 매핑하는 규칙이다. 메흐는 우리가 게임(Mech)으로 나타내는 게임을 유도한다.
• A mechanism Mech is said to implement a social-choice-function Soc if, for every combination of individual preferences, there is a Nash equilibrium in Game(Mech) in which the outcome is Soc(Prefs). Two example mechanisms are:
  • "각자는 1에서 10 사이의 숫자를 말한다. 그 물건은 가장 낮은 숫자를 말하는 사람에게 주어진다. 만약 둘 다 같은 번호를 말한다면, 그 물건은 앨리스에게 주어진다.' 이 메커니즘은 공리적인 기능을 구현하지 않는다. 왜냐하면 그 아이템을 원하는 모든 개인에게는 자신의 진가에 상관없이 "1"이라고 말하는 것이 지배적인 전략이기 때문이다. 이것은 평형상태에서 그 물건은 밥이 더 소중하게 생각하더라도 항상 앨리스에게 주어지는 것을 의미한다.
  • First-price sealed-bid auction is a mechanism which implements the utilitarian function. For example, if ${\displaystyle v_{B}>v_{A}}$, then any action profile in which Bob bids more than Alice and both bids are in the range ${\displaystyle (v_{A},v_{B})}$ is a Nash-equilibrium in which the item goes to Bob. Additionally, if the valuations of Alice and Bob are random variables drawn independently from the same distribution, then there is a Bayesian Nash equilibrium in which the item goes to the bidder with the highest value.
• A direct-mechanism is a mechanism in which the set of actions available to each player is just the set of possible preferences of the player.
• A direct-mechanism Mech is said to be Bayesian-Nash-Incentive-compatible (BNIC) if there is a Bayesian Nash equilibrium of Game(Mech) in which all players reveal their true preferences. Some example direct-mechanisms are:
  • "Each individual says how much he values the item. The item is given to the individual that said the highest value. In case of a tie, the item is given to Alice". This mechanism is NOT BNIC, since a player who wants the item is better-off by saying the highest possible value, regardless of his true value.
  • First-price sealed-bid auction is also NOT BNIC, since the winner is always better-off by bidding the lowest value that is slightly above the loser's bid.
  • However, if the distribution of the players' valuations is known, then there is a variant which is BNIC and implements the utilitarian function.
  • Moreover, it is known that Second price auction is BNIC (it is even IC in a stronger sense - dominant-strategy IC). Additionally, it implements the utilitarian function.

Proof

Suppose we have an arbitrary mechanism Mech that implements Soc.

We construct a direct mechanism Mech' that is truthful and implements Soc.

Mech' simply simulates the equilibrium strategies of the players in Game(Mech). I.e:

• Mech' asks the players to report their valuations.
• Based on the reported valuations, Mech' calculates, for each player, his equilibrium strategy in Mech.
• Mech' returns the outcome returned by Mech.

Reporting the true valuations in Mech' is like playing the equilibrium strategies in Mech. Hence, reporting the true valuations is a Nash equilibrium in Mech', as desired. Moreover, the equilibrium payoffs are the same, as desired.

In correlated equilibrium

The revelation principle says that for every arbitrary coordinating device a.k.a. correlating, there exists another direct device for which the state space equals the action space of each player. Then the coordination is done by directly informing each player of his action.

See also

• Mechanism design
• Incentive compatibility
• The Market for Lemons
• Nash equilibrium
• Game theory
• Constrained Pareto efficiency
• Myerson–Satterthwaite theorem

References