Mechanism design

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 N participants who have types (t_1,...,t_N)\in\mathcal{T}=\prod_{i=1}^N \mathcal{T}_i and who influence an outcome in the set \mathcal{O}.
  • We let the outcome set be \mathcal{O}={\mathcal X}\times{\mathbb R}^{N+1}. Here (x,p)\in\mathcal{O} consists of a decision x\in{\mathcal X} and participants payments p=(p_0,p_1,...,p_N). Payments are positive or negative, and p_0 is the payment of the mechanism designer.
  • A mechanism ({\mathcal S},\omega) is a set of strategies {\mathcal S}=\prod_{n=1}^N {\mathcal S}_n and a function \omega=(x,p):{\mathcal S}\rightarrow \mathcal{O}.
  • As a function of their types, players choose a strategy \sigma:\mathcal{T} \rightarrow {\mathcal S}, \sigma(\mathbf{t})=(\sigma_i({t}_i):i=1,...,N).
  • The function that maps types to outcomes \rho=\omega\circ\sigma : \mathcal{T} \rightarrow \mathcal{O} is called the performance function.
  • The value of a decision x to player i of type t_i is v_i(x,t_i)\in{\mathbb R}. The payoff of player i of type t_i\in\mathcal{T}_i for outcome (x,p)\in\mathcal{O} is

Once the mechanism ({\mathcal S},\omega) and players types \mathbf{t} are fixed, u^i(\omega(\cdot)|\mathbf{t}):{\mathcal S}\rightarrow {\mathbb R} defines an N-person game, an N-person game chosen by the mechanism designer. Like in Chapter [nGame]we can study the equilibria of this game. For instance, if types \mathbf{t} are random we can study Bayes-Nash equilibria.

As functions u_i(x,t_i) and \sigma_i(t_i) depend only on t_i rather than all \mathbf{t}=(t_1,...,t_N), 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 x\in{\mathcal X} is efficient if it gives the participants the highest aggregate value. More formally, given participants types \mathbf{t}\in\mathcal{T}, x is such 
  • A direct mechanism is a mechanism where the set strategies is the set of types {\mathcal S}=\mathcal{T}. So each participant can reveal their type to the mechanism design: \sigma_i(t)=t. This is called truthful reporting. However, participants could gain by lying about their type.
  • A direct mechanism (\mathcal{T},\sigma) 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 (S,\omega) and fixed types \mathbf{t}, a strategy s_i\in{\mathcal S}_i is dominant for player i if it always has the best payoff A dominant strategies equilibrium is a strategy profile s=(s_1,...,s_N) where, for all types \mathbf{t}\in\mathcal{T}, each s_i 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 (\mathcal{T},(x(\cdot),p(\cdot)+h(\cdot))) whose decision maximizes the aggregate value declared by participants and whose payments are the sum of two functions:

and a function h_i(s_{-i}) which does not depend on s_i.

  • p_i(s) is the difference of two quantities: the most efficient outcome for participants j\neq i if i’s value is ignored, and the value for participants j\neq i when i is included.So, p_i is the value lost by participants j\neq i when chooses to i participate.
  • A VCG mechanism doesn’t know participants types but is aware participants’ value functions v_i(x,\cdot).

Consider a payoff from a VCG mechanism, a participant cannot influence the payment h(s_{-i}) nor can he influence the first term in the payment of p_i . What the player can attempt to affect is it the second term and his value v_i(x(\mathbf{s}),s_i). 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 s_{-i}, the payoff of a participant i of type t_i who declares a strategy s_i is

Thus payoff for declaring your type t_i is higher than declaring another type s_i. The inequality above, uses the fact that x(\mathbf{s}) is not optimal for values with types (t_i,s_{-i}). \square

Ex. First recall some notation: we consider a mechanism with N participants. For i=1,...N, each participant’s type t_i is in the interval [0,1] and, as a function of their type, their strategies \sigma_i(t_i) are in the interval [0,1]. An outcome \omega=(x,p) consists of a decision vector x\in \{e_k:k=1,...,K\} – the kth unit vector e_k\in{\mathbb R}^K corresponds to the kth outcome occuring – and p=(p_0,p_1,...,p_N) gives the payment of each participant (and the designer). For a participant i of type t_i, we let the vector \mathbf{v}^i(t_i)=(v^i_k(t_i):k=1,...,K) give the participant’s value for each of the K decisions. We suppose each component of \mathbf{v}^i(t_i) is continuously differentiable. Participant i’s payoff for outcome (x,p) 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 \tilde{t}_i\in[0,1], 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 F(\mathbf{t}). Note we do not assume types are independent.
  • Given a mechanism ({\mathcal S},\omega), as before, a Bayes-Nash equilibrium is a function \sigma(s)=(\sigma_i(s_i):i=1,...,N) such that for each i and t_i\in\mathcal{T}_i
  • A direct mechanism (\mathcal{T},\rho) is incentive compatible for Bayes-Nash equilibria if \sigma(\mathbf{t})=\mathbf{t} is a Bayes-Nash Equilibrium.

The distribution F is known. So, we can augment the mechanism ({\mathcal S},\omega) with the Bayes-Nash equilibrium \sigma. We then consider the notion of Bayes-Nash equilibrium for the augmented mechanism (\mathcal{T},\rho)=(\mathcal{T},\omega\circ\sigma). An incentive compatible performance for (\mathcal{T},\rho) is, by definition, a Bayes-Nash equilibrium. However, in addition, the augmented mechanism must incentive compatible:

Thrm. [The Revelation Principle] The augmented mechanism (\mathcal{T},\rho)=(\mathcal{T},\omega\circ\sigma) 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 ({\mathcal S},\omega) achieves performance \rho, it may not be that the mechanism (\mathcal{T},\rho) 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 ({\mathcal S},\omega) by considering its corresponding direct mechanism (\mathcal{T},\rho).

Proof. Because holds, {\mathbb E}[ u_i(\omega(\sigma(\mathbf{t})),t_i)|t_i]\geq {\mathbb E}[ u_i(\omega(\sigma_i(\tilde{t}_i),\sigma_{-i}(\mathbf{t}_{-i})),t_i)|t_i],\; \forall \tilde{t}_i\in \mathcal{T}_i. Here we just replaced \tilde{\sigma}_i with {\sigma}_i(\tilde{t}_i). But this is just the statement that \mathbf{t} is a Bayes-Nash equilibrium for (\mathcal{T},\rho). So (\mathcal{T},\rho) is incentive compatible. \square

  1. Just to add to the splurge of jargon: the triple (N,\mathcal{O},\mathcal{T}) is sometimes called the environment; if payments (p_0,...,p_N) always sum to zero, the payments are said to be budget balanced; payoffs are sometimes called \emph{utilities}; the payoff function of the form is called quasi-linear; the mechanism that consists of types and the performance function (\mathcal{T},\rho)=(\mathcal{T},\omega\circ\sigma) 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 p (next page) is sometimes called the VCG pivot. Bluh!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s