The complexity of mixed multi-unit combinatorial auctions: tractability under structural and qualitative restrictions. (English) Zbl 1270.91026

Fionda, Valeria; Greco, Gianluigi

Artif. Intell. 196, 1-25 (2013).

Summary: Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i.e., determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from classical combinatorial auctions, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out on the basis of their characteristics. The paper fills this gap, by studying the computational complexity of MMUCA instances under structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively.

MSC:

91B26	Auctions, bargaining, bidding and selling, and other market models
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25	Analysis of algorithms and problem complexity