Market-based allocation with indivisible bids

• 成果类型: Article; Proceedings Paper
• 署名作者: Schvartzman, L. Julian; Wellman, Michael P.
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• 发表日期: 2007
• 页码: 495-509
• 关键词: auction algorithms; price quotes; indivisible bids; AON auctions; incremental multiple-choice knapsack problem

摘要

We study multiunit double auctions accepting bids with indivisibility constraints. Modeling the auction problem as a Multiple Choice Knapsack Problem and using dynamic programming, we show that incremental computations during bid processing can speed the handling of key auction operations such as clearing and quoting. We propose different price-quote policies and study their influence on the efficiency of market-based allocation. Using a reconfigurable manufacturing scenario where agents trade large quantities of multiple goods, we demonstrate potential benefits of supporting indivisibility constraints in bidding. These benefits are highly sensitive to the form of price quote provided, indicating interesting tradeoffs in communication and allocation efficiency.