Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Philosophy > Faculty    Search Help Login pdf version printable version 

Publications [#236213] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V; Derryberry, J; Sandholm, T, Combinatorial auctions with structured item graphs, Proceedings of the National Conference on Artificial Intelligence (December, 2004), pp. 212-218.
    (last updated on 2024/03/29)

    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.


Duke University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login