Revelation principle

Last updated

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

Contents

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 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:

Example

Consider the following example. There is a certain item that Alice values as and Bob values as . The government needs to decide who will receive that item and in what terms.

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:

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

Related Research Articles

Mechanism design field in game theory

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics to networked-systems.

In game theory, an asymmetric game where played have private information is said to be strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. you fare best or at least not worse by being truthful, regardless of what the others do.

In economics and game theory, complete information is an economic situation or game in which knowledge about other market participants or players is available to all participants. The utility functions, payoffs, strategies and "types" of players are thus common knowledge. Complete information is the concept that each player in the game is aware of the sequence, strategies, and payoffs throughout gameplay. Given this information, the players have the ability to plan accordingly based on the information to maximize their own strategies and utility at the end of the game.

In common valueauctions the value of the item for sale is identical amongst bidders, but bidders have different information about the item's value. This stands in contrast to a private value auction where each bidder's private valuation of the item is different and independent of peers' valuations.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

A double auction is a process of buying and selling goods when potential buyers submit their bids and potential sellers simultaneously submit their ask prices to an auctioneer, and then an auctioneer chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included.

A mechanism is called incentive-compatible (IC) if every participant can achieve the best outcome to themselves just by acting according to their true preferences.

A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids, so that no bidder knows the bid of any other participant. The highest bidder pays the price they submitted.

Implementation theory is an area of research in game theory concerned with whether a class of mechanisms can be designed whose equilibrium outcomes implement a given set of normative goals or welfare criteria.

In game theory, the traveler's dilemma is a non-zero-sum game in which each player proposes a payoff. The lower of the two proposals wins; the lowball player receives the lowball payoff plus a small bonus, and the highball player receives the same lowball payoff, minus a small penalty. Surprisingly, the Nash equilibrium is for both players to aggressively lowball. The traveler's dilemma is notable in that naive play appears to outperform the Nash equilibrium; this apparent paradox also appears in the centipede game and the finitely-iterated prisoner's dilemma.

Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes also has the same expected revenue.

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. Each bidder places a bid. The highest bidder gets the first slot, the second-highest, the second slot and so on, but the highest bidder pays the price bid by the second-highest bidder, the second-highest pays the price bid by the third-highest, and so on. First conceived as a natural extension of the Vickrey auction, it conserves some of the desirable properties of the Vickrey auction. It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction basis. The first analyses of GSP are in the economics literature by Edelman, Ostrovsky, and Schwarz and by Varian. It is employed by Google's AdWords technology.

Arunava Sen Indian Economist

Arunava Sen is a Professor of Economics at the Indian Statistical Institute. He works on Game Theory, Social Choice Theory, Mechanism Design, Voting and Auctions.

In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.

In mechanism design, implementability is a property of a social choice function. It means that there is an incentive-compatible mechanism that attains ("implements") this function. There are several degrees of implementability, corresponding to the different degrees of incentive-compatibility, e.g:

In mechanism design, monotonicity is a property of a social choice function. It is a necessary condition for being able to implement the function using a strategyproof mechanism. Its verbal description is:

If changing one agent's type changes the outcome under the social choice function, then the resulting difference in utilities of the new and original outcomes evaluated at the new type of this agent must be at least as much as this difference in utilities evaluated at the original type of this agent.

A sequential auction is an auction in which several items are sold, one after the other, to the same group of potential buyers. In a sequential first-price auction (SAFP), each individual item is sold using a first price auction, while in a sequential second-price auction (SASP), each individual item is sold using a second price auction.

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

References

  1. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN   0-521-87282-0.
  2. Gibbard, A. 1973. Manipulation of voting schemes: a general result. Econometrica 41, 587–601.
  3. Dasgupta, P., Hammond, P. and Maskin, E. 1979. The implementation of social choice rules: some results on incentive compatibility. Review of Economic Studies 46, 185–216.
  4. Holmstrom, B. 1977. On incentives and control in organizations. Ph.D. thesis, Stanford University.
  5. Myerson, R. 1979. Incentive-compatibility and the bargaining problem. Econometrica 47, 61–73.