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 $\label{VCG:quasi} u_i((x,p),t_i)= v_i(x,t_i)-p_i$

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.¹

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 $x\in \argmax_{\tilde{x}\in{\mathcal X}} \sum_{i=1}^N v_i(x,t_i).$
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 $u_i((x(\bm{s}),p(\bm{s})),t_i)\geq u_i((x(\tilde{s}_i,s_{-i}),p(\tilde{s}_i,s_{-i})),t_i),\qquad \forall \tilde{s}_i\in{\mathcal S}_i, \quad \forall s_{-i}\in\prod_{j:j\neq i}{\mathcal S}_j.$ 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 $x(\bm{s})\in \argmax_{x\in{\mathcal X}} \sum_{i=1}^N v_i(x,s_i),$ and whose payments are the sum of two functions: $\label{VCG:p} p_i(\bm{s})= \max_{x\in{\mathcal X}}\bigg\{ \sum_{j: j\neq i} v_j(x,s_j) \bigg\} - \sum_{j: j\neq i} v_j(x(\bm{s}),s_j)$

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 $\begin{aligned} & u_i((x(\bm{s}),p(\bm{s})),t_i)\\ =& v_i(x(\bm{s}),t_i)-p_i(\bm{s})-h_i(s_{-i})\\ =&v_i(x(s_i,s_{-i})),t_i)+\sum_{j:j\neq i} v_j(x(s_i,s_{-i}),s_j)-\max_{x\in{\mathcal X}}\bigg\{ \sum_{j: j\neq i} v_j(x,s_j) \bigg\}-h_i(s_{-i})\\ \leq & \max_{x\in{\mathcal X}}\bigg\{v_i(x,t_i)+\sum_{j:j\neq i} v_j(x,s_j)\bigg\}-\max_{x\in{\mathcal X}}\bigg\{ \sum_{j: j\neq i} v_j(x,s_j) \bigg\}-h_i(s_{-i})\\ =&v_i(x(t_i,s_{-i}), t_i)+\sum_{j:j\neq i} v_j(x(t_i,s_{-i}),s_j)-\max_{x\in{\mathcal X}}\bigg\{ \sum_{j: j\neq i} v_j(x,s_j) \bigg\}-h_i(s_{-i}) \\ =&u_i((x(t_i,s_{-i}),p(t_i,s_{-i})),t_i) \end{aligned}$

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 $k$ th unit vector $e_k\in{\mathbb R}^K$ corresponds to the $k$ th 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

$u_i((x,p),t_i)=x\cdot\bm{v}^i(t_i) - p_i.$

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 $U_i(\tilde{t}_i,t_{-i})=\max_{\tilde{\sigma}\in [0,1]} u_i(\omega(\tilde{\sigma},\sigma_{-i}(t_{-i})),\tilde{t}_i)\quad\text{and}\quad \sigma(\tilde{t}_i)\in\argmax_{\tilde{\sigma}\in [0,1]} u_i(\omega(\tilde{\sigma},\sigma_{-i}(t_{-i})),\tilde{t}_i).$ Stating any theorems that you assume, show that $U_i(\tilde{t}_i,t_{-i})=U_i(0,t_{-i}) + \int_0^{\tilde{t}_i} x(\sigma_i(s),\sigma_{-i}(t_{-i}))\cdot \frac{d \bm{v}^i}{d s}(s) ds,$ and thus show that $p_i(\sigma_i(\tilde{t}_i),\sigma_{-i}(t_{-i}))=-U_i(0,t_{-i}) + x(\sigma_i(\tilde{t}_i),\sigma_{-i}(t_{-i}))\cdot {\bm{v}^i}(\tilde{t}_i)-\int_0^{\tilde{t}_i} x(\sigma_i(s),\sigma_{-i}(t_{-i}))\cdot \frac{d \bm{v}^i}{d s}(s) ds.$ 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$ $\label{VCG:Bayes-Nash} {\mathbb E}[ u_i(\omega(\sigma(\bm{t})),t_i)|t_i]\geq {\mathbb E}[ u_i(\omega(\tilde{\sigma}_i,\sigma_{-i}(\bm{t}_{-i})),t_i)|t_i],\qquad \forall \tilde{\sigma}_i\in {\mathcal S}_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$

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!↩