How to generalize the Vickrey auction for two-sided trading?

Question

I want to try out the Vickrey auction for a project of mine, but I'm not sure that I understand it completely. The thing is that I have several consumers and several providers trading one resource type on the market. If I have just one provider and several consumers, the things are pretty straight forward. But what happens if I have more of them? If I randomly choose one provider's offer and try to find the appropriate buyer and then continue until I find a match for all the offers, it might happen that I won't find the optimal solution. For example, I have two offers (o1, o2) and two requirements (r1, r2). If I check first the best match for o1, I might find out that the best result would be o1-r1, and therefore o2-r2 (that's what's left). But what if when I first check the o2 and find out that o2-r1 and o1-r2 brings higher utility?

For me it seems the best to try out all solutions and then to compare the welfare, but it sounds incredibly stupid. It would take many iterations. Any ideas how to solve this?

Answer 1

One idea - borrowing from Google's 2nd Price auction model, which uses Vickery, for prioritizing rank of ads on their search page would be to determine a strictly monotonic increasing function $f(*)$, which applied to $u1 = (o1 - r1)$ and $u2 = (o2-r2)$ results in $o1*f(u1) \geq o2*f(u2)$ iff $o1 \geq o2$. The winner in this case would pay: $o2*f(u2) / f(u1)$.

In Google's case, they use a function that also incorporates other variables that describe the utility of being in a "winning" or higher ranked position for each resource.

Answer 2

I think there is a result that some generalizations of the Vickrey auction to two sided trading do not have balanced budgets: i.e. require additional incentives from the market maker. It occurs as a consequence of avoiding any participant's price being dependent on their own input. The "Vickrey" approach would be to make someone's price equal to the decrease in surplus of everyone else that is involved in accepting their bid or ask. But that means buyers all pay marginal cost of the most costly traded unit and sellers all receive marginal value of the lowest valued traded unit. Obviously there is a gap there and thats what the market maker has to pay to get traders individually to tell the truth. Also, it can be manipulated by groups of traders. Milgrom, "Putting Auction Theory To Work" http://www.amazon.com/Putting-Auction-Churchill-Lectures-Economics/dp/0521536723/ref=sr_1_1?ie=UTF8&qid=1314177894&sr=8-1 would be a good place to start reading for an understanding of these issues.

A more practical approach perhaps is the UPDA.

Consider using a uniform price double auction if you need a two-sided trading institution -- for buying or selling -- but want something like the kind of truth-telling incentive found in the Vickrey auction.

In the Uniform Price Double Auction, truth-telling bids/asks are incentive compatible if you are not the price setter because pricing is an order statistic (like a median, but not literally the median) not a mean. And, you can't know if you are the price setter if all the bids and asks are processed simultaneously and in secret. Like the Vickrey auciton, with the UPDA, strategic under pricing or over pricing by a participant exposes that specific participant to either lost opportunities that would have made money or to actual deals with losses.

If your single resource type consists of identical units of a commodity, then a reasonable approach is the uniform price double auction, as follows:

1. All bids (quotes from buyers) and asks (quotes from sellers) are for single units of a well-defined commodity good or service. To bid for multiple units, just send more than one bid or ask. Collect all the bids and asks from everyone in two arrays b[], and a[]. Thats two arrays for the entire market, not for each participant.
2. Sort the bids in b[] by price from high to low.
3. Sort the asks in a[] by price from low to high.
4. Find q*>0, perhaps incrementally, such that b[q*]>=a[q*] AND b[q*+1]<a[q*+1]
5. Make every bid/ask corresponding to an array index q, q<=q* a trade. q>q* does NOT trade
6. Set price the same for all traders, p can be set anywhere from as low as max(a[q*],b[q*+1]) to as high as min(b[q*],a[q*+1]) and the result will be consistent with all the bids and asks. It is common to calculate both and choose the midpoint.

You might also want to do some reading on Experimental Economics, where many variations of auctions and markets have been studied with prototype software in human subject laboratories where the human subjects trade for profit. I have also done some work in this area.

See:

Vernon L. Smith, Economics in the Laboratory, Journal of Economic Perspectives, Vol 8, no.1, 1994.

You can find a few examples of uniform price double auctions in Smith's collected works, which can be had on Amazon:

http://www.amazon.com/Papers-Experimental-Economics-Vernon-Smith/dp/052102465X/ref=sr_1_7?ie=UTF8&qid=1314072760&sr=8-7