Charting the Tractability Frontier of Mixed Multi-Unit Combinatorial Auctions

Abstract

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 CAs, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out based on constraining their characteristics. The paper precisely fills this gap, by depicting a clear picture of the tractability frontier for MMUCA instances under both structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. By analyzing these restrictions, a sharp frontier is charted based on various dichotomy results. In particular, tractability islands resulting from the investigation generalize on MMUCAs the largest class of tractable CAs emerging from the literature.Valeria Fionda, Gianluigi Greco