# Mechanism Design: Proving that the expected utility is differentiable

Given a direct mechanism, we define a buyer's expected utility $$u(\theta)$$ conditional on her type being $$\theta$$ by $$u(\theta)=\theta q(\theta)-t(\theta)$$, where $$q:[\underline{\theta},\bar{\theta}]\to[0,1]$$ and $$t:[\underline{\theta},\bar{\theta}]\to\mathbb{R}$$.

We also define that a direct mechanism is incentive-compatible if truth-telling is optimal for every $$\theta\in[\underline{\theta},\bar{\theta}]$$, i.e., $$u(\theta)\geq \theta q(\theta')-t(\theta'),\quad\forall\theta,\theta'\in[\underline{\theta},\bar{\theta}].$$

LEMMA: For an incentive-compatible direct mechanism, we want to show that for all $$\theta$$ that $$u$$ is differentiable, we have $$u'(\theta)=q(\theta)$$.

PROOF: Consider any $$\theta$$ for which $$u$$ is differentiable. Let $$\delta>0$$. Then by incentive compatibility, we have the following:

I don't understand how from incentive compatibility it follows the first and second inequality 2.6 and 2.8. How can we use the same $$\theta$$ in the proof while the definition clearly states $$u(\theta)\geq \theta q(\theta')-t(\theta'),\forall\theta,\theta'$$?

• @HerrK. "An Introduction to the Theory of Mechanism Design" by Tilman Börgers - page 12, lemma 2.2 – johnny09 Feb 27 at 5:51

By definition we have \begin{align*} u(\theta) & = \theta q(\theta)-t(\theta) \\ \\ u(\theta + \delta) & = (\theta + \delta) q(\theta + \delta)-t(\theta + \delta) \end{align*} By incentive compatibility (where $$\theta + \delta$$ is the true type, $$\theta$$ is the false type) we have $$u(\theta + \delta) \geq (\theta + \delta) q(\theta)-t(\theta)$$ Using these (I used square brackets for clearer notation, there is no mathematical function to them) \begin{align*} u(\theta + \delta) - u(\theta) & = \left[(\theta + \delta) q(\theta + \delta)-t(\theta + \delta)\right] - \left[\theta q(\theta)-t(\theta)\right] \\ \\ u(\theta + \delta) - u(\theta) & \geq \left[(\theta + \delta) q(\theta)-t(\theta)\right] - \left[\theta q(\theta)-t(\theta)\right] \end{align*} This also holds if you divide by $$\delta > 0$$.

Similar argument for 2.8., using true type $$\theta - \delta$$ instead of $$\theta + \delta$$.

Let $$u(x)=xq(x)-t(x)$$. Incentive compatibility dictates that $$xq(x)-t(x)\geq xq(z)-t(z)$$, when $$x$$ is the observed private value. Using a little algebraic manipulation, it can be shown that,

$$xq(x)-t(x)+zq(z)\geq xq(z)-t(z)+zq(z)$$, or

$$u(x)+zq(z)\geq u(z)+xq(z)$$, or

$$u(x)\geq u(z) +(x-z)q(z)$$. Let this be $$(1)$$.

Similarly, $$zq(z)-t(z)\geq zq(x)-t(x)$$, when $$z$$ is the observed private value. Thus, from here as well, we have $$u(z)\geq u(x) +(z-x)q(x)$$. Let this expression be $$(2)$$.

From $$(1)$$, we have $$\cfrac{u(x)-u(z)}{x-z} \geq q(z)$$. Similarly, from $$(2)$$, we have $$\cfrac{u(x)-u(z)}{x-z} \leq q(x)$$. Now, we have the expression, \begin{align*} q(z) \leq \cfrac{u(x)-u(z)}{x-z} \leq q(x) \\ -(3) \end{align*}

EDIT As correctly pointed out by TheoreticalEconomist, if $$x > z$$, expression $$(3)$$ tells us that $$q(x)$$ is monotone. Also, as $$u$$ is a convex function, it is absolutely continuous. This tells us that $$u$$ is differentiable almost everywhere. Thus, wherever $$u$$ is differentiable, we have $$u'(x) = q(x)$$.

• I’m less fond of this way of presenting the argument — it seems to implicitly assume that $q$ is continuous, since you want that $q(z+\delta) \to q(z)$ as $\delta \to 0$. – Theoretical Economist Feb 28 at 8:10
• @TheoreticalEconomist You're right, this differentiability criteria holds almost every. – superhulk Feb 28 at 10:44
• don’t you need $q$ to be continuous a.e. to say that? – Theoretical Economist Feb 28 at 11:12
• @TheoreticalEconomist $u'(x)=q(x)$ whenever $u$ is differentiable. Also, $u$ is absolutely continuous, so it is differentiable almost everywhere, except for a set of countable points at the most. The left and right derivatives, although, exist for all $x$. – superhulk Feb 28 at 12:45
• I know that. I don’t think you understand my point. From what you’ve written in your answer, one can only conclude that $u^\prime = q$ only if one assumes that $q$ is continuous a.e. Suppose $q$ where discontinuous a.e. The conclusion you assert at the end of your answer is no longer valid. Of course, this is ruled out by incentive compatibility (since $q$ must be monotone), but this is not at all clear in your answer. – Theoretical Economist Feb 28 at 12:54