Charting the Tractability Frontier of Mixed Multi-Unit Combinatorial Auctions

1 Introduction

Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just simple goods [Cerquides et al., 2007]. These mechanisms are particularly useful in the context of automating supply chain formation, where production processes often emerge as the result of complex interactions among producers and consumers (cf. [Walsh andWellman, 2003]).

Formally, a transformation over a set G of types of goods is a tuple 〈I, O, p〉 where I ∈ N|G| (resp., O ∈ N|G| ) is a vector of natural numbers denoting the quantities of the goods that are required (resp., produced) for the transformation to take place (resp., as a result of the transformation), and p ∈ R is the payment the bidder is willing to make in return for being allocated the transformation 1 . Then, a mixed multi-unit combinatorial auction instance is a tuple 〈G, T , Uin, Uout〉 where

1 If p < 0, then the auctioneer must actually pay -p to the bidder in order for she to implement the transformation.

Gianluigi Greco

Dip. di Matematica Universit`a della Calabria I-87036 Rende, Italy ggreco@mat.unical.it

T is a multi-set of transformations over G, and Uin ∈ N|G| (resp., Uout ∈ N|G| ) is a vector denoting the quantities of goods the auctioneer holds to begin with (resp., expects to end up with). Solving a MMUCA instance 〈G, T , Uin, Uout〉 amounts to finding a sequence of transformations such that, based on the input goods in Uin, the auctioneer may end up with the desired goods in Uout with the maximum possible revenue (short: WINNER-DETERMINATION problem).

The above problem has been intensively studied in recent years, by extending to MMUCAs several results originally conceived for classical CAs. In particular, languages have been defined and analyzed that allow bidders to compose (atomic) bids in a natural and intuitive way [Cerquides et al., 2007]; and, motivated by their intractability (formally, NPhardness), solution approaches have been proposed (see, e.g., [Giovannucci et al., 2007]) that well-behave on realistic scenarios [Ottens and Endriss, 2008].

Differently from classical CAs, however, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out based on the structural and topological properties of the instances at hand. As a matter of fact, by focusing on the kinds of interactions among bidders that are likely to occur in practice, classes of instances over which WINNER-DETERMINATION is tractable-called "islands of tractability" in the literature-have been identified for classical CAs (such as structured item graphs [Conitzer et al., 2004] or bounded hypertree-width dual hypergraphs [Gottlob and Greco, 2007]). However, none of these results had a counterpart in the case of MMUCAs.

The aim of this paper is precisely to fill this gap, by depicting a clear and complete picture of the frontier of tractability for MMUCA instances. In particular, since the existence of a solution is not guaranteed in the case of MMUCAs (unlike classical CAs), attention is focused not only on the WINNERDETERMINATION but also on the FEASIBILITY problem of deciding whether a given instance admits a solution at all; indeed, an important and peculiar source of complexity for MMUCAs lays hidden in this latter problem.

In more detail, in the first part of the paper, we show two interesting dichotomy results pertaining FEASIBILITY, which precisely determine the frontier of tractability under qualitative restrictions, i.e., under restrictions characterizing the types of bids in terms of the variety and quantity of goods involved in the various transformations. In fact:

1. In the casewhere each bidder submits amulti-set of transformations and accepts any combination of them for the sum of their prizes (short: OR-language), we show that FEASIBILITY is tractable if and only if every transformation requires and produces one item of one single good at most, or every type of good is required (or produced) as input (resp., output) by one transformation at most.
2. In the case where each bidder accepts at most one transformation from the multi-set of hers submitted transformations (short: XOR-language), we show that FEASIBILITY is tractable if and only if every type of good is required as input by one transformation at most.

Then, we turn to consider structural properties of the networks originating from bidder interactions, motivated by the fact that many NP-hard problems in different application areas are known to be efficiently solvable when restricted to instances that can be modeled via (nearly)acyclic graphs. Surprisingly, bad news emerged from our investigation. Indeed:

1. We show that FEASIBILITY is hard on (nearly)acyclic instances too. In particular, this is the case for two natural ways of encoding bidder interactions, namely for transformations graphs (where nodes are in one-to-one correspondence with transformations and an edge indicates that one transformation produces a good required by the other), and for goods graphs (where nodes are in one-to-one correspondence with goods and an edge indicates the possibility of transforming a good into another).

Eventually, in the final part of the paper, we focus on the WINNER-DETERMINATION problem, in order to single out tractable classes of MMUCAs complementing those defined in [Conitzer et al., 2004; Gottlob and Greco, 2007] for CAs:

1. On the one hand, WINNER-DETERMINATION emerges to be intractable under most kinds of qualitative restrictions, for it inherits all the intractability results that hold with FEASIBILITY as well as with classical CAs.
2. However, on the other hand, we show that if qualitative restrictions are combined with suitable structural restrictions (on a hypergraph encoding the interactions), then a tractable class of instances can be identified, which truly generalizes on MMUCAs the largest class of tractable CAs singled out in the literature [Gottlob and Greco, 2007]. In particular, for this class, a polynomial-time solution algorithm is proposed and its properties are analyzed.

The rest of the paper is organized as follows. Section 2 reports a few preliminaries on MMUCAs. The complexity of FEASIBILITY under qualitative and structural restrictions is discussed in Section 3 and Section 4, respectively. Tractability islands for the WINNER-DETERMINATION problem are isolated in Section 5, and conclusions are drawn in Section 6.

2 MixedMulti-Unit Combinatorial Auctions

Let G be a set of types of goods. For each vector W ∈ N|G| , we denote by W(g) the element of W referring to any good g ∈ G. Sometimes, W will be viewed as a multi-set over G.

Let A = 〈G, T , Uin, Uout〉 be a MMUCA instance. Solving A amounts to deciding which transformations have to be accepted, and in which order to implement them.

Formally, consider a sequence of transformations σ = 〈I1,O1, p1〉, ..., 〈Ik,Ok, pk〉 such that 〈Ii,Oi, pi〉 ∈ T , for each i ∈ {1, ..., k}. Let M0 = Uin denote the quantities of goods initially hold by the auctioneer, and let Mi ∈ N|G| be the quantities owned after the i-th transformation, i.e., ∀g ∈ G, Mi(g) = Mi-1(g) + Oi(g) - Ii(g).

Then, σ is legal w.r.t. A if Mi-1(g) ≥ Ii(g), for each i ∈ {1, ..., k} and g ∈ G. The revenue of the auctioneer with σ is the sum of the payments associated with each transformation in it, i.e., the value ∑ki=1 pi. Under the free disposal assumption, a legal sequence of transformations σ is a solution to A if ∀g ∈ G, Mk(g) ≥ Uout(g). An optimal solution is a solution providing the auctioneer with the maximum revenue over all the possible solutions.

Throughout the paper we shall always look for (optimal) solutions under the free disposal assumption.

Bidding Languages. In the basic setting above, there is a one-to-one correspondence between bidders and transformations. However, in many practical cases, bidders may want to exploit more expressive languages to submit bids, in place of submitting atomic transformations only. Thus, as commonly done in the literature, we assume that bidders may submit multi-sets of transformations under conditions of two kinds.

An OR-condition on a multi-set S ⊆ T states that the bidder may accept any transformations in S at the sum of the respective prizes; instead, a XOR-condition states that she is prepared to accept at most one of them. Equipping A with a set L of c-conditions (with c ∈ {OR, XOR}, ⋃S∈L S = T , and S ∩ S ′ = ∅, ∀S, S ′ ∈ L) is denoted by A[L,c].

3 FEASIBILITY and Qualitative Restrictions

In this section, we start the analysis of the complexity of FEASIBILITY, by taking into account various qualitative properties of the underlying instances, as for they can formally be measured in terms of the following parameters:

• in-var(A) = max〈I ,O,p〉∈T |{I (g) | g ∈ G, I (g) > 0}| is the input variety of A, i.e., the maximum number of types of goods required as input over all transformations. Symmetrically, the output variety is the value out-var(A) = max〈I ,O,p〉∈T |{O(g) | g ∈ G, O(g) > 0}|.
• in-mul(A) = max〈I ,O,p〉∈T ,g∈G I (g) is the input multiplicity of A, i.e., the maximum quantity of any good required as input over all transformations. And, symmetrically, the output multiplicity is the value out-mul(A) = max〈I ,O,p〉∈T ,g∈G O(g).
• in-deg(A) = maxg∈G |{〈I,O, p〉 ∈ T | O(g) > 0}| is the input degree of A, i.e., the maximum number of transformations producing a given good over all goods. Symmetrically, the output degree of A is the value out-deg(A) = maxg∈G |{〈I,O, p〉 ∈ T | I (g) > 0}|.

Below, C(iv, ov, im, om, id, od) will denote the class of instances A such that: in-var(A) ≤ iv, out-var(A) ≤ ov, in-mul(A) ≤ im, out-mul(A) ≤ om, in-deg(A) ≤ id, and out-deg(A) ≤ od. Also, the symbol ∞ is used to denote that no bound is issued on some given parameter.

Results. A summary of our analysis is reported in Figure 1: Our results clearly depict a tractability frontier, since relaxing any condition in a tractable scenario leads to intractability and since FEASIBILITY trivializes when turning some parameter from 1 to 0 (details on these trivial cases are omitted). Note also that the expressiveness of the XOR-language [Cerquides et al., 2007] is payed in terms of a smaller tractability island.

In the remainder, we overview the proofs of these results, by starting with OR-conditions. In particular, we shall consider a "normal form" for MMUCAs where for each good g ∈ G such that Uout(g) > 0 (resp., Uin(g) > 0), there is no transformation 〈I,O, p〉 ∈ T such that I (g) > 0 (resp., O(g) > 0) holds-indeed, any instance can be modified in polynomial time as to meet this requirement.

3.1 Tractable Instances (OR-conditions)

We next illustrate the good news on the tractability of FEASIBILITY. We start by considering the case where every transformation requires and produces an item of one good at most.

Theorem 3.1 Let A = 〈G, T , Uin, Uout〉[L,OR] be a MMUCA such that A ∈ C(1, 1, 1, 1,∞,∞). Then, FEASIBILITY can be solved in time O (|G|3 ) .

Proof. (Sketch). Based on A, consider the directed graph (N,E) built as follows. The set N of the nodes contains a node g for each good g ∈ G, plus the distinguished node n. There is an edge (g, g′ ) from g to g′ in E if there is a transformation 〈Ih,Oh, ph〉 ∈ T such that Ih(g) > 0 and Oh(g′ ) > 0; and, there is an edge (g, n) ∈ E for each g ∈ G.

The idea is now to consider (N, E) as a demand flow network (see, e.g., [Kleinberg and Tardos, 2005]) where:

• (i) each edge (g, g′ ) has capacity u(g, g′) = 1, and each edge (g, n) has capacity u(g, n) = Uin(g); and,
• (ii) each node g has demand d(g) = Uout(g) -Uin(g), while n has demand d(n) = ∑g∈G(Uin(g) - Uout(g)).

It can be shown that A has a solution if and only if there is a circulation on (N, E), i.e., a function f : E ↦→ R such that f (v, v′ ) ≤ u(v, v′ ) for each (v, v′ ) ∈ E, and Ps∈N f(s, v) - Pt∈N f(v, t) = d(v), for each v ∈ N.

Eventually, the existence of a circulation can be checked in O(|G|3 ), where (|G| + 1) is the number of nodes in N. In fact, note that OR-conditions do not play any role here. ✷

Let us now turn to the scenario where every type of good is produced by one transformation at most, i.e., let us assume that the input degree is unitary at most. Moreover, let Δ = maxg(Uin(g)+ ∑〈I ,O,p〉∈T O(g)) be an upper bound on the number of any good produced over all solutions.

Theorem 3.2 Let A = 〈G, T , Uin, Uout〉[L,OR] be a MMUCA such that A ∈ C(∞,∞,∞,∞, 1,∞). Then, FEASIBILITY can be solved in time O(|T |2 × |G| × log Δ).

Proof. (Sketch). Let Tr ⊆ T denote the set of all the necessary transformations w.r.t. some good g with Uout(g) > 0, built as follows. Initially, Tr includes all the transformations that may produce output goods only; then, Tr is iteratively updated (until the fixed point is reached) by including those transformations that may produce goods required in input by some transformation already in Tr. Since in-deg(A) ≤ 1, A admits a solution if and only if it is possible to execute all the transformations in Tr. Thus, we may simple start applying transformations in Tr till a step k is reached such all the transformations in Tr are applied (thereby witnessing that there is a solution to A), or there is some transformation in Tr that cannot be applied (so that there is no solution to A). In particular, note that the application of any transformation does not interfere with the applicability of other transformations (since in-deg(A) ≤ 1). Hence, the execution order of applicable transformations is not relevant. Eventually, O(|T |) steps are required, each one feasible in O(|T | × |G| × logΔ), where in particular the logarithmic factor accounts for the complexity of executing algebraic manipulations over the numbers involved in the computation. ✷

A complementary reasoning (i.e., applying transformations from input goods till there is an applicable transformation) shows the tractability of unitary output degree instances.

Theorem 3.3 Let A = 〈G, T , Uin, Uout〉[L,OR] be a MMUCA such that A ∈ C(∞,∞,∞,∞,∞, 1). Then, FEASIBILITY can be solved in time O(|T |2 × |G| × log Δ).

3.2 Hard Instances (OR-conditions)

Hardness results are next provided as reductions from the SATISFIABILITY of Boolean formulas in conjunctive normal form. In particular, recall that deciding whether a Boolean formula in conjunctive normal form Φ = c1 ∧ . . . ∧ cm over the variables X1, . . . , Xn is satisfiable is NP-hard. Below, we state the intractability of a specific class of Boolean formulas.

Lemma 3.4 SATISFIABILITY is NP-hard, even if each variable occurs positively in at most two clauses and negatively in at most one other clause, and if each clause contains three variables at most.

Theorem 3.5 FEASIBILITY is NP-complete, even under atomic bids and restricted on the class C(1, 2, 1, 1, 2, 2).

Proof. (Sketch). Membership in NP was show in [Cerquides et al., 2007] for the whole class C(∞,∞,∞,∞,∞,∞).

As for the hardness, let Φ be a formula satisfying the conditions in Lemma 3.4, and A(Φ) = 〈G, T , Uin, Uout〉 be such that: G = ⋃ni=1{Xi,X T i , X F i } ∪ {c1, ..., cm} ∪ {cij | Xi occurs in cj}, Uin = {X1, ...,Xn}, Uout = {c1, ..., cm}, and T = ⋃ni=1 Ti, where Ti (for 1 ≤ i ≤ n) is defined next.

For each variable Xi occurring positively in the clauses cα and cβ while occurring negatively in cγ, the set Ti consists of the transformations 2 graphically depicted in Figure 2adaptations to the cases where Xi does not negatively occur in a clause and positively in two further clauses are trivial and, hence, omitted. Observe that two transformations occur in Ti requiringXi as input, one that produces X T i and another that produces X F i . These transformations are meant to encode the selection of a truth value assignment to the variableXi and, in fact, they are mutually exclusive in any solution, since there is just one copy of Xi in A(Φ). Eventually, one may check that it is possible to produce the output goods {c1, .., cm} if and only if all the various selections encode a satisfying assignment to Φ. Thus, Φ is satisfiable ⇔A(Φ) has a solution.

Actually, observe that A(Φ) belongs to C(1, 2, 1, 1, 3, 2), but not necessarily to C(1, 2, 1, 1, 2, 2) since a clause cj may contain three variables Xi,Xi′ , and Xi′′ . In order to face this case, we may add one further good ¯ cj, and replace the two transformations 〈{ci′ j }, {cj}〉 and 〈{ci′′ j }, {cj}〉 with the transformations: 〈{ci′ j }, {¯ cj}〉, 〈{ci′′ j }, {¯ cj}〉, and 〈{¯ cj }, {cj }〉. Clearly, the resulting auction has input degree equals to 2, while keeping unchanged the values of all the other parameters and the properties of the reduction. ✷

The other hardness results can be shown with a similar line of reasoning, provided the modifications on the auction A(Φ) that are graphically illustrated in Figure 2. Thus, the following holds, whose proof is omitted due to space constraints.

Theorem 3.6 FEASIBILITY is NP-complete, even under atomic bids and restricted on the classes C(1, 1, 1, 2, 2, 2), C(1, 1, 2, 1, 2, 2), and C(2, 1, 1, 1, 2, 2).

3.3 Results for the XOR-language

We now conclude the analysis by considering the case of XOR-conditions. Firstly, we observe that the proof of Theorem 3.2 can easily be adapted to deal with XOR-conditions, based on the fact that executing necessary transformations is mandatory as to solve the instance at hand; thus, if some necessary transformation cannot be executed because of some given XOR-condition (whose check is a source of additional complexity), then no solution exists.

2 Given our interest in the FEASIBILITY problem, we shall omit the indication of the payments in the various transformations.

Theorem 3.7 Let A = 〈G, T , Uin, Uout〉[L,XOR] be a MMUCA such that A ∈ C(∞,∞,∞,∞, 1,∞). Then, FEASIBILITY can be solved in time O(|T |2 × (|G| × logΔ+ |T |)).

Interestingly, the above tractability cannot be extended on the dual class C(∞,∞,∞,∞,∞, 1), since XOR conditions may be used to simulate scenarios where every type of good is required as input by more than one transformation.

Theorem 3.8 FEASIBILITY is NP-complete under XORconditions, even restricted on the class C(1, 1, 1, 1, 2, 1).

4 Structural Restrictions (Alone) Do Not Help

Many NP-hard problems can efficiently be solved when restricted to instances that can be modeled via (nearly)acyclic graphs. Thus, one may expect that these structural restrictions are also beneficial to isolate tractable MMUCAs. This is next investigated, by modeling interactions among bidders in an instance A via the transformations and the goods graph of A, denoted by TG(A) and GG(A), respectively-see Section 1. In addition, we shall consider their undirected versions, denoted by TG(A) and GG(A), respectively.

Beforehand, note that some of the qualitative restrictions studied in Section 3 induce structural restrictions on the transformations and goods graphs. Indeed, it is easily checked that unitary input (or output) degree instances are guaranteed to be associated with graphs that are basically acyclic-cycles there cannot contribute to producing goods. In fact, these cases are tractable (cf. Theorem 3.2 and Theorem 3.3). In general, however, acyclicity does not guarantee tractability. Indeed, the undirected transformations graph associated with the MMUCA instance built in the proof of Theorem 3.5 is acyclic, while still encoding an NP-complete problem. Thus:

Corollary 4.1 FEASIBILITY is NP-complete, even restricted on the class {A | TG(A) is acyclic} (and, hence, on the class {A | TG(A) is acyclic}) and under atomic bids.

In addition, the (directed) goods graph in the proof of Theorem 3.5 is also acyclic. Thus:

Corollary 4.2 FEASIBILITY is NP-complete, even restricted on the class {A | GG(A) is acyclic} and under atomic bids.

In particular, the above result is rather interesting in the light that instances with (directed) acyclic goods graphs correspond to natural transformation processes (cf. [Ottens and Endriss, 2008]). Thus, transformation processes emerge to be as hard as arbitrary trades and exchanges of goods.

In order to complete our analysis, we shall show that FEASIBILITY remains NP-hard on nearly-acyclic undirected goods graphs-formally, graphs of bounded treewidth. To this end, we recall here that a tree decomposition of a graph G = (V,E) is a pair 〈T, χ〉, where T = (N, F) is a tree, and χ is a labeling function assigning to each vertex p ∈ N a set of vertices χ(p) ⊆ V , such that the following conditions are satisfied: (1) for each node 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); and, (3) for each node b of G, the set {p ∈ N | b ∈ χ(p)} induces a connected subtree.

The width of 〈T, χ〉 is the number maxp∈N(|χ(p)| - 1). The treewidth of G, denoted by tw(G), is the minimumwidth over all its tree decompositions. It is well-known that an undirected graph G is acyclic if and only if tw(G) = 1.

Theorem 4.3 FEASIBILITY is NP-complete, even restricted on the class {A | tw(GG(A)) = 2} and under atomic bids.

Proof. (Sketch). Deciding whether there is a way to partition a multi-set S = {s1, s2, ..., sn} of integers into two multi-sets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2 is a well-known NP-hard problem.

Let m = ∑ni=1 si. Consider the auction A(S) = 〈G, T , Uin, Uout〉 such that: G = {g1, ..., gn, c1, c2}, Uin = {g1, ..., gn}, Uout = ⋃ m2 i=1 {c1} ∪ ⋃ m2 i=1{c2}, and T = ⋃ni=1 Ti. In particular, for each number si, the set Ti consists of the transformations: 〈{gi}, ⋃si i=1{c1}〉, 〈{gi}, ⋃si {c2}〉.

i=1

Since the transformation 〈{gi}, ⋃si i=1 {c1}〉 is alternative to 〈{gi}, ⋃si i=1{c2}〉 (where c1 and c2 are meant to encode S1 and S2, respectively), a partition of S exists ⇔A(S) has a solution. Eventually, we also note that the undirected goods graph associated with A(S) has treewidth equals to 2, which is witnessed by the tree decomposition T whose root r is such that χ(r) = {c1, c2}, and where for each good si, exactly one (leaf) child ℓi of r is in T with χ(ℓi) = {c1, c2, gi}. ✷

We leave the section by noticing that XOR-conditions may be used to state in the above proof that 〈{gi}, ⋃si i=1{c1}〉 is alternative to 〈{g′i}, ⋃si i=1 {c2}〉, where g′i is a copy of gi also available in input. Thus, one may easily derive the following:

Theorem 4.4 FEASIBILITY is NP-complete under XORconditions, even on the class {A | GG(A) is acyclic}.

5 Tractable WINNER-DETERMINATION

When turning to WINNER-DETERMINATION, we firstly observe that this problem inherits all the hardness results derived for FEASIBILITY. In addition, computing the optimal solution remains hard even if there is no transformation producing (or requiring) goods. In fact, the result below follows by adapting classical results on combinatorial auctions (see, e.g., [Lehmann et al., 2006]).

Theorem 5.1 WINNER-DETERMINATION is NP-hard, even restricted on the classes {A | in-deg(A) = 0} and {A | out-deg(A) = 0}, and under atomic bids.

The reason for the above intractability is that interactions among bidders may be too complex to be analyzed. To bound these interactions, we next consider a structural restriction based on a hypergraph encoding, which is more general than graph (near)acyclicity. In particular, we define the auction hypergraph AH(A) = (T ,H) as the hypergraph whose nodes are in one-to-one correspondence with the transformations in A, and where for each good g ∈ G, there is a hyperedge in H such that: hg = {〈I,O, p〉 ∈ T | I (g) + O(g) > 0}- in the following, for any hypergraph H, the set of its nodes (resp., edges) is denoted by N(H) (resp., E(H)). On such hypergraphs, the idea is to consider the hypertree decomposition [Gottlob et al., 2002] approach to isolate nearly acyclic auction hypergraphs.

Formally, a hypertree for a hypergraph H is a triple 〈T, χ, λ〉, where T = (N, E) is a rooted tree, and χ and λ are labeling functions, which associate each vertex p ∈ N with two sets χ(p) ⊆ N(H) and λ(p) ⊆ E(H). For a set of edges H ⊆ E(H), N(H) denotes the set ⋃h∈H 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 5.2 (cf. [Gottlob et al., 2002]) A (complete) hypertree decomposition of H is a hypertree HD = 〈T, χ, λ〉 for H satisfying the following conditions:

1. for each edge h ∈ E(H), there exists a leaf p ∈ vertices(T ) such that h ⊆ χ(p), and h ∈ λ(p);
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.

Computing a k-width decomposition of H (or stating that it does not exist) is feasible in O(|E(H)|2k × |N(H)|2 ). ✷

Actually, we have noticed in Section 4 that structural restrictions does not suffice to single out tractable classes of instances. In particular, acyclic instances may still require complex reasoning tasks on the transformations that have to be activated, because of the large number of goods in the scenario. Thus, in addition to considering (generalizations of) acyclicity, we must also define a bound the number of transformations producing a given good g (as to easily control its availability in any solution); plus either a bound on the maximum quantity of g that can be produced over solutions, or a bound on the number of transformations requiring g (as to easily control the consumption of g). This is formalized via the measure of intricacy of an instance A = 〈G, T , Uin, Uout〉, that is: maxg∈G(|{〈I,O, p〉 | O(g) > 0}|+ min{Uin(g) + ∑〈I ,O,p〉∈T O(g), |{〈I,O, p〉 | I (g) > 0}|}).

Putting It All Together. Let C ∗ (h, k) denote the class of instances whose intricacy is bounded by h and whose auction hypergraphs have hypertree width bounded by k.

We next show that WINNER-DETERMINATION is tractable on C ∗ (h, k), by means of the algorithm SolveMMUCAh,k shown in Figure 3. In the algorithm, any sequence σ is encoded as a set of pairs of the form (t, i) where t ∈ T and i is the step where t is executed, by assuming w.l.o.g. that transformations can be applied in parallel (i = 0 means that t is not applied in σ). Moreover, we say that σ is legal over a good g ∈ G if Mi-1(g) ≥ Ii(g), for each (〈I,O, p〉, i) ∈ σ with i > 0, and if Mk(g) ≥ Uout(g) where k is the last step in σ. And, finally, for each σ′ ⊆ σ, we define pay(σ′ ) = ∑(〈I ,O,p〉,i)∈σ′ ,i>0 p.

The algorithm receives a k-width hypertree decomposition HD = 〈T=(N,E), χ, λ〉 of AH(A). Firstly, for each vertex v ∈ N, it computes the set Hv of all the v-solutions, where {(t, i) | (t, i) ∈ σ ∧ t ∈ χ(v)} is a v-solution if there is a sequence σ that is legal over each good g such that hg ∈ λ(v).

Input: A k-width decomposition HD = 〈T =(N, E), χ, λ〉 of AH(A); Output: An optimal solution to WINNER-DETERMINATION on A; var σ∗ : optimal solution; ℓvσv : real number, for each v-solution σv ∈ Hv; σσv,c : c-solution in Hc, for each v-solution σv and (v, c) ∈ E; ------------------------------- Hv := the set of all the v-solutions, for each v ∈ N; Done := the set of all the leaves of T; while ∃v ∈ T \ Done such that {c | c is child of v} ⊆ Done do Hv := Hv - {σv | ∃(v, c) ∈ E∧ ̸ ∃σc ∈ Hc s.t. σv ≈ σc}; for each σv ∈ Hv do ℓvσv := pay(σv); for each (v, c) ∈ E do ¯σc := argmaxσc∈Hc|σv≈ σc "ℓcσc - pay(σc ∩ σv)" ; σσv,c := ¯σc; ℓvσv := ℓvσv + ℓc¯σc - pay(¯σc ∩ σv); end for end for Done := Done ∪ {v}; end while let r be the root of T; if Hr = ∅ then HALT answering 'no solution'; ¯σr := argmaxσr∈Hr ℓrσr , and σ∗ := ¯σr ; T opDown(r, σr ); return σ∗ ; ------------------------------- Procedure TopDown(v : vertex of N, ¯σv ∈ Hv); begin for each c ∈ N s.t. (v, c) ∈ E do ¯σc := σ¯σv,c; σ∗ := σ∗ ∪ ¯σc; TopDown(c, ¯σc); end for end;

Then, it manipulates v-solutions, at each vertex v, by looking for their "conformance" with c-solutions in Hc, for each child c of v in T , where σv ∈ Hv conforms with σc ∈ Hc (σv ≈ σc) if ∀t ∈ χ(v) ∩ χ(c), (t, i) ∈ σv ⇔ (t, i) ∈ σc.

In particular, in the first phase, vertices of T are processed from the leaves to the root r as to filter v-solutions that do not conformwith any solution at some child of v, and as to update the weight ℓvσv of each remaining v-solution σv. Intuitively, ℓvσv stores the maximum revenue over all potential solutions restricted on transformations in χ(Tv). Indeed, if v is a leaf, then ℓvσv = pay(σv). Otherwise, for each child c of v in T , ℓvσv is incremented by the maximum of ℓcσc - pay (σc ∩ σv) over all c-solutions conforming with σv. The c-solution over which the maximum is achieved is stored in σσv,c. In a second phase, T is processed starting from the root: The solution σ∗ is defined as the r-solution in Hr with the maximum payoff, and procedure TopDown extends σ∗ , at each vertex v, with the c-solution σσv,c for each (v, c) ∈ E.

As to analyze SolveMMUCAh,k, the crucial observation is that for each vertex v, |Hv| ≤ (|T | + 1)2×h×k .

Theorem 5.3 WINNER-DETERMINATION can be solved in O(|G|2k × (|T | + 1)4×h×k+2 × log Δ) under OR-conditions and on C ∗ (h, k)-with the uniform cost model for payoffs.

As a final remark, observe that SolveMMUCAh,k can be used even under XOR-conditions, after encoding them in terms of transformations. For instance, if t1 and t2 are alternative because of a XOR-condition, we may simply add one good g1,2 and force t1 and t2 to require g1,2 for their application. Moreover, the restriction of SolveMMUCAh,k on h = 1 can be used to solve the tractable class of CA instances (where one item of each type is available at most, and no good can be produced) identified in [Gottlob and Greco, 2007].

6 Conclusion

The problem of identifying tractability islands for MMUCAs has been faced, by complementing tractability results that were derived for classical CAs. Our results paves the way for the implementation of solution algorithms for arbitrary MMUCA instances, which may take advantage of structural and qualitative properties of some of their portions. In addition, interesting avenues of further research are to chart the tractability frontier under lack of free disposal (i.e., when the auctioneer wants to end up exactly with the goods in Uout), to consider more involved kinds of bidding languages, for instance where bidders preferences are taken into account, and to look for approximability results for the various NP-hard scenarios we have singled out, in the spirit of the thorough analysis recently carried for combinatorial exchange problems [Babaioff et al., 2008].