Typically, we study games under given rules, but we can also examine the optimal rules of the game, i.e., mechanism design. For example,

• optimal design of auction, e.g., first-price or second-price auction;
• negotiation versus auction;
• voting rules;
• allocation rules.

Example of Pricing a Single Indivisible Good [1]

<aside> Sequence of events

1. The seller announces his mechanism to sell a single indivisible good.
   • the seller has unlimited commitment power;
   • the mechanism means the game tree and the strategy committed by the seller.
2. The buyer learns her type $\theta$, and her utility function is $\theta-t$, where $t$ is a monetary transfer to the seller.
   • $\theta$ is her private information;
   • the seller has a prior belief that $\theta$ is drawn from a cdf $F$ with an interval $[\underline{\theta}, \bar{\theta}]$, the density of $F$ is $f$.
3. The buyer is asked to choose a strategy allowed in the mechanism, and then the outcome is implemented according to the rule of the mechanism. </aside>

At first sight, this looks like a very hard problem since the set of all possible mechanisms is immense.

<aside> Direct Mechanism

A direct mechanism (a.k.a. direct-revelation mechanism) is characterized by two functions:

$$ q: [\underline{\theta}, \bar{\theta}] \rightarrow [0,1], t:[\underline{\theta}, \bar{\theta}] \rightarrow \mathbb{R}. $$

• The buyer is asked to reveal her type $\theta$ directly.
• After that, the buyer pays the seller $t(\theta)$, and the good is transferred to the buyer with prob. $q(\theta)$. </aside>

<aside> Individual Rational Mechanism

A direct mechanism is “individually rational” if the buyer is voluntarily willing to participate, i.e.,

$$ \theta q(\theta) - t(\theta) \geq0 \quad \forall \theta \in [\underline{\theta}, \bar{\theta}]. $$

</aside>

<aside> Incentive Compatible Mechanism

A direct mechanism is “incentive compatible” if truth telling is optimal for every type, i.e.,

$$ \theta q(\theta) - t(\theta) \geq \theta q(\theta') - t(\theta') \quad \forall \theta, \theta' \in [\underline{\theta}, \bar{\theta}]. $$

</aside>

<aside> Revelation Principle

For every mechanism $\Gamma$ and every optimal buyer strategy $\sigma^*$ in $\Gamma$ there is a direct mechanism $(q,t)$ such that

• $(q,t)$ is individually rational and incentive compatible;
• For every $\theta \in [\underline{\theta}, \bar{\theta}]$, the probability $q(\theta)$ and the payment $t(\theta)$ equal the prob. of purchase and the expected payment that result under $\Gamma$ if the buyer plays her optimal strategy $\sigma^*$. </aside>

<aside> Proof of Revelation Principle

For every mechanism $\Gamma$,

• Let $\sigma^{\Gamma} (\theta)$ denote the optimal disclosure strategy of type $\theta$ under mechanism $\Gamma$.
• Consider a direct mechanism,

$$ q(\theta)=q^{\Gamma} (\sigma^{\Gamma}(\theta)), t(\theta) = t^{\Gamma} (\sigma^{\Gamma}(\theta)), $$

• it is easy to see that truth-telling is optimal for all the buyer types;
• Moreover, the seller’s revenue is the same under this direct mechanism. </aside>

Owing to revelation principle, we can restrict attention to incentive-compatible and individually-rational direct mechanisms. The revelation principles also tells that, to solve for the revenue-maximizing mechanism, it suffices to solve the following problem:

$$ \begin{equation} \begin{aligned} \max_{(q,t):[\underline{\theta}, \bar{\theta}] \rightarrow [0,1]\times \mathbb{R}} & \int_{\underline{\theta}}^{\bar{\theta}} t(\theta) f(\theta) d\theta,\\
\text{s.t.} \quad& \theta q(\theta) - t(\theta) \geq \theta q(\theta') - t(\theta') \quad \forall \theta, \theta' \in [\underline{\theta}, \bar{\theta}] \quad \text{(incentive-compatibility)}\\ & \theta q(\theta) - t(\theta) \geq0 \forall \theta \in [\underline{\theta}, \bar{\theta}] \quad \text{(individual-rationality)}\\ \end{aligned}\nonumber\end{equation} $$

Next, we will focus on this problem, and the following lemmas will assist us in identifying a suitable mechanism.

<aside>

Lemma (Property of IC)

If a direct mechanism is incentive compatible,

1. then $q$ is increasing in $\theta$;
2. then $u$ is increasing and convex, and hence differentiable except in at most countable many points. For all $\theta$ for which it is differentiable, $u’(\theta)=q(\theta)$;
3. for all $\theta\in [\underline{\theta}, \bar{\theta}]$,

$$ u(\theta) = u(\underline{\theta}) + \int_{\underline{\theta}}^{\theta} q(x)dx. $$

This property is also called payoff equivalence.

1. for all $\theta\in [\underline{\theta}, \bar{\theta}]$,

$$ t(\theta) = \theta q(\theta) - u(\theta) = t(\underline{\theta}) + (\theta q(\theta) - \underline{\theta} q (\underline{\theta})) - \int_{\underline{\theta}}^{\theta} q(x) dx. $$

This property is also called revenue equivalence.

</aside>

<aside>

Proof of Lemma (Property of IC)

1. Consider two types $\theta > \theta’$, IC implies that

$$ \theta q(\theta) - t(\theta) \geq \theta q(\theta') - t(\theta'),\\ \theta' q(\theta') - t(\theta') \geq \theta' q(\theta) - t(\theta). $$

Combine them, we have $q(\theta)\geq q(\theta’)$.

1. The buyer with type $\theta$ chooses disclosure $\theta’$ to maximize her utility

$$ u(\theta) = \max_{\theta' \in [\underline{\theta}, \bar{\theta}]} \theta q(\theta') - t(\theta'). $$

It is easy to see that $u$ is increasingly convex in $\theta$. Since $u$ is the maximum of increasing and convex function. Using envelope theorem, $u’(\theta) = q(\theta^) = q(\theta)$ since the optimal strategy is truth-telling, i.e., $\theta^=\theta$.

1. $u$ is convex hence absolutely continuous. And $u$ is the integral of its derivative.
2. A direct result of 3. </aside>

These properties help us derive the

<aside>

Proposition (Necessary and Sufficient Condition of IC)

A direct mechanism $(q,t)$ is incentive compatible iff

1. $q$ is increasing;
2. $t(\theta) = t(\underline{\theta}) + (\theta q(\theta) - \underline{\theta} q (\underline{\theta})) - \int_{\underline{\theta}}^{\theta} q(x) dx$ for all $\theta\in [\underline{\theta}, \bar{\theta}]$. </aside>