Mechanism design is the game-theoretic setting where a designer chooses the game played in order to ensure some desired behavior or some desirable outcome occurs. We cover the VCG mechanism and Revelation Principle.
We now give the notation of a mechanism design problem.
- There are participants who have types and who influence an outcome in the set .
- We let the outcome set be . Here consists of a decision and participants payments . Payments are positive or negative, and is the payment of the mechanism designer.
- A mechanism is a set of strategies and a function .
- As a function of their types, players choose a strategy , .
- The function that maps types to outcomes is called the performance function.
- The value of a decision to player of type is . The payoff of player of type for outcome is
Once the mechanism and players types are fixed, defines an -person game, an -person game chosen by the mechanism designer. Like in Chapter [nGame]we can study the equilibria of this game. For instance, if types are random we can study Bayes-Nash equilibria.
As functions and depend only on rather than all , players have private values: they do not explicit use other participants types when choosing a strategy. In addition when choosing a mechanism, the mechanism designer will not know the player’s types though, perhaps, he will know their distribution.
The VCG Mechanism
Shortly, we will define the Vickery-Clark-Groves Mechanism, but first we describe further mechanism design concepts.1
- A decision is efficient if it gives the participants the highest aggregate value. More formally, given participants types , is such
- A direct mechanism is a mechanism where the set strategies is the set of types . So each participant can reveal their type to the mechanism design: . This is called truthful reporting. However, participants could gain by lying about their type.
- A direct mechanism is called incentive compatible if truthful reporting is always equilibrium. This notion depends on which equilibrium concept is considered…
- We consider a dominant strategies equilibrium. For any game, i.e. fixed mechanism and fixed types , a strategy is dominant for player if it always has the best payoff A dominant strategies equilibrium is a strategy profile where, for all types , each is a dominant strategy.
Note a dominant strategy equilibrium is a much stronger notion of equilibrium in comparison to a Nash equilibrium. The strategy profile is globally the best choice in comparison to the locally best choice. As the above definitions suggest, we are interested in an incentive compatible mechanism under a dominant strategy equilibrium. We now describe the Vickery-Clark-Groves mechanism (VCG).
- A Vickery-Clark-Groves mechanism is a direct mechanism whose decision maximizes the aggregate value declared by participants and whose payments are the sum of two functions:
and a function which does not depend on .
- is the difference of two quantities: the most efficient outcome for participants if ’s value is ignored, and the value for participants when is included.So, is the value lost by participants when chooses to participate.
- A VCG mechanism doesn’t know participants types but is aware participants’ value functions .
Consider a payoff from a VCG mechanism, a participant cannot influence the payment nor can he influence the first term in the payment of . What the player can attempt to affect is it the second term and his value . But for this to maximize his payoff, he must want the aggregate payoff of participants to be maximized and he can only do this by truthful reporting. This summarizes the result which we prove below.
Thrm. All VCG mechanisms are incentive compatible under a dominant strategy equilibrium.
Proof. For any , the payoff of a participant of type who declares a strategy is
Thus payoff for declaring your type is higher than declaring another type . The inequality above, uses the fact that is not optimal for values with types .
Ex. First recall some notation: we consider a mechanism with participants. For , each participant’s type is in the interval and, as a function of their type, their strategies are in the interval . An outcome consists of a decision vector – the th unit vector corresponds to the th outcome occuring – and gives the payment of each participant (and the designer). For a participant of type , we let the vector give the participant’s value for each of the decisions. We suppose each component of is continuously differentiable. Participant ’s payoff for outcome is
a) What is a direct mechanism and what is a VCG mechanism?
b) A VCG mechanism is a direct mechanism that is both efficient and incentive compatible under a dominant strategies equilibrium. What do we mean by efficient and incentive compatible under a dominate strategies equilibrium?
c) For , let Stating any theorems that you assume, show that and thus show that d) Use part c) to show that a direct mechanism that is efficient and incentive compatible under a dominant strategies equilibrium is a VCG-mechanism.
(Hint: compare the prices of a VCG mechanism with the prices of an efficient and incentive compatible mechanism.)
The Revelation Principle
We now generalize our notion equilibrium and generalize incentive compatibility for that equilibrium.
- We, now, assume type of participants are generated from a known probability distribution . Note we do not assume types are independent.
- Given a mechanism , as before, a Bayes-Nash equilibrium is a function such that for each and
- A direct mechanism is incentive compatible for Bayes-Nash equilibria if is a Bayes-Nash Equilibrium.
The distribution is known. So, we can augment the mechanism with the Bayes-Nash equilibrium . We then consider the notion of Bayes-Nash equilibrium for the augmented mechanism . An incentive compatible performance for is, by definition, a Bayes-Nash equilibrium. However, in addition, the augmented mechanism must incentive compatible:
Thrm. [The Revelation Principle] The augmented mechanism is incentive compatible for Bayes-Nash equilibria.
- Here, we state the Revelation Principle for Bayes-Nash equilibria. We could consider other equilibria. We stick to Bayes-Nash because of its applications to auctions.
- Although achieves performance , it may not be that the mechanism achieves a performance that equals the identity function. However checking the definitions above, we see that it is indeed an immediate observation.
- We can often use the Revelation Principle to simplify the analysis of a mechanism by considering its corresponding direct mechanism .
Proof. Because holds, . Here we just replaced with . But this is just the statement that is a Bayes-Nash equilibrium for . So is incentive compatible.
- Just to add to the splurge of jargon: the triple is sometimes called the environment; if payments always sum to zero, the payments are said to be budget balanced; payoffs are sometimes called ; the payoff function of the form is called quasi-linear; the mechanism that consists of types and the performance function is called the augmented mechanism; a mechanism that is incentive compatible under dominant strategies equilibrium is sometimes called strategy proof; sometimes we say weakly dominates instead of dominates because we do not use strict inequality; the VCG payment function (next page) is sometimes called the VCG pivot. Bluh!↩