Mechanism Design for Grandma

Ok, Grandma may still have some difficulty but in honor of today's Nobelists, Hurwicz, Maskin and Myerson let's give it a go.  Suppose that you are selling a rare painting for which you want to raise the maximum revenue.  There are two potential buyers, Tyler, who values the painting at $100,000, and Alex who values it at $20,000.  The problem would be simple if you knew this information - you would then set the price at $99,999 and Tyler would buy maximizing your revenue.  But how much Tyler and Alex value the painting is their own private information.  How then should sell the painting?

One possibility that springs quickly to mind is an auction.  In a standard English open-cry auction Alex and Tyler will bid for the painting and the bids will keep rising until Alex is forced to drop out at $20,001.  Thus the auction earns you $20,001.  Not bad but is this the maximum revenue possible?  Remember that Tyler values the painting at $100,000 so you could be leaving a lot of money on the table.

What else can you do?  Well, how about an auction with a reserve price, say $50,000 - think of a reserve price as a secret bidder who calls in his bids on the phone.  A reserve price of $50,000 works well in this case as Tyler will pay $50,001.  But note that you just got lucky, if Tyler had valued the good at $30,000 you would have earned nothing at all.  Thus you would like to know whether a reserve is always optimal and how to set it.  (Riley and Samuelson, and much more generally Myerson both show that a reserve price is always optimal and how to set it).

But why stop at a reserve price?  How about a reserve price and an entry fee?  But why stop at reserve prices and entry fees?  You can add any kind of requirement to the auction that you want but will these requirements help you to raise revenue?  Lets boil the problem down to its essence.  Think about an auction as a mechanism - bidders put information into the mechanism, their bids, and the mechanism tells them the outcome.  (Hurwicz was the first to really start thinking about mechanisms in these very general terms.)

You want to design the mechanism to achieve a certain outcome.  The mechanism can be as complicated as you want but it must satisfy certain conditions.  First, the bidders must participate voluntarily - you can't boil them in oil - so there is a participation constraint.  At the end of the day the bidders must expect to be at least as well off as if they did not play the mechanism game (at least on average).

Second, there is an incentive compatability constraint.  You don't know how much Alex and Tyler truly value the painting so suppose that Tyler mimics whatever Alex does - Tyler can do this since he values the painting at least as much as Alex does.  It follows that whatever outcome the mechanism assigns to Alex, Tyler must get at least as much.  This is a significant constraint because it means that if you want Tyler to do something different than Alex, and you do, you want Tyler to bid more, then you must give Tyler something in return.  Thus, even in the optimal mechanism you, the seller, are not going to get everything.  Tyler is going to walk away with some surplus.

We still haven't solved for optimal mechanism, however.  And here is where the magic comes.  Not magic as in something wonderful but magic as in hand-waving.  Maskin and Myerson proved something very useful about mechanisms with these types of constraints.  It turns out that if you follow the constraints then you can restrict attention to mechanisms in which Tyler and Alex always tell the truth about their values, this is called the revelation principle.  (In a sense, this is obvious for imagine that we find the optimal mechanism given that Tyler and Alex submit whatever bids/information they want.  Then you tell Tyler and Alex - next time why don't you tell the truth about your values and we promise to give you exactly the outcome that we would have given you under the previous mechanism.)

In the case of auctions the direct mechanism is well known, a second price auction.  In a second price auction the high bidder wins but pays the second highest-bid.  In this auction it makes sense for every bidder to bid his true value - see if you can work out why - and it turns out that as the revelation principle says, revenues in this direct auction are the same as in say a regular English auction (under certain conditions, of course).

Ok, I have gone on for a while.  Here's the bottom line.  The basic set-up of agents with private information submitting "bids" which are then fed into a mechanism resulting in outcomes is very general.  How to raise taxes, regulate a monopolist, fund a public good (here's my own contribution to mechanism design), allocate organs, assign interns to hospitals, split common costs, allocate electricity across a grid - all can be thought of as mechanism design problems.   The tools that Hurwicz, Maskin and Myerson developed and their methods of paying attention to participation and incentive compatability constraints and using the revelation principle helps us to design, at least in principle, the best solutions to all of these problems.