Mechanism Designing of Multi-unit Combinatorial Online Double Auction

Combinatorial (double) auctions have recently been used in business-to-business trading of centralized marketplace or other multi-agent coordination systems. When the goods are indivisible, winner determination problem (WDP) can be described as an integer-programming model and NP-hard in its general form, so a novel multi-round combinatorial double auction mechanism is proposed to solve it. A multi-objection integer programming is set up to study special properties of online combinatorial double auctions so as to search for the optimal solutions of the model. Comparing to previous researches on double auction, the combinatorial double auctions mechanism expatriated shows some advantages in respect that running for several rounds to matching bids as more as possible and permitting agents applying online learning algorithms to adjust bidding strategy adaptively to pursue more bargain opportunities. Agents trade identical bundles of goods with discriminatory prices, which embodied the diversity and flexibility of practical market. Result of a typical example shows that the mechanism increased the overall revenue and improved market efficiency greatly relative to single-round combinatorial (double) auctions