<p>Let <span class="math-container">$u(x)=xq(x)-t(x)$</span>. Incentive compatibility dictates that <span class="math-container">$xq(x)-t(x)\geq xq(z)-t(z)$</span>, when <span class="math-container">$x$</span> is the observed private value. Using a little algebraic manipulation, it can be shown that,</p>

<p><span class="math-container">$xq(x)-t(x)+zq(z)\geq xq(z)-t(z)+zq(z)$</span>, or</p>

<p><span class="math-container">$u(x)+zq(z)\geq u(z)+xq(z)$</span>, or</p>

<p><span class="math-container">$u(x)\geq u(z) +(x-z)q(z)$</span>. Let this be <span class="math-container">$(1)$</span>.</p>

<p>Similarly, <span class="math-container">$zq(z)-t(z)\geq zq(x)-t(x)$</span>, when <span class="math-container">$z$</span> is the observed private value. Thus, from here as well, we have <span class="math-container">$u(z)\geq u(x) +(z-x)q(x)$</span>. Let this expression be <span class="math-container">$(2)$</span>.</p>

<p>From <span class="math-container">$(1)$</span>, we have <span class="math-container">$\cfrac{u(x)-u(z)}{x-z} \geq q(z)$</span>. Similarly, from <span class="math-container">$(2)$</span>, we have <span class="math-container">$\cfrac{u(x)-u(z)}{x-z} \leq q(x)$</span>. Now, we have the expression, 
<span class="math-container">\begin{align*}
q(z) \leq \cfrac{u(x)-u(z)}{x-z} \leq q(x)  \\ -(3)
\end{align*}</span></p>

<p><strong>EDIT</strong>
As correctly pointed out by TheoreticalEconomist, if  <span class="math-container">$x &gt; z$</span>, expression <span class="math-container">$(3)$</span> tells us that <span class="math-container">$q(x)$</span> is monotone. Also, as <span class="math-container">$u$</span> is a convex function, it is absolutely continuous. This tells us that <span class="math-container">$u$</span> is differentiable almost everywhere. Thus, wherever <span class="math-container">$u$</span> is differentiable, we have <span class="math-container">$u'(x) = q(x)$</span>.</p>

CC BY-SA 4.0
2019-02-28T08:10:03.980Z
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
CC BY-SA 4.0
2019-02-28T10:44:49.583Z
@TheoreticalEconomist You're right, this differentiability criteria holds almost every.
superhulk
CC BY-SA 4.0
2019-02-28T11:12:09.033Z
don’t you need $q$ to be continuous a.e. to say that?
Theoretical Economist
CC BY-SA 4.0
2019-02-28T12:45:41.740Z
@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
CC BY-SA 4.0
2019-02-28T12:54:15.143Z
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
CC BY-SA 4.0
2019-02-28T13:56:11.950Z
@TheoreticalEconomist I've made the edits.
superhulk
CC BY-SA 4.0
2019-02-27T14:10:20.253Z
2019-02-28T13:55:27.767Z
2019-02-28T13:55:27.767Z
superhulk
<p>By definition we have
<span class="math-container">$$
\begin{align*}
u(\theta) &amp; = \theta q(\theta)-t(\theta) \\
\\
u(\theta + \delta) &amp; = (\theta + \delta) q(\theta + \delta)-t(\theta + \delta)
\end{align*}
$$</span>
By incentive compatibility (where <span class="math-container">$\theta + \delta$</span> is the true type, <span class="math-container">$\theta$</span> is the false type) we have
<span class="math-container">$$
u(\theta + \delta) \geq (\theta + \delta) q(\theta)-t(\theta)
$$</span>
Using these (I used square brackets for clearer notation, there is no mathematical function to them)
<span class="math-container">$$
\begin{align*}
u(\theta + \delta) - u(\theta) &amp; =
\left[(\theta + \delta) q(\theta + \delta)-t(\theta + \delta)\right] -
\left[\theta q(\theta)-t(\theta)\right]  \\
\\
u(\theta + \delta) - u(\theta) &amp; \geq
\left[(\theta + \delta) q(\theta)-t(\theta)\right] -
\left[\theta q(\theta)-t(\theta)\right]
\end{align*}
$$</span>
This also holds if you divide by <span class="math-container">$\delta &gt; 0$</span>.</p>

<p>Similar argument for 2.8., using true type <span class="math-container">$\theta - \delta$</span> instead of <span class="math-container">$\theta + \delta$</span>.</p>

CC BY-SA 4.0
2019-02-27T07:25:50.787Z
2019-02-27T07:54:27.127Z
2019-02-27T07:54:27.127Z
Giskard
<p>Given a direct mechanism, we define a buyer's expected utility <span class="math-container">$u(\theta)$</span> conditional on her type being <span class="math-container">$\theta$</span> by <span class="math-container">$u(\theta)=\theta q(\theta)-t(\theta)$</span>, where <span class="math-container">$q:[\underline{\theta},\bar{\theta}]\to[0,1]$</span> and <span class="math-container">$t:[\underline{\theta},\bar{\theta}]\to\mathbb{R}$</span>.</p>

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

<p><strong>LEMMA</strong>: For an incentive-compatible direct mechanism, we want to show that for all <span class="math-container">$\theta$</span> that <span class="math-container">$u$</span> is differentiable, we have <span class="math-container">$u'(\theta)=q(\theta)$</span>.</p>

<p><strong>PROOF</strong>: Consider any <span class="math-container">$\theta$</span> for which <span class="math-container">$u$</span> is differentiable. Let <span class="math-container">$\delta&gt;0$</span>. Then by incentive compatibility, we have the following:</p>

<p><a href="https://i.sstatic.net/dwdPG.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/dwdPG.png" alt="enter image description here"></a></p>

<p>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 <span class="math-container">$\theta$</span> in the proof while the definition clearly states <span class="math-container">$u(\theta)\geq \theta q(\theta')-t(\theta'),\forall\theta,\theta'$</span>?</p>

CC BY-SA 4.0
2019-02-27T05:51:39.453Z
@HerrK. "An Introduction to the Theory of Mechanism Design" by Tilman Börgers - page 12, lemma 2.2
johnny09
<mathematical-economics><game-theory><mechanism-design>
Mechanism Design: Proving that the expected utility is differentiable
johnny09
# Mechanism Design: Proving that the expected utility is differentiable

(Asked by: username_0 on 2019-02-27)

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:

[![enter image description here](https://i.sstatic.net/dwdPG.png)](https://i.sstatic.net/dwdPG.png)

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'$?

**Tags:** mathematical-economics, game-theory, mechanism-design

> **Comments:**
> **username_0**: @HerrK. "An Introduction to the Theory of Mechanism Design" by Tilman Börgers - page 12, lemma 2.2  

---

## 2 answers

### Answer by username_3 on 2019-02-27. Score: 5 | Accepted answer

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


---

### Answer by username_1 on 2019-02-27. Score: 2

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)$.

> **Comments:**
> **username_2**: 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$.  
> **username_1**: @TheoreticalEconomist You're right, this differentiability criteria holds almost every.  
> **username_2**: don’t you need $q$ to be continuous a.e. to say that?  
> **username_1**: @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$.  
> **username_2**: 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.  
> **username_1**: @TheoreticalEconomist I've made the edits.  

---

