Multi-option descending clock auction

A descending clock auction (DCA) is for buying items from multiple sellers. The literature has focused on the case where each bidder has two options: to accept or reject the offered price. However, in many settings-such as the FCC's imminent incentive auction-each bidder may be able to sell one from a set of options. We present a multi-option DCA (MDCA) framework where at each round, the auctioneer offers each bidder different prices for different options, and a bidder may find multiple options still acceptable. Setting prices during a MDCA is trickier than in a DCA. We develop a Markov chain model for the dynamics of each bidder's state (which options are still acceptable). We leverage it to optimize the trajectory of price offers to different bidders for different options. This is unlike most auctions which only compute the next price vector. Computing the trajectory enables better planning. We reoptimize the trajectory after each round. Each optimization minimizes total payment while ensuring feasibility in a stochastic sense. We also introduce percentile-based approaches to decrementing prices. Experiments with real FCC incentive auction interference constraint data show that the optimization-based approach dramatically outperforms the percentile-based approach - because it takes feasibility into account in pricing. Both pricing techniques scale to the large. Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.