On the Computational Power of Iterative Auctions II: Ascending Auctions

Liad Blumrosen and Noam Nisan

We embark on a systematic analysis of the power and limitations of iterative ascending-price combinatorial auctions. We prove a large number of results showing the boundaries of what can be achieved by different types of ascending auctions: item prices vs. bundle prices, anonymous prices vs. personalized prices, deterministic vs. non-deterministic, ascending vs. descending, preference elicitation vs. full elicitation, adaptive vs. non-adaptive, and single trajectory vs. multi trajectory. Two of our main results show that neither ascending item-price auctions nor ascending anonymous bundle-price auctions can determine the optimal allocation among general valuations. This justifies the use of personalized bundle prices in iterative combinatorial auctions like the FCC spectrum auctions.

February, 2005
Published in: