Home > theory > MHR, Regular Distributions and Myerson’s Lemma

MHR, Regular Distributions and Myerson’s Lemma

May 30th, 2011 Leave a comment Go to comments

Monotone Hazard Rate (MHR) distributions and its superclass regular distributions keep appearing in the Mechanism Design literature and this is due to a very good reason: they are the class of distributions for which Myerson’s Optimal Auction is simple and natural. Let’s brief discuss some properties of those distributions. First, two definitions:

  1. Hazard rate of a distribution f : h(z) = \frac{f(z)}{1-F(z)}
  2. Myerson virtual value of a distribution f : \phi(z) = z - \frac{1-F(z)}{f(z)}

We can interpret the hazard rate in the following way: think of T \sim f as a random variable that indicates the time that a light bulb will take to extinguish. If we are in time t and the light bulb hasn’t extinguished so far, what is the probability it will extinguish in the next \delta time:

\mathbb{P}[T \leq t+\delta \vert T > t] \approx \frac{f(t) \delta}{1-F(t)}

We say that a distribution is monotone hazard rate, if h(z) is non-decreasing. This is very natural for light bulbs, for example. Many of the distributions that we are used to are MHR, for example, uniform, exponential and normal. The way that I like to think about MHR distributions is the following: if some distribution has hazard rate h(z), then it means that F'(z) = (1-F(z)) h(z). If we define G(z) = 1-F(z), then (log G(z))' = \frac{G'(z)}{G(z)} = -h(z), so:

F(z) = 1-\text{exp}(-\int_0^z h(u) du)

From this characterization, it is simple to see that the extremal distributions for this class, i.e. the distributions that are in the edge of being MHR and non-MHR are constant hazard rate, which correspond to the exponential distribution F(z) = 1-e^{-\lambda z} for z \in [0,\infty). They way I like to think about those distributions is that whenever you are able to prove something about the exponential distribution, then you can prove a similar statement about MHR distributions. Consider those three examples:

Example 1: \mathbb{P}[\phi(z) \geq 0] \geq \frac{1}{e} for MHR distributions. This fact is straightforward for the exponential distribution. For the exponential distribution \phi(z) = z-\lambda^{-1} and therefore

\mathbb{P}[\phi(z) \geq 0] \geq \mathbb{P}[z > \lambda^{-1}] = 1-F(\lambda^{-1}) = e^{-1}

but the proof for MHR is equally simple: Let r = \inf \{z; \phi(z) \geq 0\}, therefore r h(r) \leq 1.
P\{ \phi(v) \geq 0\} = P\{ v \geq r \} = 1 - F(r) = e^{-\int_0^r h(u) du} \geq e^{-r h(r)} \geq e^{-1}

Example 2: Given z_1, z_2 \sim f iid where f is MHR and v_1 = \max \{z_1, z_2\} and v_2 = \min \{z_1, z_2\}, then \mathbb{E}[v_2] \geq \frac{1}{3} \mathbb{E}[v_1]. The proof for the exponential distribution is trivial, and in fact, this is tight for the exponential, the trick is to use the convexity of z \mapsto \int_0^z h(u) du. We use that \int_0^{2z} h \geq 2 \int_0^z h in the following way:

\mathbb{E} [v_2] = \int_0^\infty (1 - F(z))^2 dz = \int_0^\infty e^{-2 \int_0^z h} dz

\geq \int_0^\infty e^{-\int_0^{2z} h} dz= \frac{1}{2} \int_0^\infty 1 - F(z) dz = \frac{1}{2} \mathbb{E} [z]

Since \mathbb{E} [v_1 + v_2] = \mathbb{E} [z_1 + z_2] = 2 \mathbb{E} [z], we have that \mathbb{E}[v_1] = 2 \mathbb{E}[z] - \mathbb{E}[v_2] \leq \frac{3}{2} \mathbb{E}[z]. This way, we get: \mathbb{E}[v_2] \geq \frac{1}{2}\mathbb{E}[z] \geq \frac{1}{2} \cdot \frac{2}{3} \mathbb{E}[v_1] = \frac{1}{3} \mathbb{E}[v_1]

Example 3: For MHR distributions, there is a simple lemma that relates the virtual value and the real value and this lemma is quite useful in various settings: let r = \inf \{z; \phi(z) > 0 \}, then for z \geq r, \phi(z) \geq z - r. Again, this is tight for exponential distribution. The proof is quite trivial:

x - \phi(x) = \frac{1-F(x)}{f(x)} \leq \frac{1-F(r)}{f(r)} = r

Now, MHR distributions are a subclass of regular distributions, which are the distributions for which Myerson’s virtual value \phi(z) is a monotone function. I usually find harder to think about regular distributions than to think about MHR (in fact, I don’t know so many examples that are regular, but not MHR. Here is one, though, called the equal-revenue-distribution. Consider z \in [1, \infty) distributed according to f(z) = 1/z^2. The cumulative distribution is given by F(z) = 1-1/z. The interesting thing of this distribution is that posted prices get the same revenue regardless of the price. For example, if we post any price r \in [1,\infty), then a customer with valuations z \sim f buys the item if z > r by price r, getting  revenue is r (1-F(r)) = 1. This can be expressed by the fact that \phi(z) = 0. I was a bit puzzled by this fact, because of Myerson’s Lemma:

Myerson Lemma: If a mechanism sells to some player that has valuation v \sim f with probability x(v) when he has value v, then the revenue is \mathbb{E} [x(v) \phi(v)].

And it seemed that the auctioneers was doomed to get zero revenue, since \phi(z) = 0. For example, suppose we fix some price r and we sell the item if v \geq r by price r. Then it seems that Myerson’s Lemma should go through by a derivation like that (for this special case, although the general proof is quite similar):

\mathbb{E} [x(v) \phi(v)] = \int_r^\infty \phi(z) f(z) dz = \int_r^\infty z f(z) - (1-F(z)) dz =

= \int_r^\infty [ z f(z) - \int_z^\infty f(u) du ] dz = \int_r^\infty z f(z) dz - \int_r^\infty \int_r^u f(u) dz du

= r (1-F(r))

but those don’t seem to match, since one side is zero and the other is 1. The mistake we did above is classic, which is to calculate \infty - \infty. We wrote:

\mathbb{E}[\phi(v)] = \int_r^\infty z f(z) dz - \int_r^\infty 1-F(z) dz

but both are infinity! This made me realize that Myerson’s Lemma needs the condition that \mathbb{E}[z] < \infty, which is quite a natural a distribution over valuations of a good. So, one of the bugs of the the equal-revenue-distribution is that \mathbb{E}[z] = \infty. A family that is close to this, but doesn’t suffer this bug is: f(z) = \frac{\alpha-1}{z^\alpha} for z \in [1,\infty), then F(z) = 1 - z^{1-\alpha}. For \alpha > 2 we have \mathbb{E}[v] < \infty, then we get \phi(z) = \frac{\alpha-2}{\alpha-1} z.

Categories: theory Tags: ,
  1. No comments yet.
  1. No trackbacks yet.