On The Complexity of Combinatorial Auctions:  Structured Item Graphs and Hypertree Decompositions  [Extended Abstract]  Georg Gottlob  Computing Laboratory  Oxford University  OX1 3QD Oxford, UK  georg.gottlob@comlab.ox.ac.uk  Gianluigi Greco  Dipartimento di Matematica  University of Calabria  I-87030 Rende, Italy  ggreco@mat.unical.it  ABSTRACT  The winner determination problem in combinatorial   auctions is the problem of determining the allocation of the  items among the bidders that maximizes the sum of the  accepted bid prices. While this problem is in general   NPhard, it is known to be feasible in polynomial time on  those instances whose associated item graphs have bounded  treewidth (called structured item graphs). Formally, an item  graph is a graph whose nodes are in one-to-one   correspondence with items, and edges are such that for any bid, the  items occurring in it induce a connected subgraph. Note  that many item graphs might be associated with a given  combinatorial auction, depending on the edges selected for  guaranteeing the connectedness. In fact, the tractability  of determining whether a structured item graph of a fixed  treewidth exists (and if so, computing one) was left as a  crucial open problem.  In this paper, we solve this problem by proving that the  existence of a structured item graph is computationally   intractable, even for treewidth 3. Motivated by this bad news,  we investigate different kinds of structural requirements that  can be used to isolate tractable classes of combinatorial   auctions. We show that the notion of hypertree decomposition,  a recently introduced measure of hypergraph cyclicity, turns  out to be most useful here. Indeed, we show that the   winner determination problem is solvable in polynomial time  on instances whose bidder interactions can be represented  with (dual) hypergraphs having bounded hypertree width.  Even more surprisingly, we show that the class of tractable  instances identified by means of our approach properly   contains the class of instances having a structured item graph.  Categories and Subject Descriptors  J.4 [Computer Applications]: Social and Behavioral   Sciences-Economics; F.2 [Theory of Computation]:   Analysis of Algorithms and Problem Complexity  1. INTRODUCTION  Combinatorial auctions. Combinatorial auctions are  well-known mechanisms for resource and task allocation  where bidders are allowed to simultaneously bid on   combinations of items. This is desirable when a bidder"s valuation  of a bundle of items is not equal to the sum of her valuations  of the individual items. This framework is currently used to  regulate agents" interactions in several application domains  (cf., e.g., [21]) such as, electricity markets [13], bandwidth  auctions [14], and transportation exchanges [18].  Formally, a combinatorial auction is a pair I, B , where  I = {I1, ..., Im} is the set of items the auctioneer has  to sell, and B = {B1, ..., Bn} is the set of bids from the  buyers interested in the items in I. Each bid Bi has  the form item(Bi), pay(Bi) , where pay(Bi) is a rational  number denoting the price a buyer offers for the items in  item(Bi) ⊆ I. An outcome for I, B is a subset b of B  such that item(Bi)∩item(Bj) = ∅, for each pair Bi and Bj  of bids in b with i = j.  The winner determination problem. A crucial   problem for combinatorial auctions is to determine the outcome  b∗  that maximizes the sum of the accepted bid prices (i.e.,  Bi∈b∗ pay(Bi)) over all the possible outcomes. This   problem, called winner determination problem (e.g., [11]), is  known to be intractable, actually NP-hard [17], and even  not approximable in polynomial time unless NP = ZPP [19].  Hence, it comes with no surprise that several efforts have  been spent to design practically efficient algorithms for   general auctions (e.g., [20, 5, 2, 8, 23]) and to identify classes of  instances where solving the winner determination problem  is feasible in polynomial time (e.g., [15, 22, 12, 21]). In fact,  constraining bidder interaction was proven to be useful for  identifying classes of tractable combinatorial auctions.  Item graphs. Currently, the most general class of  tractable combinatorial auctions has been singled out by  modelling interactions among bidders with the notion of  item graph, which is a graph whose nodes are in one-to-one  correspondence with items, and edges are such that for any  152  Figure 1: Example MaxWSP problem: (a) Hypergraph  H I0,B0  , and a packing h for it; (b) Primal graph for  H I0,B0  ; and, (c,d) Two item graphs for H I0,B0  .  bid, the items occurring in it induce a connected subgraph.  Indeed, the winner determination problem was proven to be  solvable in polynomial time if interactions among bidders  can be represented by means of a structured item graph,  i.e., a tree or, more generally, a graph having tree-like   structure [3]-formally bounded treewidth [16].  To have some intuition on how item graphs can be built,  we notice that bidder interaction in a combinatorial auction  I, B can be represented by means of a hypergraph H I,B  such that its set of nodes N(H I,B ) coincides with set of  items I, and where its edges E(H I,B ) are precisely the bids  of the buyers {item(Bi) | Bi ∈ B}. A special item graph for  I, B is the primal graph of H I,B , denoted by G(H I,B ),  which contains an edge between any pair of nodes in some  hyperedge of H I,B . Then, any item graph for H I,B can be  viewed as a simplification of G(H I,B ) obtained by deleting  some edges, yet preserving the connectivity condition on the  nodes included in each hyperedge.  Example 1. The hypergraph H I0,B0  reported in   Figure 1.(a) is an encoding for a combinatorial auction I0, B0 ,  where I0 = {I1, ..., I5}, and item(Bi) = hi, for each  1 ≤ i ≤ 3. The primal graph for H I0,B0  is reported in  Figure 1.(b), while two example item graphs are reported in  Figure 1.(c) and (d), where edges required for maintaining  the connectivity for h1 are depicted in bold. ¡  Open Problem: Computing structured item  graphs efficiently. The above mentioned tractability result  on structured item graphs turns out to be useful in practice  only when a structured item graph either is given or can be  efficiently determined. However, exponentially many item  graphs might be associated with a combinatorial auction,  and it is not clear how to determine whether a structured  item graph of a certain (constant) treewidth exists, and if  so, how to compute such a structured item graph efficiently.  Polynomial time algorithms to find the best   simplification of the primal graph were so far only known for the cases  where the item graph to be constructed is a line [10], a cycle  [4], or a tree [3], but it was an important open problem (cf.  [3]) whether it is tractable to check if for a combinatorial  auction, an item graph of treewidth bounded by a fixed   natural number k exists and can be constructed in polynomial  time, if so.  Weighted Set Packing. Let us note that the hypergraph  representation H I,B of a combinatorial auction I, B is  also useful to make the analogy between the winner   determination problem and the maximum weighted-set packing  problem on hypergraphs clear (e.g., [17]).  Formally, a packing h for a hypergraph H is a set of   hyperedges of H such that for each pair h, h ∈ h with h = h , it  holds that h ∩ h = ∅. Letting w be a weighting function for  H, i.e., a polynomially-time computable function from E(H)  to rational numbers, the weight of a packing h is the   rational number w(h) = h∈h w(h), where w({}) = 0. Then,  the maximum-weighted set packing problem for H w.r.t. w,  denoted by MaxWSP(H, w), is the problem of finding a   packing for H having the maximum weight over all the packings  for H. To see that MaxWSP is just a different formulation  for the winner determination problem, given a   combinatorial auction I, B , it is sufficient to define the weighting  function w I,B (item(Bi)) = pay(Bi). Then, the set of the  solutions for the weighted set packing problem for H I,B  w.r.t. w I,B coincides with the set of the solutions for the  winner determination problem on I, B .  Example 2. Consider again the hypergraph H I0,B0    reported in Figure 1.(a). An example packing for H I0,B0  is  h = {h1}, which intuitively corresponds to an outcome for  I0, B0 , where the auctioneer accepted the bid B1. By   assuming that bids B1, B2, and B3 are such that pay(B1) =  pay(B2) = pay(B3), the packing h is not a solution for  the problem MaxWSP(H I0,B0  , w I0,B0  ). Indeed, the packing  h∗  = {h2, h3} is such that w I0,B0  (h∗  ) > w I0,B0  (h). ¡  Contributions  The primary aim of this paper is to identify large tractable  classes for the winner determination problem, that are,  moreover polynomially recognizable. Towards this aim, we  first study structured item graphs and solve the open   problem in [3]. The result is very bad news:  It is NP complete to check whether a combinatorial   auction has a structured item graph of treewidth 3. More  formally, letting C(ig, k) denote the class of all the   hypergraphs having an item tree of treewidth bounded by k,  we prove that deciding whether a hypergraph (associated  with a combinatorial auction problem) belongs to C(ig, 3)  is NP-complete.  In the light of this result, it was crucial to assess whether  there are some other kinds of structural requirement that  can be checked in polynomial time and that can still be  used to isolate tractable classes of the maximum   weightedset packing problem or, equivalently, the winner   determination problem. Our investigations, this time, led to very good  news which are summarized below:  For a hypergraph H, its dual ¯H = (V, E) is such that  nodes in V are in one-to-one correspondence with   hyperedges in H, and for each node x ∈ N(H), {h | x ∈ h ∧ h ∈  153  E(H)} is in E. We show that MaxWSP is tractable on the  class of those instances whose dual hypergraphs have   hypertree width[7] bounded by k (short: class C(hw, k) of   hypergraphs). Note that a key issue of the tractability is to  consider the hypertree width of the dual hypergraph ¯H   instead of the auction hypergraph H. In fact, we can show  that MaxWSP remains NP-hard even when H is acyclic (i.e.,  when it has hypertree width 1), even when each node is  contained in 3 hyperedges at most.  For some relevant special classes of hypergraphs in  C(hw, k), we design a higly-parallelizeable algorithm for  MaxWSP. Specifically, if the weighting functions can be  computed in logarithmic space and weights are   polynomial (e.g., when all the hyperegdes have unitary weights  and one is interested in finding the packing with the   maximum number of edges), we show that MaxWSP can be solved  by a LOGCFL algorithm. Recall, in fact, that LOGCFL is  the class of decision problems that are logspace reducible  to context free languages, and that LOGCFL ⊆ NC2 ⊆ P  (see, e.g., [9]).  Surprisingly, we show that nothing is lost in terms of  generality when considering the hypertree decomposition  of dual hypergraphs instead of the treewidth of item  graphs. To the contrary, the proposed hypertree-based  decomposition method is strictly more general than the  method of structured item graphs. In fact, we show that  strictly larger classes of instances are tractable according  to our new approach than according to the structured item  graphs approach. Intuitively, the NP-hardness of   recognizing bounded-width structured item graphs is thus not due  to its great generality, but rather to some peculiarities in  its definition.  The proof of the above results give us some interesting   insight into the notion of structured item graph. Indeed, we  show that structured item graphs are in one-to-one   correspondence with some special kinds of hypertree   decomposition of the dual hypergraph, which we call strict hypertree  decompositions. A game-characterization for the notion of  strict hypertree width is also proposed, which specializes  the Robber and Marshals game in [6] (proposed to   characterize the hypertree width), and which makes it clear the  further requirements on hypertree decompositions.  The rest of the paper is organized as follows. Section 2   discusses the intractability of structured item graphs. Section 3  presents the polynomial-time algorithm for solving MaxWSP  on the class of those instances whose dual hypergraphs have  bounded hypertree width, and discusses the cases where the  algorithm is also highly parallelizable. The comparison   between the classes C(ig, k) and C(hw, k) is discussed in   Section 4. Finally, in Section 5 we draw our conclusions by also  outlining directions for further research.  2. COMPLEXITY OF STRUCTURED  ITEM GRAPHS  Let H be a hypergraph. A graph G = (V, E) is an item  graph for H if V = N(H) and, for each h ∈ E(H), the  subgraph of G induced over the nodes in h is connected.  An important class of item graphs is that of structured item  graphs, i.e., of those item graphs having bounded treewidth  as formalized below.  A tree decomposition [16] of a graph G = (V, E) is a pair  T, χ , where T = (N, F) is a tree, and χ is a labelling  function assigning to each vertex p ∈ N a set of vertices  χ(p) ⊆ V , such that the following conditions are satisfied:  (1) for each vertex b of G, there exists p ∈ N such that  b ∈ χ(p); (2) for each edge {b, d} ∈ E, there exists p ∈ N  such that {b, d} ⊆ χ(p); (3) for each vertex b of G, the  set {p ∈ N | b ∈ χ(p)} induces a connected subtree of T.  The width of T, χ is the number maxp∈N |χ(p) − 1|. The  treewidth of G, denoted by tw(G), is the minimum width  over all its tree decompositions.  The winner determination problem can be solved in   polynomial time on item graphs having bounded treewidth [3].  Theorem 1 (cf. [3]). Assume a k-width tree   decomposition T, χ of an item graph for H is given. Then,  MaxWSP(H, w) can be solved in time O(|T|2  ×(|E(H)|+1)k+1  ).  Many item graphs can be associated with a hypergraph.  As an example, observe that the item graph in Figure 1.(c)  has treewidth 1, while Figure 1.(d) reports an item graph  whose treewidth is 2. Indeed, it was an open question  whether for a given constant k it can be checked in   polynomial time if an item graph of treewidth k exists, and if so,  whether such an item graph can be efficiently computed.  Let C(ig, k) denote the class of all the hypergraphs having  an item graph G such that tw(G) ≤ k. The main result of  this section is to show that the class C(ig, k) is hard to  recognize.  Theorem 2. Deciding whether a hypergraph H belongs to  C(ig, 3) is NP-hard.  The proof of this result relies on an elaborate reduction from  the Hamiltonian path problem HP(s, t) of deciding whether  there is an Hamiltonian path from a node s to a node t in a  directed graph G = (N, E). To help the intuition, we report  here a high-level overview of the main ingredients exploited  in the proof1  .  The general idea it to build a hypergraph HG such that  there is an item graph G for HG with tw(G ) ≤ 3 if and only  if HP(s, t) over G has a solution. First, we discuss the way  HG is constructed. See Figure 2.(a) for an illustration, where  the graph G consists of the nodes s, x, y, and t, and the set of  its edges is {e1 = (s, x), e2 = (x, y), e3 = (x, t), e4 = (y, t)}.  From G to HG. Let G = (N, E) be a directed graph.  Then, the set of the nodes in HG is such that: for each  x ∈ N, N(HG) contains the nodes bsx, btx, bx, bx, bdx; for  each e = (x, y) ∈ E, N(HG) contains the nodes nsx, nsx,  nty, nty , nse  x and nte  y. No other node is in N(HG).  Hyperedges in HG are of three kinds:  1) for each x ∈ N, E(HG) contains the hyperedges:  • Sx = {bsx} ∪ {nse  x | e = (x, y) ∈ E};  • Tx = {btx} ∪ {nte  x | e = (z, x) ∈ E};  • A1  x = {bdx, bx}, A2  x = {bdx, bx}, and A3  x = {bx, bx}  -notice that these hyperedges induce a clique on  the nodes {bx, bx, bdx};  1  Detailed proofs can be found in the Appendix, available at  www.mat.unical.it/∼ggreco/papers/ca.pdf.  154  Figure 2: Proof of Theorem 2: (a) from G to HG - hyperedges in 1) and 2) are reported only; (b) a skeleton  for a tree decomposition TD for HG.  • SA1  x = {bsx, bx}, SA2  x = {bsx, bx}, SA3  x =  {bsx, bdx} -notice that these hyperedges plus  A1  x, A2  x, and A3  x induce a clique on the nodes  {bsx, bx, bx, bdx};  • TA1  x = {btx, bx}, TA2  x = {btx, bx}, and TA3  x =  {btx, bdx} -notice that these hyperedges plus  A1  x, A2  x, and A3  x induce a clique on the nodes  {btx, bx, bx, bdx};  2) for each e = (x, y) ∈ E, E(HG) contains the hyperedges:  • SHx = {nsx, nsx};  • THy = {nty, nty };  • SEe = {nsx, nse  x} and SEe = {nsx, nse  x} -notice  that these two hyperedges plus SHx induce a clique  on the nodes {nsx, nsx, nse  x};  • TEe = {nty, nte  y} and TEe = {nty , nte  y} -notice  that these two hyperedges plus THy induce a clique  on the nodes {nty, nty , nte  y}.  Notice that each of the above hyperedges but those of the  form Sx and Tx contains exactly two nodes. As an example  of the hyperedges of kind 1) and 2), the reader may refer  to the example construction reported in Figure 2.(a), and  notice, for instance, that Sx = {bsx, nse2  x , nse3  x } and that  Tt = {btt, nte4  t , nte3  t }.  3) finally, we denote by DG the set containing the   hyperedges in E(HG) of the third kind. In the   reduction we are exploiting, DG can be an arbitrary set  of hyperedges satisfying the four conditions that are  discussed below. Let PG be the set of the following  |PG| ≤ |N| + 3 × |E| pairs: PG = {(bx, bx) | x ∈ N} ∪  {(nsx, nsx), (nty, nty ), (nse  x, nte  y) | e = (x, y) ∈ E}.  Also, let I(v) denote the set {h ∈ E(H) | v ∈ h} of the  hyperedges of H that are touched by v; and, for a set  V ⊆ N(H), let I(V ) = v∈V I(v). Then, DG has to be  a set such that:  (c1) ∀(α, β) ∈ PG, I(α) ∩ I(β) ∩ DG = ∅;  (c2) ∀(α, β) ∈ PG, I(α) ∪ I(β) ⊇ DG;  (c3) ∀α ∈ N such that ∃β ∈ N with (α, β) ∈ PG or  (β, α) ∈ PG, it holds: I(α) ∩ DG = ∅; and,  (c4) ∀S ⊆ N such that |S| ≤ 3 and where ∃α, β ∈ S  with (α, β) ∈ PG, it is the case that: I(S) ⊇ DG.  Intuitively, the set DG is such that each of its hyperedges  is touched by exactly one of the two nodes in every pair  155  of PG - cf. (c1) and (c2). Moreover, hyperedges in  DG touch only vertices included in at least a pair of PG  - cf. (c3); and, any triple of nodes is not capable of  touching all the elements of DG if none of the pairs that  can be built from it belongs to PG - cf. (c4).  The reader may now ask whether a set DG exists at  all satisfying (c1), (c2), (c3) and (c4). In the following  lemma, we positively answer this question and refer the  reader to its proof for an example construction.  Lemma 1. A set DG, with |DG| = 2 × |PG| + 2,   satisfying conditions (c1), (c2), (c3), and (c4) can be built  in time O(|PG|2  ).  Key Ingredients. We are now in the position of presenting  an overview of the key ingredients of the proof. Let G be  an arbitrary item graph for HG, and let TD = T, χ be a  3-width tree decomposition of G (note that, because of the  cliques, e.g., on the nodes {bsx, bx, bx, bdx}, any item graph  for HG has treewidth 3 at least).  There are three basic observations serving the purpose of  proving the correctness of the reduction.  Blocks of TD: First, we observe that TD must contain  some special kinds of vertex. Specifically, for each  node x ∈ N, TD contains a vertex bs(x) such that  χ(bs(x)) ⊇ {bsx, bx, bx, bdx}, and a vertex bt(x) such  that χ(bt(x)) ⊇ {btx, bx, bx, bdx}. And, for each edge  e = (x, y) ∈ E, TD contains a vertex ns(x,e) such that  χ(ns(x,e)) ⊇ {nse  x, nsx, nsx}, and a vertex nt(y,e) such  that χ(nt(y,e)) ⊇ {nte  y, nty, nty }.  Intuitively, these vertices are required to cover the  cliques of HG associated with the hyperedges of kind  1) and 2). Each of these vertices plays a specific  role in the reduction. Indeed, each directed edge  e = (x, y) ∈ E is encoded in TD by means of the  vertices: ns(x,e), representing precisely that e starts  from x; and, nt(y,e), representing precisely that e   terminates into y. Also, each node x ∈ N is encoded in  TD be means of the vertices: bs(x), representing the  starting point of edges originating from x; and, bt(x),  representing the terminating point of edges ending into  x. As an example, Figure 2.(b) reports the skeleton  of a tree decomposition TD. The reader may notice  in it the blocks defined above and how they are   related with the hypergraph HG in Figure 2.(a) - other  blocks in it (of the form w(x,y)) are defined next.  Connectedness between blocks,  and uniqueness of the connections: The second   crucial observation is that in the path connecting a   vertex of the form bs(x) (resp., bt(y)) with a vertex of  the form ns(x,e) (resp., nt(y,e)) there is one special  vertex of the form w(x,y) such that: χ(w(x,y)) ⊇  {nse  x , nte  y }, for some edge e = (x, y) ∈ E.   Guaranteeing the existence of one such vertex is precisely  the role played by the hyperedges in DG. The   arguments for the proof are as follows. First, we   observe that I(χ(bs(x))) ∩ I(χ(ns(x,e))) ⊇ DG ∪ {Sx}  and I(χ(bt(y))) ∩ I(χ(nt(y,e))) ⊇ DG ∪ {Ty}. Then,  we show a property stating that for a pair of   consecutive vertices p and q in the path connecting bs(x)  and ns(x,e) (resp., bt(y) and nt(y,e)), I(χ(p) ∩ χ(q)) ⊇  I(χ(bs(x))) ∩ I(χ(ns(x,e))) (resp., I(χ(p) ∩ χ(q)) ⊇  I(χ(bt(x))) ∩ I(χ(nt(y,e)))). Thus, we have: I(χ(p) ∩  χ(q)) ⊇ DG ∪{Sx} (resp., I(χ(p)∩χ(q)) ⊇ DG ∪{Ty}).  Based on this observation, and by exploiting the   properties of the hyperedges in DG, it is not difficult to  show that any pair of consecutive vertices p and q  must share two nodes of HG forming a pair in PG, and  must both touch Sx (resp., Ty). When the treewidth  of G is 3, we can conclude that a vertex, say w(x,y),  in this path is such that χ(w(x,y)) ⊇ {nse  x , nte  y }, for  some edge e = (x, y) ∈ E - to this end, note that  nse  x ∈ Sx, nte  t ∈ Ty, and I(χ(w(x,y))) ⊇ DG. In   particular, w(x,y) is the only kind of vertex satisfying these  conditions, i.e., in the path there is no further vertex  of the form w(x,z), for z = y (resp., w(z,y), for z = x).  To help the intuition, we observe that having a vertex  of the form w(x,y) in TD corresponds to the selection  of an edge from node x to node y in the Hamiltonian  path. In fact, given the uniqueness of these vertices   selected for ensuring the connectivity, a one-to-one   correspondence can be established between the existence  of a Hamiltonian path for G and the vertices of the  form w(x,y). As an example, in Figure 2.(b), the   vertices of the form w(s,x), w(x,y), and w(y,t) are in TD,  and GT D shows the corresponding Hamiltonian path.  Unused blocks: Finally, the third ingredient of the proof  is the observation that if a vertex of the form w(x,y),  for an edge e = (x, y) ∈ E is not in TD (i.e., if the  edge (x, y) does not belong to the Hamiltonian path),  then the corresponding block ns(x,e ) (resp., nt(y,e ))  can be arbitrarily appended in the subtree rooted at  the block ns(x,e) (resp., nt(y,e)), where e is the edge of  the form e = (x, z) (resp., e = (z, y)) such that w(x,z)  (resp., w(z,y)) is in TD.  E.g., Figure 2.(a) shows w(x,t), which is not used in  TD, and Figure 2.(b) shows how the blocks ns(x,e3)  and nt(t,e3) can be arranged in TD for ensuring the  connectedness condition.  3. TRACTABLE CASES VIA HYPERTREE  DECOMPOSITIONS  Since constructing structured item graphs is intractable, it  is relevant to assess whether other structural restrictions can  be used to single out classes of tractable MaxWSP instances.  To this end, we focus on the notion of hypertree   decomposition [7], which is a natural generalization of hypergraph  acyclicity and which has been profitably used in other   domains, e.g, constraint satisfaction and database query   evaluation, to identify tractability islands for NP-hard problems.  A hypertree for a hypergraph H is a triple T, χ, λ , where  T = (N, E) is a rooted tree, and χ and λ are labelling  functions which associate each vertex p ∈ N with two sets  χ(p) ⊆ N(H) and λ(p) ⊆ E(H). If T = (N , E ) is a subtree  of T, we define χ(T ) = v∈N χ(v). We denote the set of  vertices N of T by vertices(T). Moreover, for any p ∈ N,  Tp denotes the subtree of T rooted at p.  Definition 1. A hypertree decomposition of a   hypergraph H is a hypertree HD = T, χ, λ for H which satisfies  all the following conditions:  1. for each edge h ∈ E(H), there exists p ∈ vertices(T)  such that h ⊆ χ(p) (we say that p covers h);  156  Figure 3: Example MaxWSP problem: (a) Hypergraph  H1; (b) Hypergraph ¯H1; (b) A 2-width hypertree  decomposition of ¯H1.  2. for each node Y ∈ N(H), the set {p ∈ vertices(T) |  Y ∈ χ(p)} induces a (connected) subtree of T;  3. for each p ∈ vertices(T), χ(p) ⊆ N(λ(p));  4. for each p ∈ vertices(T), N(λ(p)) ∩ χ(Tp) ⊆ χ(p).  The width of a hypertree decomposition T, χ, λ is  maxp∈vertices(T )|λ(p)|. The HYPERTREE width hw(H) of H  is the minimum width over all its hypertree decompositions.  A hypergraph H is acyclic if hw(H) = 1. P  Example 3. The hypergraph H I0,B0  reported in   Figure 1.(a) is an example acyclic hypergraph. Instead, both  the hypergraphs H1 and ¯H1 shown in Figure 3.(a) and   Figure 3.(b), respectively, are not acyclic since their hypertree  width is 2. A 2-width hypertree decomposition for ¯H1 is  reported in Figure 3.(c).  In particular, observe that H1 has been obtained by  adding the two hyperedges h4 and h5 to H I0,B0  to model,  for instance, that two new bids, B4 and B5, respectively,  have been proposed to the auctioneer. ¡  In the following, rather than working on the hypergraph  H associated with a MaxWSP problem, we shall deal with its  dual ¯H, i.e., with the hypergraph such that its nodes are in  one-to-one correspondence with the hyperedges of H, and  where for each node x ∈ N(H), {h | x ∈ h ∧ h ∈ E(H)}  is in E( ¯H). As an example, the reader may want to check  again the hypergraph H1 in Figure 3.(a) and notice that the  hypergraph in Figure 3.(b) is in fact its dual.  The rationale for this choice is that issuing restrictions on  the original hypergraph is a guarantee for the tractability  only in very simple scenarios.  Theorem 3. On the class of acyclic hypergraphs, MaxWSP  is (1) in P if each node occurs into two hyperedges at most;  and, (2) NP-hard, even if each node is contained into three  hyperedges at most.  3.1 Hypertree Decomposition on the Dual  Hypergraph and Tractable Packing  Problems  For a fixed constant k, let C(hw, k) denote the class of  all the hypergraphs whose dual hypergraphs have   hypertree width bounded by k. The maximum weighted-set   packing problem can be solved in polynomial time on the class  C(hw, k) by means of the algorithm ComputeSetPackingk,  shown in Figure 4.  The algorithm receives in input a hypergraph H, a   weighting function w, and a k-width hypertree decomposition  HD = T=(N, E), χ, λ of ¯H.  For each vertex v ∈ N, let Hv be the hypergraph whose  set of nodes N(Hv) ⊆ N(H) coincides with λ(v), and whose  set of edges E(Hv) ⊆ E(H) coincides with χ(v). In an   initialization step, the algorithm equips each vertex v with all  the possible packings for Hv, which are stored in the set  Hv. Note that the size of Hv is bounded by (|E(H)| + 1)k  ,  since each node in λ(v) is either left uncovered in a   packing or is covered with precisely one of the hyperedges in  χ(v) ⊆ E(H). Then, ComputeSetPackingk is designed to  filter these packings by retaining only those that conform  with some packing for Hc, for each children c of v in T, as  formalized next. Let hv and hc be two packings for Hv and  Hc, respectively. We say that hv conforms with hc, denoted  by hv ≈ hc if: for each h ∈ hc ∩ E(Hv), h is in hv; and, for  each h ∈ (E(Hc) − hc), h is not in hv.  Example 4. Consider again the hypertree   decomposition of ¯H1 reported in Figure 3.(c). Then, the set of all  the possible packings (which are build in the initialization  step of ComputeSetPackingk), for each of its vertices, is   reFigure 5: Example application of Algorithm  ComputeSetPackingk.  157  Input: H, w, and a k-width hypertree decomposition HD = T =(N, E), χ, λ of ¯H;  Output: A solution to MaxWSP(H, w);  var Hv : set of packings for Hv, for each v ∈ N; h∗  : packing for H;  v  hv  : rational number, for each partial packing hv for Hv;  hhv,c : partial packing for Hc, for each partial packing hv for Hv, and for each (v, c) ∈ E;    -------------------------------------------Procedure BottomUp;  begin  Done := the set of all the leaves of T ;  while ∃v ∈ T such that (i) v ∈ Done, and (ii) {c | c is child of v} ⊆ Done do  for each c such that (v, c) ∈ E do  Hv := Hv − {hv | ∃hc ∈ Hc s.t. hv ≈ hc};  for each hv ∈ Hv do  v  hv  := w(hv);  for each c such that (v, c) ∈ E do  ¯hc := arg maxhc∈Hc|hv≈ hc  c  hc  − w(hc ∩ hv) ;  hhv,c := ¯hc; (* set best packing *)  v  hv  := v  hv  + c  ¯hc  − w(¯hc ∩ hv);  end for  end for  Done := Done ∪ {v};  end while  end;    -------------------------------------------begin (* MAIN *)  for each vertex v in T do  Hv := {hv packing for Hv};  BottomUp;  let r be the root of T ;  ¯hr := arg maxhr∈Hr  r  hr  ;  h∗  := ¯hr; (* include packing *)  T opDown(r, hr);  return h∗  ;  end.  Procedure T opDown(v : vertex of N, ¯hv ∈ Hv);  begin  for each c ∈ N s.t. (v, c) ∈ E do  ¯hc := h¯hv,c;  h∗  := h∗  ∪ ¯hc; (* include packing *)  T opDown(c, ¯hc);  end for  end;  Figure 4: Algorithm ComputeSetPackingk.  ported in Figure 5.(a). For instance, the root v1 is such that  Hv1 = { {}, {h1}, {h3}, {h5} }.  Moreover, an arrow from a packing hc to hv denotes that  hv conforms with hc. For instance, the reader may check  that the packing {h3} ∈ Hv1 conforms with the packing  {h2, h3} ∈ Hv3 , but do not conform with {h1} ∈ Hv3 . ¡  ComputeSetPackingk builds a solution by traversing T in  two phases. In the first phase, vertices of T are processed  from the leaves to the root r, by means of the procedure  BottomUp. For each node v being processed, the set Hv is  preliminary updated by removing all the packings hv that  do not conform with any packing for some of the children  of v. After this filtering is performed, the weight hv is   updated. Intuitively, v  hv  stores the weight of the best partial  packing for H computed by using only the hyperedges   occurring in χ(Tv). Indeed, if v is a leaf, then v  hv  = w(hv).  Otherwise, for each child c of v in T, v  hv  is updated with  the maximum of c  hc  − w(hc ∩ hv) over all the packings hc  that conforms with hv (resolving ties arbitrarily). The   packing ¯hc for which this maximum is achieved is stored in the  variable hhv,c.  In the second phase, the tree T is processed starting from  the root. Firstly, the packing h∗  is selected that maximizes  the weight equipped with the packings in Hr. Then,   procedure TopDown is used to extend h∗  to all the other partial  packings for vertices of T. In particular, at each vertex v,  h∗  is extended with the packing hhv,c, for each child c of v.  Example 5. Assume that, in our running example,  w(h1) = w(h2) = w(h3) = w(h4) = 1. Then, an   execution of ComputeSetPackingk is graphically depicted in  Figure 5.(b), where an arrow from a packing hc to a   packing hv is used to denote that hc = hhv,c. Specifically, the  choices made during the computation are such that the   packing {h2, h3} is computed.  In particular, during the bottom-up phase, we have that:  (1) v4 is processed, and we set v4  {h2} = v4  {h4} = 1 and v4  {} = 0;  (2) v3 is processed, and we set v3  {h1} = v3  {h3} = 1 and v3  {} = 0;  (3) v2 is processed, and we set v2  {h1} = v2  {h2} = v2  {h3} =  v2  {h4} = 1, v2  {h2,h3} = 2 and v3  {} = 0; (4) v1 is processed  and we set v1  {h1} = 1, v1  {h5} = v1  {h3} = 2 and v1  {} = 0. For  instance, note that v1  {h5} = 2 since {h5} conforms with the  packing {h4} of Hv2 such that v2  {h4} = 1.  Then, at the beginning of the top-down phase,  ComputeSetPackingk selects {h3} as a packing for Hv1 and  propagates this choice in the tree. Equivalently, the   algorithm may have chosen {h5}.  As a further example, the way the solution {h1} is   obtained by the algorithm when w(h1) = 5 and w(h2) =  w(h3) = w(h4) = 1 is reported in Figure 5.(c). Notice  that, this time, in the top-down phase, ComputeSetPackingk  starts selecting {h1} as the best packing for Hv1 . ¡  Theorem 4. Let H be a hypergraph and w be a weighting  function for it. Let HD = T, χ, λ be a complete k-width  hypertree decomposition of ¯H. Then, ComputeSetPackingk  on input H, w, and HD correctly outputs a solution for  MaxWSP(H, w) in time O(|T| × (|E(H)| + 1)2k  ).  Proof. [Sketch] We observe that h∗  (computed by  ComputeSetPackingk) is a packing for H. Indeed, consider  a pair of hyperedges h1 and h2 in h∗  , and assume, for the  sake of contradiction, that h1 ∩ h2 = ∅. Let v1 (resp., v2)  be an arbitrary vertex of T, for which ComputeSetPackingk  included h1 (resp., h2) in h∗  in the bottom-down   computation. By construction, we have h1 ∈ χ(v1) and h2 ∈ χ(v2).  158  Let I be an element in h1 ∩ h2. In the dual hypergraph  H, I is a hyperedge in E( ¯H) which covers both the nodes  h1 and h2. Hence, by condition (1) in Definition 1, there is  a vertex v ∈ vertices(T) such that {h1, h2} ⊆ χ(v). Note  that, because of the connectedness condition in Definition 1,  we can also assume, w.l.o.g., that v is in the path connecting  v1 and v2 in T.  Let hv ∈ Hv denote the element added by  ComputeSetPackingk into h∗  during the bottom-down  phase. Since the elements in Hv are packings for Hv, it is the  case that either h1 ∈ hv or h2 ∈ hv. Assume, w.l.o.g., that  h1 ∈ hv, and notice that each vertex w in T in the path   connecting v to v1 is such that h1 ∈ χ(w), because of the   connectedness condition. Hence, because of definition of   conformance, the packing hw selected by ComputeSetPackingk  to be added at vertex w in h∗  must be such that h1 ∈ hw.  This holds in particular for w = v1. Contradiction with the  definition of v1.  Therefore, h∗  is a packing for H. It remains then to show  that it has the maximum weight over all the packings for H.  To this aim, we can use structural induction on T to prove  that, in the bottom-up phase, the variable v  hv  is updated  to contain the weight of the packing on the edges in χ(Tv),  which contains hv and which has the maximum weight over  all such packings for the edges in χ(Tv). Then, the result  follows, since in the top-down phase, the packing hr giving  the maximum weight over χ(Tr) = E(H) is first included in  h∗  , and then extended at each node c with the packing hhv,c  conformingly with hv and such that the maximum value of  v  hv  is achieved.  As for the complexity, observe that the initialization step  requires the construction of the set Hv, for each vertex v, and  each set has size (|E(H)| + 1)k  at most. Then, the function  BottomUp checks for the conformance between strategies  in Hv with strategies in Hc, for each pair (v, c) ∈ E, and  updates the weight v  hv  . These tasks can be carried out in  time O((|E(H)| + 1)2k  ) and must be repeated for each edge  in T, i.e., O(|T|) times. Finally, the function TopDown can  be implemented in linear time in the size of T, since it just  requires updating h∗  by accessing the variable hhv,c.  The above result shows that if a hypertree decomposition  of width k is given, the MaxWSP problem can be efficiently  solved. Moreover, differently from the case of structured  item graphs, it is well known that deciding the existence of  a k-bounded hypertree decomposition and computing one  (if any) are problems which can be efficiently solved in   polynomial time [7]. Therefore, Theorem 4 witnesses that the  class C(hw, k) actually constitutes a tractable class for the  winner determination problem.  As the following theorem shows, for large subclasses  (that depend only on how the weight function is specified),  MaxWSP(H, w) is even highly parallelizeable. Let us call a  weighting function smooth if it is logspace computable and  if all weights are polynomial (and thus just require O(log n)  bits for their representation). Recall that LOGCFL is a   parallel complexity class contained in NC2, cf. [9]. The   functional version of LOGCFL is LLOGCFL  , which is obtained by  equipping a logspace transducer with an oracle in LOGCFL.  Theorem 5. Let H be a hypergraph in C(hw, k), and let w  be a smooth weighting function for it. Then, MaxWSP(H, w)  is in LLOGCFL  .  4. HYPERTREE DECOMPOSITIONS VS  STRUCTURED ITEM GRAPHS  Given that the class C(hw, k) has been shown to be an  island of tractability for the winner determination problem,  and given that the class C(ig, k) has been shown not to be  efficiently recognizable, one may be inclined to think that  there are instances having unbounded hypertree width, but  admitting an item graph of bounded tree width (so that the  intractability of structured item graphs would lie in their  generality).  Surprisingly, we establish this is not the case. The line of  the proof is to first show that structured item graphs are in  one-to-one correspondence with a special kind of hypertree  decompositions of the dual hypergraph, which we shall call  strict. Then, the result will follow by proving that k-width  strict hypertree decompositions are less powerful than   kwith hypertree decompositions.  4.1 Strict Hypertree Decompositions  Let H be a hypergraph, and let V ⊆ N(H) be a set of  nodes and X, Y ∈ N(H). X is [V ]-adjacent to Y if there  exists an edge h ∈ E(H) such that {X, Y } ⊆ (h − V ). A  [V ]-path π from X to Y is a sequence X = X0, . . . , X = Y  of variables such that: Xi is [V ]-adjacent to Xi+1, for each  i ∈ [0... -1]. A set W ⊆ N(H) of nodes is [V ]-connected  if ∀X, Y ∈ W there is a [V ]-path from X to Y . A  [V ]-component is a maximal [V ]-connected non-empty set  of nodes W ⊆ (N(H) − V ). For any [V ]-component C, let  E(C) = {h ∈ E(H) | h ∩ C = ∅}.  Definition 2. A hypertree decomposition HD =  T, χ, λ of H is strict if the following conditions hold:  1. for each pair of vertices r and s in vertices(T)  such that s is a child of r, and for each  [χ(r)]-component Cr s.t. Cr ∩ χ(Ts) = ∅, Cr is a  [χ(r) ∩ N(λ(r) ∩ λ(s))]-component;  2. for each edge h ∈ E(H), there is a vertex p such that  h ∈ λ(p) and h ⊆ χ(p) (we say p strongly covers h);  3. for each edge h ∈ E(H), the set {p ∈ vertices(T) | h ∈  λ(p)} induces a (connected) subtree of T.  The strict hypertree width shw(H) of H is the minimum  width over all its strict hypertree decompositions. P  The basic relationship between nice hypertree   decompositions and structured item graphs is shown in the following  theorem.  Theorem 6. Let H be a hypergraph such that for each  node v ∈ N(H), {v} is in E(H). Then, a k-width tree   decomposition of an item graph for H exists if and only if ¯H  has a (k + 1)-width strict hypertree decomposition2  .  Note that, as far as the maximum weighted-set packing  problem is concerned, given a hypergraph H, we can always  assume that for each node v ∈ N(H), {v} is in E(H). In  fact, if this hyperedge is not in the hypergraph, then it can  be added without loss of generality, by setting w({v}) = 0.  Therefore, letting C(shw, k) denote the class of all the   hypergraphs whose dual hypergraphs (associated with maximum  2  The term +1 only plays the technical role of taking care  of the different definition of width for tree decompositions  and hypertree decompositions.  159  weighted-set packing problems) have strict hypertree width  bounded by k, we have that C(shw, k + 1) = C(ig, k).  By definition, strict hypertree decompositions are special  hypertree decompositions. In fact, we are able to show that  the additional conditions in Definition 2 induce an actual  restriction on the decomposition power.  Theorem 7. C(ig, k) = C(shw, k + 1) ⊂ C(hw, k + 1).  A Game Theoretic View. We shed further lights on  strict hypertree decompositions by discussing an interesting  characterization based on the strict Robber and Marshals  Game, defined by adapting the Robber and Marshals game  defined in [6], which characterizes hypertree width.  The game is played on a hypergraph H by a robber against  k marshals which act in coordination. Marshals move on  the hyperedges of H, while the robber moves on nodes of  H. The robber sees where the marshals intend to move, and  reacts by moving to another node which is connected with  its current position and through a path in G(H) which does  not use any node contained in a hyperedge that is occupied  by the marshals before and after their move-we say that  these hyperedges are blocked. Note that in the basic game  defined in [6], the robber is not allowed to move on vertices  that are occupied by the marshals before and after their  move, even if they do not belong to blocked hyperedges.  Importantly, marshals are required to play monotonically,  i.e., they cannot occupy an edge that was previously   occupied in the game, and which is currently not. The marshals  win the game if they capture the robber, by occupying an  edge covering a node where the robber is. Otherwise, the  robber wins.  Theorem 8. Let H be a hypergraph such that for each  node v ∈ N(H), {v} is in E(H). Then, ¯H has a k-width  strict hypertree decomposition if and only if k marshals can  win the strict Robber and Marshals Game on ¯H, no matter  of the robber"s moves.  5. CONCLUSIONS  We have solved the open question of determining the  complexity of computing a structured item graph   associated with a combinatorial auction scenario. The result is  bad news, since it turned out that it is NP-complete to  check whether a combinatorial auction has a structured item  graph, even for treewidth 3. Motivated by this result, we   investigated the use of hypertree decomposition (on the dual  hypergraph associated with the scenario) and we shown that  the problem is tractable on the class of those instances whose  dual hypergraphs have bounded hypertree width. For some  special, yet relevant cases, a highly parallelizable algorithm  is also discussed. Interestingly, it also emerged that the class  of structured item graphs is properly contained in the class  of instances having bounded hypertree width (hence, the  reason of their intractability is not their generality).  In particular, the latter result is established by showing  a precise relationship between structured item graphs and  restricted forms of hypertree decompositions (on the dual  hypergraph), called query decompositions (see, e.g., [7]). In  the light of this observation, we note that proving some   approximability results for structured item graphs requires a  deep understanding of the approximability of query   decompositions, which is currently missing in the literature.  As a further avenue of research, it would be relevant to  enhance the algorithm ComputeSetPackingk, e.g., by using  specialized data structures, in order to avoid the quadratic  dependency from (|E(H)| + 1)k  .  Finally, an other interesting question is to assess whether  the structural decomposition techniques discussed in the   paper can be used to efficiently deal with generalizations of the  winner determination problem. For instance, it might be   relevant in several application scenarios to design algorithms  that can find a selling strategy when several copies of the  same item are available for selling, and when moreover the  auctioneer is satisfied when at least a given number of copies  is actually sold.  Acknowledgement  G. Gottlob"s work was supported by the EC3 - E-Commerce  Competence Center (Vienna) and by a Royal Society   Wolfson Research Merit Award. In particular, this Award   allowed Gottlob to invite G. Greco for a research visit to   Oxford. In addition, G. Greco is supported by ICAR-CNR,  and by M.I.U.R. under project TOCAI.IT.  6. REFERENCES  [1] I. Adler, G. Gottlob, and M. Grohe. Hypertree-Width  and Related Hypergraph Invariants. In Proc. of  EUROCOMB"05, pages 5-10, 2005.  [2] C. Boutilier. Solving Concisely Expressed  Combinatorial Auction Problems. In Proc. of  AAAI"02, pages 359-366, 2002.  [3] V. Conitzer, J. Derryberry, and T. Sandholm.  Combinatorial auctions with structured item graphs.  In Proc. of AAAI"04, pages 212-218, 2004.  [4] E. M. Eschen and J. P. Sinrad. An o(n2  ) algorithm for  circular-arc graph recognition. In Proc. of SODA"93,  pages 128-137, 1993.  [5] Y. Fujishima, K. Leyton-Brown, and Y. Shoham.  Taming the computational complexity of  combinatorial auctions: Optimal and approximate. In  Proc. of IJCAI"99, pages 548-553, 1999.  [6] G. Gottlob, N. Leone, and F. Scarcello. Robbers,  marshals, and guards: game theoretic and logical  characterizations of hypertree width. Journal of  Computer and System Sciences, 66(4):775-808, 2003.  [7] G. Gottlob, N. Leone, and S. Scarcello. Hypertree  decompositions and tractable queries. Journal of  Computer and System Sciences, 63(3):579-627, 2002.  [8] H. H. Hoos and C. Boutilier. Solving combinatorial  auctions using stochastic local search. In Proc. of  AAAI"00, pages 22-29, 2000.  [9] D. Johnson. A Catalog of Complexity Classes. In  P. Cramton, Y. Shoham, and R. Steinberg, editors,  Handbook of Theoretical Computer Science, Volume  A: Algorithms and Complexity, pages 67-161. 1990.  [10] N. Korte and R. H. Mohring. An incremental  linear-time algorithm for recognizing interval graphs.  SIAM Journal on Computing, 18(1):68-81, 1989.  [11] D. Lehmann, R. M¨uller, and T. Sandholm. The  Winner Determination Problem. In P. Cramton,  Y. Shoham, and R. Steinberg, editors, Combinatorial  Auctions. MIT Press, 2006.  [12] D. Lehmann, L. I. O"Callaghan, and Y. Shoham.  Truth revelation in approximately efficient  160  combinatorial auctions. J. ACM, 49(5):577-602, 2002.  [13] R. McAfee and J. McMillan. Analyzing the airwaves  auction. Journal of Economic Perspectives,  10(1):159175, 1996.  [14] J. McMillan. Selling spectrum rights. Journal of  Economic Perspectives, 8(3):145-62, 1994.  [15] N. Nisan. Bidding and allocation in combinatorial  auctions. In Proc. of EC"00, pages 1-12, 2000.  [16] N. Robertson and P. Seymour. Graph minors ii.  algorithmic aspects of tree width. Journal of  Algorithms, 7:309-322, 1986.  [17] M. H. Rothkopf, A. Pekec, and R. M. Harstad.  Computationally manageable combinatorial auctions.  Management Science, 44:1131-1147, 1998.  [18] T. Sandholm. An implementation of the contract net  protocol based on marginal cost calculations. In Proc.  of AAAI"93, pages 256-262, 1993.  [19] T. Sandholm. Algorithm for optimal winner  determination in combinatorial auctions. Artificial  Intelligence, 135(1-2):1-54, 2002.  [20] T. Sandholm. Winner determination algorithms. In  P. Cramton, Y. Shoham, and R. Steinberg, editors,  Combinatorial Auctions. MIT Press, 2006.  [21] T. Sandholm and S. Suri. Bob: Improved winner  determination in combinatorial auctions and  generalizations. Artificial Intelligence, 7:33-58, 2003.  [22] M. Tennenholtz. Some tractable combinatorial  auctions. In Proc. of AAAI"00, pages 98-103, 2000.  [23] E. Zurel and N. Nisan. An efficient approximate  allocation algorithm for combinatorial auctions. In  Proc. of EC"01, pages 125-136, 2001.  161