<p>I think I've gotten part of the answer. The above statement actually says that for any <em>truthful</em> mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form. </p>

CC BY-SA 3.0
2016-07-21T06:27:37.190Z
2016-07-21T06:27:37.190Z
xyguo
<p>I am learning algorithmic game theory with the <a href="http://theory.stanford.edu/~tim/f13/f13.html" rel="nofollow">lecture notes posted by Tim Roughgarden</a>. In <a href="http://theory.stanford.edu/~tim/f13/l/l5.pdf" rel="nofollow">lecture 5</a> it is proved that the problem of revenue (or profit) maximization in single-parameter environment is equivalent to maximizing something called "virtual welfare". I find it hard to understand the logic of the proof.</p>

<p>The very first step of the proof assumes that the payment rule is exactly in the form given by Myerson's lemma:
$$p_i(b_i,\mathbf{b}_{-i})=\int_0^{b_i}z\cdot x'_i(z,\mathbf{b}_i)\mathrm{dz}$$
where $x'_i(z,\mathbf{b}_i)$ is the derivative of the allocation rule $x'_i(z,\mathbf{b}_i)$. Then substitute the formula of payment into the profit object
$$\mathbb{E}\left[\sum_{i=1}^n\mathbf{p}(\mathbf{v})\right]$$
with some calculus the "virtual-welfare" magically shows up.</p>

<p>Then the author claims that maximizing the virtual welfare is equivalent to maximizing revenue, and if the corresponding allocation rule is monotone then we get a optimal DSIC mechanism. I have two questions about this:</p>

<ol>
<li><p>The result relies on the assumption that the payment rule is given in the previous form. Why does it must be in that form? The proof feels like some circular reasoning. Is this because that we are restricted on searching only for DSIC mechanism?</p></li>
<li><p>Furthermore, sometimes there exists no monotone allocation rule to optimize the deduced <em>virtual welfare</em>, but does this also mean that there exists no monotone rule to optimize the original <em>profit</em>?</p></li>
</ol>

<gt.game-theory><combinatorial-game-theory><mechanism-design>
The logic in derivation of virtual welfare
xyguo
# The logic in derivation of virtual welfare

(Asked by: username_0 on 2016-07-19)

I am learning algorithmic game theory with the [lecture notes posted by Tim Roughgarden](http://theory.stanford.edu/~tim/f13/f13.html). In [lecture 5](http://theory.stanford.edu/~tim/f13/l/l5.pdf) it is proved that the problem of revenue (or profit) maximization in single-parameter environment is equivalent to maximizing something called "virtual welfare". I find it hard to understand the logic of the proof.

The very first step of the proof assumes that the payment rule is exactly in the form given by Myerson's lemma:
$$p\_i(b\_i,\mathbf{b}\_{-i})=\int\_0^{b\_i}z\cdot x'\_i(z,\mathbf{b}\_i)\mathrm{dz}$$
where $x'\_i(z,\mathbf{b}\_i)$ is the derivative of the allocation rule $x'\_i(z,\mathbf{b}\_i)$. Then substitute the formula of payment into the profit object
$$\mathbb{E}\left[\sum\_{i=1}^n\mathbf{p}(\mathbf{v})\right]$$
with some calculus the "virtual-welfare" magically shows up.

Then the author claims that maximizing the virtual welfare is equivalent to maximizing revenue, and if the corresponding allocation rule is monotone then we get a optimal DSIC mechanism. I have two questions about this:

1. The result relies on the assumption that the payment rule is given in the previous form. Why does it must be in that form? The proof feels like some circular reasoning. Is this because that we are restricted on searching only for DSIC mechanism?
2. Furthermore, sometimes there exists no monotone allocation rule to optimize the deduced *virtual welfare*, but does this also mean that there exists no monotone rule to optimize the original *profit*?

**Tags:** gt.game-theory, combinatorial-game-theory, mechanism-design


---

## 1 answers

### Answer by username_0 on 2016-07-21. Score: 2

I think I've gotten part of the answer. The above statement actually says that for any *truthful* mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form.


---

