In this note I describe the Vickrey auction at the heart of the exploratory bandwidth allocation implementation. In this auction, bidding agents for video conferees submit split bids for each of several discrete service levels, one for each alternative video compression scheme available to them. The auctioneer considers available bandwidth that these levels would place on the underlying network links and allocates capacity to the conferees to maximize total utility, as expressed in the bids. A feasible allocation here is complicated by the fact that different conferees use different combinations of links of limited capacity.

This auction overcomes a problem with a more obvious scheme where the agents bid independently in auctions at each of the links required for the circuit. In such a simpler scheme the conferees may win some bids but lose a bid for a critical part of the circuit. He must then pay for and waste the capacity he bought in the other auctions.

The allocation computation is combinatorial and is thus suitable for only a handful of concurrent conferences. It also fails to interface to other network allocation mechanisms. It does not deal with variable rate compression schemes where the demand fluctuates faster than auctions can be held, but it may be possible to sell excess capacity on the spot market.

In the note I allow bidders who submit bids to sell as well as to buy. This requires me to distinguish between auctioneer and seller. With this insight it becomes clear that the auctioneer must pay to make the market run efficiently.

I have rumors that these general results are already known in micro-economics.

Many of the ideas are expressed in US patent 5640569.

Here are some web pointers to interesting auction papers.

Here is a game that uses Vickrey auctions to allocate bandwidth in continuously varying amounts.

Mechanism Design Theory seems relevant!