Complexity and Tractability Islands for Combinatorial Auctions on Discrete Intervals with Gaps

Combinatorial auctions are mechanisms for allocating bundles of goods to agents who each have preferences over these goods. Finding an economically efficient allocation, the so-called winner determination problem, is computationally intractable in the general case, which is why it is important to identify special cases that are tractable but also sufficiently expressive for applications. We introduce a family of auction problems in which the goods on auction can be rearranged into a sequence, and each bid submitted concerns a bundle of goods corresponding to an interval on this sequence, possibly with multiple gaps of bounded length. We investigate the computational complexity of the winner determination problem for such auctions and explore the frontier between tractability and intractability in detail, identifying tractable, intractable, and fixed-parameter tractable cases.