Designing Real-Time Feedback for Bidders in Homogeneous-Item Continuous Combinatorial Auctions1

摘要

Although combinatorial auctions are important mechanisms for many specialized applications, their adoption in general-purpose marketplaces is still fairly limited, partly due to the inherent difficulty in evaluating the efficacy of bids without the availability of comprehensive bidder support. In this paper, we present both theoretical results and computational designs to support real-time feedback to bidders in continuous combinatorial auctions, where bidders are free to join and leave the auction at any time. In particular, we focus on the broad class of single-item multi-unit (SIMU) combinatorial auctions, where multiple identical units of one homogenous item are being auctioned. We also consider two common ways to express bidding preferences: OR bids and XOR bids. For SIMU auctions with each of the two bid types, we present comprehensive analyses of auction dynamics, which can determine winning bids that satisfy allocative fairness, and compute critical evaluative metrics needed to provide bidder support, including bid winning and deadness levels. We also design the data structures and algorithms needed to provide bidder support in real time for SIMU auctions of practically relevant sizes. The computational tools proposed in this paper can facilitate the efficient and more transparent implementation of SIMU combinatorial auctions in business- and consumer-oriented markets.