Designing information feedback for bidders in multi-item multi-unit combinatorial auctions

摘要

Combinatorial auctions (CAs) promote allocative efficiency and are important market mechanisms for a wide variety of specialized domains where bidders are allowed to place bids on packages of items. However, the adoption of combinatorial auctions in real-life business scenarios has been fairly limited, perhaps because bidders find it difficult to construct their bids without extensive knowledge of the current state of the auction. In this paper, we develop decision support tools for bidders to provide information feedback at runtime for the general class of combinatorial auctions namely, online (continuous) multi-item multi-unit combinatorial auctions (MUCAs), an area that has witnessed a rapid growth of interest in recent years. In online MUCAs the number of packages may be large, and bidders need real time decision support to construct their bids, such as information on the ask prices of packages. The deadness level of a package serves as the ask price, and indicates the minimum bid on the package that keeps it in contention for inclusion in winning combinations in future. It has proved a challenge to find a satisfactory method for computing the deadness levels of packages in MUCAs. Here we present exact methods for determining package deadness levels in such auctions. Both the OR and the XOR formulations are considered. Experiments on simulated data as well as on live data show that the time and memory requirements are not excessive, so it appears possible to adopt the methods for the procurement and sale of commodities in B2B and B2C markets.