I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.