One of the great theorems in economics is Myerson’s optimal auction when selling one good to any number of buyers with private valuations of the good. Don’t underrate this theorem just because it is mathematically quite simple: the question it answers is how to sell any object, using any mechanism (an auction, a price, a bargain, a two step process involving eliciting preferences first, and so on). That an idea as straightforward as the revelation principle makes that question possible to answer is truly amazing.
Myerson’s paper was published 32 years ago. Perhaps more amazing that the simplicity of the Myerson auction is how difficult it has been to derive similar rules for selling more than one good at a time, selling goods more than once, or selling goods when the sellers compete. The last two have well known problems that make analysis difficult: dynamic mechanisms suffer from the “ratchet effect”: a buyer won’t reveal information if she knows a seller will use it in subsequent sales, and competing mechanisms can have an IR constraint which is generated as an equilibrium condition. Hart and Reny, in a new note, show some great examples of the difficulty with the first difficult mechanism problem, selling multiple goods. In particular, increases in the distribution of private values (in the sense of first order stochastic dominance) can lower the optimal revenue, and randomized mechanisms can raise it.
Consider first increases in the private value distribution. This is strange: if for any state of the world, I value your goods more, it seems reasonable that there is “more surplus to extract” for the seller. And indeed, not only does the Myerson optimal auction with a single good have the property that increases in private values lead to increased seller revenue, but Hart and Reny show that any incentive-compatible mechanism with a single good has this property.
(This is actually very easy to prove, and a property I’d never seen stated for the general IC case, so I’ll show it here. If q(x) is the probability I get the good given the buyer’s reported type x, and s(x) is the seller revenue given this report, then incentive compatibility when the true type is x requires that
q(x)x-s(x)>=q(y)x-s(y)
and incentive compatibility when the true type is y requires that
q(y)y-s(y)>=q(x)y-s(x)
Combining these inequalities gives
(q(x)-q(y))x>=s(x)-s(y)>=(q(x)-q(y))y
Hence when x>y, q(x)-q(y)>=0, therefore s(x)>=s(y) for all x and y, therefore a fosd shift in the buyer valuations increases the expected value of seller revenue s. Nice!)
When selling multiple goods, however, this nice property doesn’t hold. Why not? Imagine the buyer might have values for (one unit of each of) 2 goods I am trying to sell of (1,1), (1,2), (2,2) or (2,3). Imagine (2,3) is a very common set of private values. If I knew this buyer’s type, I would extract 5 from him, though if I price the bundle including one of each good at 5, then none of the other types will buy. Also, if I want to extract 5 from type (2,3), then I also can’t sell unit 1 alone for less than 2 or unit 2 alone for less than 3, in which case the only other buyer will be (2,2) buying good 1 alone for price 2. Let’s try lowering the price of the bundle to 4. Now, satisfying (2,3)’s incentive compatibility constraints, we can charge as little as 1 for the first good bought by itself and 2 for the second good bought by itself: at those prices, (2,3) will buy the bundle, (2,2) will buy the first good for 1, and (1,2) will buy the second good for 2. This must look strange to you already: when the buyer’s type goes up from (1,2) to (2,2), the revenue to the seller falls from 2 to 1! And it turns out the prices and allocations described are the optimal mechanism when (2,2) is much less common than the other types. Essentially, across the whole distribution of private values the most revenue can be extracted by selling the second good, so the optimal way to satisfy IC constraints involves making the IC tightest for those whose relative value of the second good is high. Perhaps we ought call the rents (2,2) earns in this example “uncommon preference rents”!
Even crazier is that an optimal sale of multiple goods might involve using random mechanisms. It is easy to show that with a single good, a random mechanism (say, if you report your value for the good is 1 dollar, the mechanism assigns you the good with probability .5 for a payment of 50 cents) does no better than a deterministic mechanism. A footnote in the Hart and Reny paper credits Aumann for the idea that this is actually pretty strange: a mechanism is a sequential game where the designer moves first. It is intuitive that being able to randomize would be useful in these types of situations; in a matching pennies game, I would love to be able to play .5 heads and .5 tails when moving first! But the optimal mechanism with a single good does not have this property, for an intuitive reason. Imagine I will sell the good for X. Every type with private value below X does not buy, and those with types V>=X earn V-X in information rents. Offering to sell the good with probability .5 for price X/2 does not induce anybody new to buy, and selling with probability .5 for price Y less than X/2 causes some of the types close to X to switch to buying the lottery, lowering the seller revenue. Indeed, it can be verified that the revenue from the lottery just described is exactly the revenue from a mechanism which offered to sell the good with probability 1 for price 2Y<X.
With multiple goods, however, let high and low type buyers be equally common. Let the high type buyer be indifferent between buying two goods for X, buying the first good only for Y, and buying the second good only for Z (where IC requires that X generate the most seller revenue as long as buyer values are nonnegative). Let the low type value only the first good, at value W less than Y. How can I sell to the low type without violating the high type’s IC constraints? Right now, if the high type buyer has values V1 and V2 for the two goods, the indifference assumptions means V1+V2-X=V1-Y=V2-Z. Can I offer a fractional sale (with probability p) of the first good at price Y2 such that pW-Y2>=0, yet pV1-Y2<V1+V2-X=V1-Y? Sure. The low value buyer is just like the low value buyers in the single good case, but the high value buyer dislikes fractional sales because in order to buy the lottery, she is giving up her purchase of the second good. Giving up buying the second good costs her V2 in welfare whether a fraction or the whole of good 1 is sold, but the benefit of deviating is lower with the lottery.
April 2013 working paper (IDEAS version). Update: Sergiu notes there is a new version as of December 21 on his website. (Don’t think the paper is all bad news for deriving general properties of optimal mechanisms. In addition to the results above, Hart and Reny also show a nice result about mechanisms where there are multiple optimal responses by buyers, some good for the seller and some less so. It turns out that whenever you have a mechanism of this type, there is another mechanism that uniquely generates revenue arbitrarily close to the seller-optimal from among those multiple potential buyer actions in the first mechanism.)
A Fine Theorem 