Revelation principle

The revelation principle shows that, while Gibbard's theorem proves it is impossible to design a system that will always be fully invulnerable to strategy (if we do not know how players will behave), it is possible to design a system that encourages honesty given a solution concept (if the corresponding equilibrium is unique).

The idea behind the revelation principle is that, if we know which strategy the players in a game will use, we can simply ask all the players to submit their true payoffs or utility functions; then, we take those preferences and calculate each voter's optimal strategy before executing it for them. This procedure means that an honest report of preferences is now the best-possible strategy, because it guarantees the mechanism will play the optimal strategy for the player.

Examples

Consider the following example. There is a certain item that Alice values as ${\displaystyle v_A}$ and Bob values as ${\displaystyle v_B}$. The government needs to decide who will receive that item and in what terms.

• A social-choice-function is a function that maps a set of individual preferences to an optimal social outcome. An example function is the utilitarian rule, which says "give the item to a person that values it the most". We denote a social choice function by Soc and its recommended outcome given a set of preferences by Soc(Prefs).
• A mechanism is a rule that maps a set of individual actions to a social outcome. A mechanism Mech induces a game which we denote by Game(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:
  • "Each individual says a number between 1 and 10. The item is given to the individual who says the lowest number; if both say the same number, then the item is given to Alice". This mechanism does NOT implement the utilitarian function, since for every individual who wants the item, it is a dominant strategy to say "1" regardless of his/her true value. This means that in equilibrium the item is always given to Alice, even if Bob values it more.
  • 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.