Spectrum Allocation and Combinatorial Auctions
How to divide up the rights to the spectrum of electromagnetic waves is a difficult problem. There are certain parts of the spectrum that are very valuable, such as the optimal bandwidth to transmit data to cell phones, or to broadcast a television or radio signal. In order to make sure this valuable bandwidth is allocated to the companies for which it has the most value, the Federal Communications Commission auctions off licenses to use certain pieces of bandwidth in certain places. Unfortunately, this type of auction is not as simple to analyze as the auctions we did in class. This is because companies usually care about bundles spanning multiple licenses, for example, if they want to use one frequency over a large area, or they need a continuous segment of bandwidth that’s wider than just one license. This means how much they value one license is strongly dependent on which other licenses they successfully win.
It is hard to structure these actions properly. If the licenses are just auctioned off sequentially bidders have to make difficult predictions over how likely they are to win future bids, and if these predictions are wrong they might end up being very disadvantaged. If all actions are auctioned off at once, it becomes advantageous for bidders to delay making bids until after others have bid, so they have information about which items they are likely to get. If all bids are made secretly so that gathering information about other bids before making your own is impossible, then it is very likely that bidders will get a part, but not all, of bundles they want which means that they just wasted large amounts of money for something that has less value. Clearly, none of these are optimal ways to run the auction.
The way that FCC currently runs its bids is with a round-based structure, with all the licenses up for sale each round [1]. After participants bid simultaneously each round, the FCC releases the leaders of each auction. When no one is interested in upping another’s bid, the auction closes. There are activity rules to ensure that participants can not wait until the last minute to make all their bids as if they do not bid enough in one round they will be penalized in later rounds [2]. While this system works, it is not particularly efficient and has several of the problems discussed in the previous paragraph. In an ideal bidding system, participants would be incentivized to honestly state how much they value different combinations of licenses, and there would be some algorithm to optimally assign the licenses based on the values. Finding the optimal way to assign licenses is a computationally complex problem, however. In 2002, however, Tuomas Sandholm published a paper that presented a relatively efficient allocation algorithm that allows actors to state how much they value each combination of good. This auction system has the same property as 2nd price auctions, that the optimal bidding strategy is to bid one’s true valuation. Clearly, we should adopt such an algorithm for FCC auctions and other situations where bidder preferences are better described in terms of sets of goods, instead of individual goods.
[2] Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, Volume 135, Issue 1, 2002, Pages 1-54, ISSN 0004-3702, http://dx.doi.org/10.1016/S0004-3702(01)00159-X.
(http://www.sciencedirect.com/science/article/pii/S000437020100159X)