Combinatorial auctions with structured item graphs Export

@inproceedings{citeulike:3250850, abstract = {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.}, author = {Conitzer, Vincent and Derryberry, Jonathan and Tuomas, S.}, booktitle = {In AAAI}, citeulike-article-id = {3250850}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.2646}, keywords = {auctions}, pages = {212--218}, posted-at = {2008-09-12 18:55:57}, priority = {2}, title = {Combinatorial auctions with structured item graphs}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.2646}, year = {2004} }

TY - CONF ID - citeulike:3250850 L3 - citeulike-article-id:3250850 N2 - 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. EP - 218 TI - Combinatorial auctions with structured item graphs T2 - In AAAI SP - 212 KW - auctions AU - Conitzer, Vincent AU - Derryberry, Jonathan AU - Tuomas, S PY - 2004/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.2646 ER -