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.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com