Skip to main content

Combinatorial auctions with structured item graphs

Publication ,  Journal Article
Conitzer, V; Derryberry, J; Sandholm, T
Published in: Proceedings of the National Conference on Artificial Intelligence
December 9, 2004

Combinatorial auctions (CAs) are important mechanisms for allocating interrelated items. Unfortunately, winner determination is NP-complete unless there is special structure. We study the setting where there is a graph (with some desired property), with the items as vertices, and every bid bids on a connected set of items. Two computational problems arise: 1) clearing the auction when given the item graph, and 2) constructing an item graph (if one exists) with the desired property. 1 was previously solved for the case of a tree or a cycle, and 2 for the case of a line graph or a cycle. We generalize the first result by showing that given an item graph with bounded treewidth, the clearing problem can be solved in polynomial time (and every CA instance has some treewidth; the complexity is exponential in only that parameter). We then give an algorithm for constructing an item tree (treewidth 1) if such a tree exists, thus closing a recognized open problem. We show why this algorithm does not work for treewidth greater than 1, but leave open whether item graphs of (say) treewidth 2 can be constructed in polynomial time. We show that finding the item graph with the fewest edges is NP-complete (even when a graph of treewidth 2 exists). Finally, we study how the results change if a bid is allowed to have more than one connected component. Even for line graphs, we show that clearing is hard even with 2 components, and constructing the line graph is hard even with 5.

Duke Scholars

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

December 9, 2004

Start / End Page

212 / 218
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Conitzer, V., Derryberry, J., & Sandholm, T. (2004). Combinatorial auctions with structured item graphs. Proceedings of the National Conference on Artificial Intelligence, 212–218.
Conitzer, V., J. Derryberry, and T. Sandholm. “Combinatorial auctions with structured item graphs.” Proceedings of the National Conference on Artificial Intelligence, December 9, 2004, 212–18.
Conitzer V, Derryberry J, Sandholm T. Combinatorial auctions with structured item graphs. Proceedings of the National Conference on Artificial Intelligence. 2004 Dec 9;212–8.
Conitzer, V., et al. “Combinatorial auctions with structured item graphs.” Proceedings of the National Conference on Artificial Intelligence, Dec. 2004, pp. 212–18.
Conitzer V, Derryberry J, Sandholm T. Combinatorial auctions with structured item graphs. Proceedings of the National Conference on Artificial Intelligence. 2004 Dec 9;212–218.

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

December 9, 2004

Start / End Page

212 / 218