Generalized Value Decomposition and Structured  Multiattribute Auctions  Yagil Engel and Michael P. Wellman  University of Michigan, Computer Science & Engineering  2260 Hayward St, Ann Arbor, MI 48109-2121, USA  {yagil,wellman}@umich.edu  ABSTRACT  Multiattribute auction mechanisms generally either remain   agnostic about traders" preferences, or presume highly restrictive forms,  such as full additivity. Real preferences often exhibit   dependencies among attributes, yet may possess some structure that can be  usefully exploited to streamline communication and simplify   operation of a multiattribute auction. We develop such a structure  using the theory of measurable value functions, a cardinal utility  representation based on an underlying order over preference   differences. A set of local conditional independence relations over  such differences supports a generalized additive preference   representation, which decomposes utility across overlapping clusters of  related attributes. We introduce an iterative auction mechanism that  maintains prices on local clusters of attributes rather than the full  space of joint configurations. When traders" preferences are   consistent with the auction"s generalized additive structure, the   mechanism produces approximately optimal allocations, at approximate  VCG prices.  Categories and Subject Descriptors: J.4 [Computer   Applications]: Social and Behavioral Sciences-Economics    1. INTRODUCTION  Multiattribute trading mechanisms extend traditional, price-only  mechanisms by facilitating the negotiation over a set of predefined  attributes representing various non-price aspects of the deal. Rather  than negotiating over a fully defined good or service, a   multiattribute mechanism delays commitment to specific configurations  until the most promising candidates are identified. For example,  a procurement department of a company may use a multiattribute  auction to select a supplier of hard drives. Supplier offers may be  evaluated not only over the price they offer, but also over various  qualitative attributes such as volume, RPM, access time, latency,  transfer rate, and so on. In addition, suppliers may offer different  contract conditions such as warranty, delivery time, and service.  In order to account for traders" preferences, the auction   mechanism must extract evaluative information over a complex domain  of multidimensional configurations. Constructing and   communicating a complete preference specification can be a severe burden  for even a moderate number of attributes, therefore practical   multiattribute auctions must either accommodate partial specifications,  or support compact expression of preferences assuming some   simplified form. By far the most popular multiattribute form to adopt  is the simplest: an additive representation where overall value is a  linear combination of values associated with each attribute. For   example, several recent proposals for iterative multiattribute auctions  [2, 3, 8, 19] require additive preference representations.  Such additivity reduces the complexity of preference   specification exponentially (compared to the general discrete case), but   precludes expression of any interdependencies among the attributes. In  practice, however, interdependencies among natural attributes are  quite common. For example, the buyer may exhibit complementary  preferences for size and access time (since the performance effect  is more salient if much data is involved), or may view a strong   warranty as a good substitute for high reliability ratings. Similarly, the  seller"s production characteristics (such as increasing access time  is harder for larger hard drives) can easily violate additivity. In  such cases an additive value function may not be able to provide  even a reasonable approximation of real preferences.  On the other hand, fully general models are intractable, and it  is reasonable to expect multiattribute preferences to exhibit some  structure. Our goal, therefore, is to identify the subtler yet more  widely applicable structured representations, and exploit these   properties of preferences in trading mechanisms.  We propose an iterative auction mechanism based on just such a  flexible preference structure. Our approach is inspired by the   design of an iterative multiattribute procurement auction for additive  preferences, due to Parkes and Kalagnanam (PK) [19]. PK   propose two types of iterative auctions: the first (NLD) makes no   assumptions about traders" preferences, and lets sellers bid on the full  multidimensional attribute space. Because NLD maintains an   exponential price structure, it is suitable only for small domains. The  other auction (AD) assumes additive buyer valuation and seller cost  functions. It collects sell bids per attribute level and for a single   discount term. The price of a configuration is defined as the sum of  the prices of the chosen attribute levels minus the discount.  The auction we propose also supports compact price spaces,   albeit for levels of clusters of attributes rather than singletons. We  employ a preference decomposition based on generalized additive  independence (GAI), a model flexible enough to accommodate   interdependencies to the exact degree of accuracy desired, yet   providing a compact functional form to the extent that interdependence  can be limited. Given its roots in multiattribute utility theory [13],  227  the GAI condition is defined with respect to the expected utility  function. To apply it for modeling values for certain outcomes,  therefore, requires a reinterpretation for preference under certainty.  To this end, we exploit the fact that auction outcomes are associated  with continuous prices, which provide a natural scale for assessing  magnitude of preference.  We first lay out a representation framework for preferences that  captures, in addition to simple orderings among attribute   configuration values, the difference in the willingness to pay (wtp) for each.  That is, we should be able not only to compare outcomes but also  decide whether the difference in quality is worth a given difference  in price. Next, we build a direct, formally justified link from   preference statements over priced outcomes to a generalized additive  decomposition of the wtp function. After laying out this   infrastructure, we employ this representation tool for the development of a  multiattribute iterative auction mechanism that allows traders to   express their complex preferences in GAI format. We then study the  auction"s allocational, computational, and practical properties.  In Section 2 we present essential background on our   representation framework, the measurable value function (MVF). Section 3  develops new multiattribute structures for MVF, supporting   generalized additive decompositions. Next, we show the applicability of  the theoretical framework to preferences in trading. The rest of the  paper is devoted to the proposed auction mechanism.  2. MULTIATTRIBUTE PREFERENCES  As mentioned, most tools facilitating expression of multiattribute  value for trading applications assume that agents" preferences can  be represented in an additive form. By way of background, we start  by introducing the formal prerequisites justifying the additive   representation, as provided by multiattribute utility theory. We then  present the generalized additive form, and develop the formal   underpinnings for measurable value needed to extend this model to  the case of choice under certainty.  2.1 Preferential Independence  Let Θ denote the space of possible outcomes, with a   preference relation (weak total order) over Θ. Let A = {a0, . . . , am}  be a set of attributes describing Θ. Capital letters denote subsets  of variables, small letters (with or without numeric subscripts)   denote specific variables, and ¯X denotes the complement of X with  respect to A. We indicate specific variable assignments with prime  signs or superscripts. To represent an instantiation of subsets X, Y  at the same time we use a sequence of instantiation symbols, as in  X Y .  DEFINITION 1. A set of attributes Y ⊂ A is preferentially   independent (PI) of its complement Z = A \ Y if the conditional  preference order over Y given a fixed level Z0  of Z is the same  regardless of the choice of Z0  .  In other words, the preference order over the projection of A on the  attributes in Y is the same for any instantiation of the attributes in  Z.  DEFINITION 2. A = {a1, . . . , am} is mutually preferentially  independent (MPI) if any subset of A is preferentially independent  of its complement.  The preference relation when no uncertainty is modeled is   usually represented by a value function v [17]. The following   fundamental result greatly simplifies the value function representation.  THEOREM 1 ([9]). A preference order over set of attributes  A has an additive value function representation  v(a1, . . . , am) =  mX  i=1  vi(ai)  iff A is mutually preferential independent.  Essentially, the additive forms used in trading mechanisms assume  mutual preferential independence over the full set of attributes,   including the money attribute. Intuitively that means that willingness  to pay for value of an attribute or attributes cannot be affected by  the value of other attributes.  A cardinal value function representing an ordering over certain  outcomes need not in general coincide with the cardinal utility  function that represents preference over lotteries or expected utility  (EU). Nevertheless, EU functions may possess structural   properties analogous to that for value functions, such as additive   decomposition. Since the present work does not involve decisions under  uncertainty, we do not provide a full exposition of the EU concept.  However we do make frequent reference to the following additive  independence relations.  DEFINITION 3. Let X, Y, Z be a partition of the set of attributes  A. X and Y are conditionally additive independent given Z,   denoted as CAI(X, Y | Z), if preferences over lotteries on A depend  only on their marginal conditional probability distributions over X  and Y .  DEFINITION 4. Let I1, . . . , Ig ⊆ A such that  Sg  i=1 Ii = A.  I1, . . . , Ig are called generalized additive independent (GAI) if   preferences over lotteries on A depend only on their marginal   distributions over I1, . . . , Ig.  An (expected) utility function u(·) can be decomposed additively  according to its (possibly overlapping) GAI sub-configurations.  THEOREM 2 ([13]). Let I1, . . . , Ig be GAI. Then there exist  functions f1, . . . , fg such that  u(a1, . . . , am) =  g  X  r=1  fr(Ir). (1)  What is now known as the GAI condition was originally   introduced by Fishburn [13] for EU, and was named GAI and brought to  the attention of AI researchers by Bacchus and Grove [1].   Graphical models and elicitation procedures for GAI decomposable utility  were developed for EU [4, 14, 6], for a cardinal representation of  the ordinal value function [15], and for an ordinal preference   relations corresponding to a TCP-net structure by Brafman et al. [5].  Apart from the work on GAI in the context of preference handling  that were discussed above, GAI have been recently used in the   context of mechanism design by Hyafil and Boutilier [16], as an aid in  direct revelation mechanisms.  As shown by Bacchus and Grove [1], GAI structure can be   identified based on a set of CAI conditions, which are much easier to  detect and verify. In general, utility functions may exhibit GAI  structure not based on CAI. However, to date all proposals for   reasoning and eliciting utility in GAI form take advantage of the GAI  structure primarily to the extent that it represents a collection of  CAI conditions. For example, GAI trees [14] employ triangulation  of the CAI map, and Braziunas and Boutilier"s [6] conditional set  Cj of a set Ij corresponds to the CAI separating set of Ij.  Since the CAI condition is also defined based on preferences  over lotteries, we cannot apply Bacchus and Grove"s result   without first establishing an alternative framework based on priced   outcomes. We develop such a framework using the theory of   measurable value functions, ultimately producing a GAI decomposition  228  (Eq. 1) of the wtp function. Readers interested primarily in the  multiattribute auction and willing to grant the well-foundedness of  the preference structure may skip down to Section 5.  2.2 Measurable Value Functions  Trading decisions represent a special case of decisions under   certainty, where choices involve multiattribute outcomes and   corresponding monetary payments. In such problems, the key decision  often hinges on relative valuations of price differences compared  to differences in alternative configurations of goods and services.  Theoretically, price can be treated as just another attribute,   however, such an approach fails to exploit the special character of the  money dimension, and can significantly add to complexity due to  the inherent continuity and typical wide range of possible monetary  outcome values.  We build on the fundamental work of Dyer and Sarin [10, 11] on  measurable value functions (MVFs). As we show below, wtp   functions in a quasi-linear setting can be interpreted as MVFs. However  we first present the MVF framework in a more generic way, where  the measurement is not necessarily monetary. We present the   essential definitions and refer to Dyer and Sarin for more detailed  background and axiomatic treatment. The key concept is that of  preference difference. Let θ1  , θ2  , ϑ1  , ϑ2  ∈ Θ such that θ1  θ2  and ϑ1  ϑ2  . [θ2  , θ1  ] denotes the preference difference between  θ2  and θ1  , interpreted as the strength, or degree, to which θ2  is   preferred over θ1  . Let ∗  denote a preference order over Θ × Θ. We  interpret the statement  [θ2  , θ1  ] ∗  [ϑ2  , ϑ1  ]  as the preference of ϑ2  over ϑ1  is at least as strong as the   preference of θ2  over θ1  . We use the symbol ∼∗  to represent equality of  preference differences.  DEFINITION 5. u : D → is a measurable value function  (MVF) wrt ∗  if for any θ1  , θ2  , ϑ1  , ϑ2  ∈ D,  [θ2  , θ1  ] ∗  [ϑ2  , ϑ1  ] ⇔  u(θ2  ) − u(θ1  ) ≤ u(ϑ2  ) − u(ϑ1  ).  Note that an MVF can also be used as a value function representing  , since [θ , θ] ∗  [θ , θ] iff θ θ .  DEFINITION 6 ([11]). Attribute set X ⊂ A is called   difference independent of ¯X if for any two assignments X1 ¯X X2 ¯X ,  [X1 ¯X , X2 ¯X ] ∼∗  [X1 ¯X , X2 ¯X ]  for any assignment ¯X .  Or, in words, the preference differences on assignments to X given  a fixed level of ¯X do not depend on the particular level chosen for  ¯X.  As with additive independence for EU, this condition is stronger  than preferential independence of X. Also analogously to EU,  mutual preferential independence combined with other conditions  leads to additive decomposition of the MVF. Moreover, Dyer and  Sarin [11] have defined analogs of utility independence [17] for  MVF, and worked out a parallel set of decomposition results.  3. ADVANCED MVF STRUCTURES  3.1 Conditional Difference Independence  Our first step is to generalize Definition 6 to a conditional   version.  DEFINITION 7. Let X, Y, Z be a partition of the set of attributes  A. X is conditionally difference independent of Y given Z,   denoted as CDI(X, Y | Z), if  ∀ instantiations ˆZ, X1  , X2  , Y 1  , Y 2  [X1  Y 1 ˆZ, X2  Y 1 ˆZ] ∼ [X1  Y 2 ˆZ, X2  Y 2 ˆZ].  Since the conditional set is always the complement, we sometimes  leave it implicit, using the abbreviated notation CDI(X, Y ).  CDI leads to a decomposition similar to that obtained from CAI  [17].  LEMMA 3. Let u(A) be an MVF representing preference   differences. Then CDI(X, Y | Z) iff  u(A) = u(X0  , Y, Z) + u(X, Y 0  , Z) − u(X0  , Y 0  , Z).  To complete the analogy with CAI, we generalize Lemma 3 as  follows.  PROPOSITION 4. CDI(X, Y | Z) iff there exist functions  ψ1(X, Z) and ψ2(Y, Z), such that  u(X, Y, Z) = ψ1(X, Z) + ψ2(Y, Z). (2)  An immediate result of Proposition 4 is that CDI is a symmetric  relation.  The conditional independence condition is much more   applicable than the unconditional one. For example, if attributes a ∈ X  and b /∈ X are complements or substitutes, X cannot be difference  independent of ¯X. However, X \ {a} may still be CDI of ¯X given  a.  3.2 GAI Structure for MVF  A single CDI condition decomposes the value function into two  parts. We seek a finer-grain global decomposition of the utility  function, similar to that obtained from mutual preferential   independence. For this purpose we are now ready to employ the results  of Bacchus and Grove [1], who establish that the CAI condition  has a perfect map [20]; that is, there exists a graph whose nodes  correspond to the set A, and its node separation reflects exactly the  complete set of CAI conditions on A. Moreover, they show that the  utility function decomposes over the set of maximal cliques of the  perfect map. Their proofs can be easily adapted to CDI, since they  only rely on the decomposition property of CAI that is also implied  by CDI according to Proposition 4.  THEOREM 5. Let G = (A, E) be a perfect map for the CDI  conditions on A. Then  u(A) =  g  X  r=1  fr(Ir), (3)  where I1, . . . , Ig are (overlapping) subsets of A, each   corresponding to a maximal clique of G.  Given Theorem 5, we can now identify an MVF GAI structure  from a collection of CDI conditions. The CDI conditions, in turn,  are particularly intuitive to detect when the preference differences  carry a direct interpretation, as in the case with monetary   differences discussed below. Moreover, the assumption or detection of  CDI conditions can be performed incrementally, until the MVF is  decomposed to a reasonable dimension. This is in contrast with the  fully additive decomposition of MVF that requires mutual   preferential independence [11].  Theorem 5 defines a decomposition structure, but to represent  the actual MVF we need to specify the functions over the cliques.  229  The next theorem establishes that the functional constituents of  MVF are the same as those for GAI decompositions as defined by  Fishburn [13] for EU. We adopt the following conventional   notation. Let (a0  1, . . . , a0  m) be a predefined vector called the reference  outcome. For any I ⊆ A, the function u([I]) stands for the   projection of u(A) to I where the rest of the attributes are fixed at their  reference levels.  THEOREM 6. Let G = (A, E) be a perfect map for the CDI  condition on A, and {I1, . . . , Ig} a set of maximal cliques as   defined in Theorem 5. Then the functional decomposition from that  theorem can be defined as  f1 = u([I1]), and for r = 2, . . . , g (4)  fr = u([Ir]) +  r−1X  k=1  (−1)k  X  1≤i1<···<ik<r  u([  k\  s=1  Iis ∩ Ir])  The proof directly shows that if graph G = (A, E) is a perfect  map of CDI, u(A) decomposes to a sum over the functions defined  in (4).1  Thus this proof does not rely on the decomposition result  of Theorem 5, only on the existence of the perfect map.  To summarize, the results of this section generalize additive MVF  theory. In particular it justifies the application of methods recently  developed under the EU framework [1, 4, 14, 6] to representation  of value under certainty.  4. WILLINGNESS-TO-PAY AS AN MVF  4.1 Construction  In this section we apply measurable value to represent   differences of willingness to pay for outcomes. We assume that the agent  has a preference order over outcome space, represented by a set of  attributes A, and an attribute p representing monetary consequence.  Note that in evaluating a purchase decision, p would correspond to  the agent"s money holdings net of the transaction (i.e., wealth   after purchase), not the purchase price. An outcome in this space is  represented for example by (θ , p ), where θ is an instantiation of  A and p is a value of p. We further assume that preferences are  quasi-linear in p, that is there exists a value function of the form  v(A, p) = u(A) + L(p), where L is a positive linear function.2  The quasi-linear form immediately qualifies money as a   measure of preference differences, and establishes a monetary scale for  u(A).  DEFINITION 8. Let v(A, p) = u(A)+L(p) represent , where  p is the attribute representing money. We call u(A) a   willingnessto-pay (wtp) function.  Note that wtp may also refer to the seller"s willingness to accept  function. The wtp u(A) is a cardinal function, unique up to a   positive linear transformation. Since  (θ1, p ) (θ2, p ) ⇔ u(θ1) − u(θ2) ≤ L(p − p ),  (where θ1, θ1 ∈ Θ, the domain of A) the wtp function can be used  to choose among priced outcomes.  1  This proof and most other proofs in this paper are omitted for  space consideration, and are available in an online appendix.  2  In many procurement applications, the deals in question are small  relative to the enterprises involved, so the quasi-linearity   assumption is warranted. This assumption can be relaxed to a condition  called corresponding tradeoffs [17], which does not require the  value over money to be linear. To simplify the presentation,   however, we maintain the stronger assumption.  Naturally, elicitation of wtp function is most intuitive when   using direct monetary values. In other words, we elicit a function in  which L(p) = p, so v(A, p) = u(A) + p. We define a reference  outcome (θ0  , p0  ), and assuming continuity of p, for any assignment  ˆθ there exists a ˆp such that (ˆθ, ˆp) ∼ (θ0  , p0  ). As v is normalized  such that v(θ0  , p0  ) = 0, ˆp is interpreted as the wtp for ˆθ, or the  reserve price of ˆθ.  PROPOSITION 7. The wtp function is an MVF over differences  in the reserve prices.  We note that the wtp function is used extensively in economics,  and that all the development in Section 3 could be performed   directly in terms of wtp, relying on quasi-linearity for preference  measurement, and without formalization using MVFs. This   formalization however aligns this work with the fundamental   difference independence theory by Dyer and Sarin.  In addition to facilitating the detection of GAI structure, the CDI  condition supports elicitation using local queries, similar to how  CAI is used by Braziunas and Boutilier [6]. We adopt their   definition of conditional set of Ir, noted here Sr, as the set of neighbors  of attributes in Ir not including the attributes of Ir. Clearly, Sr is  the separating set of Ir in the CDI map, hence CDI(Ir, Vr), where  Vr = A \ (Ir ∪ Sr). From the definition of CDI, for any V 1  r , V 2  r  we have:  u(I1  r S0  r V 1  r ) − u(I2  r S0  r V 1  r ) = u(I1  r S0  r V 2  r ) − u(I2  r S0  r V 2  r ).  Eliciting the wtp function therefore amounts to eliciting the   utility (wtp) of one full outcome (the reference outcome θ0  ), and then  obtaining the function over each maximal clique using monetary  differences between its possible assignments (technique known as  pricing out [17]), keeping the variables in the conditional set fixed.  These ceteris paribus elicitation queries are local in the sense that  the agent does not need to consider the values of the rest of the   attributes. Furthermore, in eliciting MVFs we can avoid the global  scaling step that is required for EU functions. Since the preference  differences are extracted with respect to specific amounts of the  attribute p, the utility is already scaled according to that external  measure. Hence, once the conditional utility functions u([Ij]) are  obtained, we can calculate u(A) according to (4).  This last step may require (in the worst case) computation of a  number of terms that is exponential in the number of max cliques.  In practice however we do not expect the intersection of the cliques  to go that deep; intersection of more than just a few max cliques  would normally be empty. To take advantage of that we can use the  search algorithm suggested by Braziunas and Boutilier [6], which  efficiently finds all the nonempty intersections for each clique.  4.2 Optimization  As shown, the wtp function can be used directly for pairwise  comparisons of priced outcomes. Another preference query often  treated in the literature is optimization, or choice of best outcome,  possibly under constraints.  Typical decisions about exchange of a good or service exhibit  what we call first-order preferential independence (FOPI), under  which most or all single attributes have a natural ordering of quality,  independent of the values of the rest.3  For example, when   choosing a PC we always prefer more memory, faster CPU, longer   warranty, and so on. Under FOPI, the unconstrained optimization of  3  This should not be mistaken with the highly demanding   condition of mutual preferential independence, that requires all tradeoffs  between attributes to be independent.  230  unpriced outcomes is trivial, hence we consider choice among   attribute points with prices. Since any outcome can be best given  enough monetary compensation, this problem is not well-defined  unless the combinations are constrained somehow.  A particularly interesting optimization problem arises in the   context of negotiation, where we consider the utility of both buyers and  sellers. The multiattribute matching problem (MMP) [12] is   concerned with finding an attribute point that maximizes the surplus of  a trade, or the difference between the utilities of the buyer and the  seller, ub(A) − us(A). GAI, as an additive decomposition, has the  property that if ub and us are in GAI form then ub(A)−us(A) is in  GAI form as well. We can therefore use combinatorial optimization  procedures for GAI decomposition, based on the well studied   variable elimination schemes (e.g., [15]) to find the best trading point.  Similarly, this optimization can be done to maximize surplus   between a trader"s utility function and a pricing system that assigns a  price to each level of each GAI element, and this way guide traders  to their optimal bidding points. In the rest of the paper we develop  a multiattribute procurement auction that builds on this idea.  5. GAI IN MULTIATTRIBUTE AUCTIONS  5.1 The Multiattribute Procurement Problem  In the procurement setting a single buyer wishes to procure a  single good, in some configuration θ ∈ Θ from one of the   candidate sellers s1, . . . , sn. The buyer has some private valuation  function (wtp) ub : Θ → R, and similarly each seller si has a  private valuation function (willingness-to-accept). For compliance  with the procurement literature we refer to seller si"s valuation as a  cost function, denoted by ci. The multiattribute allocation problem  (MAP) [19] is the welfare optimization problem in procurement  over a discrete domain, and it is defined as:  i∗  , θ∗  = arg max  i,θ  (ub(θ) − ci(θ)). (5)  To illustrate the need for a GAI price space we consider the case  of traders with non-additive preferences bidding in an additive price  space such as in PK"s auction AD. If the buyer"s preferences are  not additive, choosing preferred levels per attribute (as in auction  AD) admits undesired combinations and fails to guide the sellers to  the efficient configurations. Non-additive sellers face an exposure  problem, somewhat analogous to traders with complementary   preferences that participate in simultaneous auctions. A value a1  for  attribute a may be optimal given that the value of another attribute  b is b1  , and arbitrarily suboptimal given other values of b.   Therefore bidding a1  and b1  may result in a poor allocation if the seller  is outbid on b1  but left holding a1  .4  Instead of assuming full additivity, the auction designer can come  up with a GAI preference structure that captures the set of common  interdependencies between attributes. If traders could bid on   clusters of interdependent attributes, it would solve the problems   discussed above. For example, if a and b are interdependent (meaning  CDI(a, b) does not hold), we should be able to bid on the cluster  ab. If b in turn depends on c, we need another cluster bc. This  is still better than a general pricing structure that solicits bids for  the cluster abc. We stress that each trader may have a different set  of interdependencies, and therefore to be completely general the  4  If only the sellers are non-additive, the auction design could   potentially alleviate this problem by collecting a new set of bids each  round and forgetting bids from previous rounds, and also guiding  non-additive sellers to bid on only one level per attribute in order  to avoid undesired combinations.  ya  yb       yc  Z  Z  Z  (i)      ¨  ©a, b      ¨  ©b, c  (ii)  Figure 1: (i) CDI map for {a, b, c}, reflecting the single   condition CDI(a, c). (ii) The corresponding GAI network.  GAI structure needs to account for all.5  However, in practice many  domains have natural dependencies that are mutual to traders.  5.2 GAI Trees  Assume that preferences of all traders are reflected in a GAI  structure I1, . . . , Ig. We call each Ir a GAI element, and any   assignment to Ir a sub-configuration. We use θr to denote the   subconfiguration formed by projecting configuration θ to element Ir.  DEFINITION 9. Let α be an assignment to Ir and β an   assignment to Ir . The sub-configurations α and β are consistent if for  any attribute aj ∈ Ir ∩ Ir , α and β agree on the value of aj. A  collection ν of sub-configurations is consistent if all pairs α, β ∈ ν  are consistent. The collection is called a cover if it contains   exactly one sub-configuration αr corresponding to each element Ir,  r ∈ {1, . . . , g}.  Note that a consistent cover {α1, . . . , αg} represents a full   configuration, which we denote by (α1, . . . , αg).  A GAI network is a graph G whose nodes correspond to the GAI  elements I1, . . . , Ig, with an edge between Ir, Ir iff Ir ∩ Ir = ∅.  Equivalently, a GAI network is the clique graph of a CDI-map.  In order to justify the compact pricing structure we require that  for any set of optimal configurations (wrt a given utility function),  with a corresponding collection of sub-configurations γ, all   consistent covers in γ must be optimal configurations as well. To ensure  this (see Lemmas 8 and 10), we assume a GAI decomposition in  the form of a tree or a forest (the GAI tree). A tree structure can  be achieved for any set of CDI conditions by triangulation of the  CDI-map prior to construction of the clique graph (GAI networks  and GAI trees are defined by Gonzales and Perny [14], who also  provide a triangulation algorithm). Under GAI, the buyer"s value  function ub and sellers" cost functions ci can be decomposed as in  (1). We use fb,r and fi,r to denote the local functions of buyer and  sellers (respectively), according to (4).  For example, consider the procurement of a good with three  attributes, a, b, c. Each attribute"s domain has two values (e.g.,  {a1  , a2  } is the domain of A). Let the GAI structure be I1 =  {a, b}, I2 = {b, c}. Figure 1 shows the simple CDI map and  the corresponding GAI network, which is a GAI tree. Here,   subconfigurations are assignments of the form a1  b1  , a1  b2  , b1  c1  , and  so on. The set of sub-configurations {a1  b1  , b1  c1  } is a consistent  cover, corresponding to the configuration a1  b1  c1  . In contrast, the  set {a1  b1  , b2  c1  } is inconsistent.  5.3 The GAI Auction  We define an iterative multiattribute auction that maintains a GAI  pricing structure: that is, a price pt  (·) corresponding to each   subconfiguration of each GAI-tree element. The price of a   configuration θ at time t is defined as  pt  (θ) =  g  X  r=1  pt  (θr) − Δ.  5  We relax this requirement in Section 6.  231  Bidders submit sub-bids on sub-configurations and on an   additional global discount term Δ.6  Sub-bids are always submitted for  current prices, and need to be resubmitted at each round, therefore  they do not need to explicitly carry the price. The set of full bids  of a seller contains all consistent covers that can be generated from  that seller"s current set of sub-bids. The existence of a full bid over  a configuration θ represents the seller"s willingness to accept the  price pt  (θ) for supplying θ.  At the start of the auction, the buyer reports (to the auction, not  to sellers) her complete valuation in GAI form. The initial prices  of sub-configurations are set at some level above the buyer"s   valuations, that is, p1  (θr) > fb,r(θr) for all θr. The discount Δ is  initialized to zero. The auction has the dynamics of a descending  clock auction: at each round t, bids are collected for current prices  and then prices are reduced according to price rules. A seller is  considered active in a round if she submits at least one full bid. In  round t > 1, only sellers who where active in round t − 1 are   allowed to participate, and the auction terminates when no more than  a single seller is active. We denote the set of sub-bids submitted by  si by Bt  i , and the corresponding set of full bids is  Bt  i = {θ = (θ1, . . . , θg) ∈ Θ | ∀r.θr ∈ Bt  i }.  In our example, a seller could submit sub-bids on a set of   subconfigurations such as a1  b1  and b1  c1  , and that combines to a full  bid on a1  b1  c1  .  The auction proceeds in two phases. In the first phase (A), at  each round t the auction computes a set of preferred   sub-configurations Mt  . Section 5.4 shows how to define Mt  to ensure   convergence, and Section 5.5 shows how to efficiently compute it.  In phase A, the auction adjusts prices after each round, reducing  the price of every sub-configuration that has received a bid but is  not in the preferred set. Let be the prespecified price increment  parameter. Specifically, the phase A price change rule is applied to  all θr ∈  Sn  i=1 Bt  i \ Mt  :  pt+1  (θr) ← max(pt  (θr) −  g  , fb,r(θr)). [A]  The RHS maximum ensures that prices do not get reduced below  the buyer"s valuation in phase A.  Let Mt  denote the set of configurations that are consistent covers  in Mt  :  Mt  = {θ = (θ1, . . . , θg) ∈ Θ | ∀r.θr ∈ Mt  }  The auction switches to phase B when all active sellers have at  least one full bid in the buyer"s preferred set:  ∀i. Bt  i = ∅ ∨ Bt  i ∩ Mt  = ∅. [SWITCH]  Let T be the round at which [SWITCH] becomes true. At this  point, the auction selects the buyer-optimal full bid ηi for each  seller si.  ηi = arg max  θ∈BT  i  (ub(θ) − pT  (θ)). (6)  In phase B, si may bid only on ηi. The prices of sub-configurations  are fixed at pT  (·) during this phase. The only adjustment in phase B  is to Δ, which is increased in every round by . The auction   terminates when at most one seller (if exactly one, designate it sˆi) is  active. There are four distinct cases:  1. All sellers drop out in phase A (i.e., before rule [SWITCH]  holds). The auction returns with no allocation.  6  The discount term could be replaced with a uniform price   reduction across all sub-configurations.  2. All active sellers drop out in the same round in phase B. The  auction selects the best seller (sˆi) from the preceding round,  and applies the applicable case below.  3. The auction terminates in phase B with a final price above  buyer"s valuation, pT  (ηˆi) − Δ > ub(ηˆi). The auction offers  the winner sˆi an opportunity to supply ηˆi at price ub(ηˆi).  4. The auction terminates in phase B with a final price pT  (ηˆi)−  Δ ≤ ub(ηˆi). This is the ideal situation, where the auction  allocates the chosen configuration and seller at this resulting  price.  The overall auction is described by high-level pseudocode in   Algorithm 1. As explained in Section 5.4, the role of phase A is  to guide the traders to their efficient configurations. Phase B is a  one-dimensional competition over the surplus that remaining seller  candidates can provide to the buyer. In Section 5.5 we discuss the  computational tasks associated with the auction, and Section 5.6  provides a detailed example.  Algorithm 1 GAI-based multiattribute auction  collect a reported valuation, ˆv from the buyer  set high initial prices, p1  (θr) on each level θr, and set Δ = 0  while not [SWITCH] do  collect sub-bids from sellers  compute Mt  apply price change by [A]  end while  compute ηi  while more than one active seller do  increase Δ by  collect bids on (ηi, Δ) from sellers  end while  implement allocation and payment to winning seller  5.4 Economic Analysis  When the optimal solution to MAP (5) provides negative   welfare and sellers do not bid below their cost, the auction   terminates in phase A, no trade occurs and the auction is trivially   efficient. We therefore assume throughout the analysis that the optimal  (seller,configuration) pair provides non-negative welfare.  The buyer profit from a configuration θ is defined as7  πb(θ) = ub(θ) − p(θ)  and similarly πi(θ) = p(θ) − ci(θ) is the profit of si. In   addition, for μ ⊆ {1, . . . , g} we denote the corresponding set of   subconfigurations by θμ, and define the profit from a configuration θ  over the subset μ as  πb(θμ) =  X  r∈μ  (fb,r(θr) − p(θr)).  πi(θμ) is defined similarly for si. Crucially, for any μ and its   complement ¯μ and for any trader τ,  πτ (θ) = πτ (θμ) + πτ (θ¯μ).  The function σi : Θ → R represents the welfare, or surplus   function ub(·) − ci(·). For any price system p,  σi(θ) = πb(θ) + πi(θ).  7  We drop the t superscript in generic statements involving price  and profit functions, understanding that all usage is with respect to  the (currently) applicable prices.  232  Since we do not assume anything about the buyer"s strategy, the  analysis refers to profit and surplus with respect to the face value  of the buyer"s report. The functions πi and σi refer to the true cost  functions of si.  DEFINITION 10. A seller is called Straightforward Bidder (SB)  if at each round t she bids on Bt  i as follows: if maxθ∈Θ πt  i (θ) < 0,  then Bt  i = ∅. Otherwise let  Ωt  i ⊆ arg max  θ∈Θ  πt  i (θ)  Bt  i = {θr | θ ∈ Ωt  i, r ∈ {1, . . . , g}}.  Intuitively, an SB seller follows a myopic best response strategy  (MBR), meaning they bid myopically rather than strategically by  optimizing their profit with respect to current prices. To   calculate Bt  i sellers need to optimize their current profit function, as   discussed in Section 4.2.  The following lemma bridges the apparent gap between the   compact pricing and bid structure and the global optimization performed  by the traders.  LEMMA 8. Let Ψ be a set of configurations, all maximizing  profit for a trader τ (seller or buyer) at the relevant prices. Let  Φ = {θr | θ ∈ Ψ, r ∈ {1, . . . , g}. Then any consistent cover in Φ  is also a profit-maximizing configuration for τ.  Proof sketch (full proof in the online appendix): A source of an   element θr is a configuration ˜θ ∈ Ψ from which it originated   (meaning, ˜θr = θr). Starting from the supposedly suboptimal cover θ1  ,  we build a series of covers θ1  , . . . , θL  . At each θj  we flip the value  of a set of sub-configurations μj corresponding to a subtree, with  the sub-configurations of the configuration ˆθj  ∈ Ψ which is the  source of the parent γj of μj . That ensures that all elements in  μj ∪ {γj} have a mutual source ˆθj  . We show that all θj  are   consistent and that they must all be suboptimal as well, and since all  elements of θL  have a mutual source, meaning θL  = ˆθL  ∈ Ψ, it  contradicts optimality of Ψ.  COROLLARY 9. For SB seller si,  ∀t, ∀θ ∈ Bt  i , πt  i (θ ) = max  θ∈Θ  πt  i (θ).  Next we consider combinations of configurations that are only  within some δ of optimality.  LEMMA 10. Let Ψ be a set of configurations, all are within δ  of maximizing profit for a trader τ at the prices, and Φ defined  as in Lemma 8. Then any consistent cover in Φ is within δg of  maximizing utility for τ.  This bound is tight, that is for any GAI tree and a non-trivial  domain we can construct a set Ψ as above in which there exists a  consistent cover whose utility is exactly δg below the maximal.  Next we formally define Mt  . For connected GAI trees, Mt  is  the set of sub-configurations that are part of a configuration within  of optimal. When the GAI tree is in fact a forest, we apportion  the error proportionally across the disconnected trees. Let G be  comprised of trees G1, . . . , Gh. We use θj to denote the projection  of a configuration θ on the tree Gj , and gj denotes the number of  GAI elements in Gj .  Mt  j = {θr | πt  b(θj) ≥ max  θj ∈Θj  πt  b(θj ) − gj  g  , r ∈ Gj }  Then define Mt  =  Sh  j=1 Mt  j.  Let ej = gj −1 denote the number of edges in Gj . We define the  connectivity parameter, e = maxj=1,...,h ej . As shown below, this  connectivity parameter is an important factor in the performance of  the auction.  COROLLARY 11.  ∀θ ∈ Mt  , πt  b(θ ) ≥ max  θ∈Θ  πt  b(θ) − (e + 1)  In the fully additive case this loss of efficiency reduces to . On the  other extreme, if the GAI network is connected then e+1 = g. We  also note that without assuming any preference structure, meaning  that the CDI map is fully connected, g = 1 and the efficiency loss  is again .  Lemmas 12 through 15 show that through the price system, the  choice of buyer preferred configurations, and price change rules,  Phase A leads the buyer and each of the sellers to their mutually  efficient configuration.  LEMMA 12. maxθ∈Θ πt  b(θ) does not change in any round t of  phase A.  PROOF. We prove the lemma per each tree Gj. The optimal  values for disconnected components are independent of each other  hence if the maximal profit for each component does not change  the combined maximal profit does not change as well. If the price  of θj was reduced during phase A, that is pt+1  (θj) = pt  (θj ) − δ,  it must be the case that some w ≤ gj sub-configurations of θj are  not in Mt  j, and δ = w  g  . The definition of Mt  j ensures  πt  b(θj ) < max  θ∈Θ  πt  b(θj) − gj  g  .  Therefore,  πt+1  b (θ ) = πt  (θ ) + δ = πt  (θ ) +  w  g  ≤ max  θ∈Θ  πt  b(θj).  This is true for any configuration whose profit improves,   therefore the maximal buyer profit does not change during phase A.  LEMMA 13. The price of at least one sub-configuration must  be reduced at every round in phase A.  PROOF. In each round t < T of phase A there exists an active  seller i for whom Bt  i ∩ Mt  = ∅. However to be active in round t,  Bt  i = ∅. Let ˆθ ∈ Bt  i . If ∀r.ˆθr ∈ Mt  , then ˆθ ∈ Mt  by definition  of Mt  . Therefore there must be ˆθr ∈ Mt  . We need to prove that  for at least one of these sub-configurations, πt  b(ˆθr) < 0 to ensure  activation of rule [A].  Assume for contradiction that for any ˆθr ∈ ¯Mt  , πt  b(ˆθr) ≥ 0.  For simplicity we assume that for any θr, π1  b (θr) is some product  of g  (that can be easily done), and that ensures that πt  b(ˆθr) = 0  because once profit hits 0 it cannot increase by rule [A].  If ˆθr ∈ ¯Mt  , ∀r = 1, . . . , g then πt  b(ˆθ) = 0. This contradicts  Lemma 12 since we set high initial prices. Therefore some of the  sub-configurations of ˆθ are in Mt  , and WLOG we assume it is  ˆθ1, . . . , ˆθk. To be in Mt  these k sub-configurations must have been  in some preferred full configuration, meaning there exists θ ∈ Mt  such that  θ = (ˆθ1, . . . , ˆθk, θk+1, . . . , θg)  Since ˆθ /∈ Mt  It must be that case that πt  b(ˆθ) < πt  b(θ ). Therefore  πt  b(θk+1, . . . , θg) > πt  b(ˆθk+1, . . . , ˆθg) = 0  Hence for at least one r ∈ {k + 1, . . . , g}, πt  b(θr) > 0   contradicting rule [A].  233  LEMMA 14. When the solution to MAP provides positive   surplus, and at least the best seller is SB, the auction must reach  phase B.  PROOF. By Lemma 13 prices must go down in every round  of phase A. Rule [A] sets a lower bound on all prices therefore  the auction either terminates in phase A or must reach condition  [SWITCH].  We set the initial prices are high such that maxθ∈Θ π1  b (θ) < 0,  and by Lemma 12 maxθ∈Θ πt  b(θ) < 0 during phase A. We   assume that the efficient allocation (θ∗  , i∗  ) provides positive welfare,  that is σi∗ (θ∗  ) = πt  b(θ∗  ) + πt  i∗ (θ∗  ) > 0. si∗ is SB therefore  she will leave the auction only when πt  i∗ (θ∗  ) < 0. This can  happen only when πt  b(θ∗  ) > 0, therefore si∗ does not drop in  phase A hence the auction cannot terminate before reaching   condition [SWITCH].  LEMMA 15. For SB seller si, ηi is (e + 1) -efficient.  PROOF. ηi is chosen to maximize the buyer"s surplus out of Bt  i  at the end of phase A. Since Bt  i ∩ Mt  = ∅, clearly ηi ∈ Mt  . From  Corollary 11 and Corollary 9, for any ˜θ,  πT  b (ηi) ≥ πT  b (˜θ) − (e + 1)  πT  i (ηi) ≥ πT  i (˜θ)  ⇒ σi(ηi) ≥ σi(˜θ) − (e + 1)  This establishes the approximate bilateral efficiency of the results  of Phase A (at this point under the assumption of SB). Based on  Phase B"s simple role as a single-dimensional bidding competition  over the discount, we next assert that the overall result is efficient  under SB, which in turn proves to be an approximately ex-post  equilibrium strategy in the two phases.  LEMMA 16. If sellers si and sj are SB, and si is active at least  as long as sj is active in phase B, then  σi(ηi) ≥ max  θ∈Θ  σj(θ) − (e + 2)  .  THEOREM 17. Given a truthful buyer and SB sellers, the   auction is (e+2) -efficient: the surplus of the final allocation is within  (e + 2) of the maximal surplus.  Following PK, we rely on an equivalence to the one-sided VCG  auction to establish incentive properties for the sellers. In the   onesided multiattribute VCG auction, buyer and sellers report   valuation and cost functions ˆub, ˆci, and the buyer pays the sell-side VCG  payment to the winning seller.  DEFINITION 11. Let (θ∗  , i∗  ) be the optimal solution to MAP.  Let (˜θ,˜i) be the best solution to MAP when i∗  does not participate.  The sell-side VCG payment is  V CG(ˆub, ˆci) = ˆub(θ∗  ) − (ˆub(˜θ) − ˆc˜i(˜θ)).  It is well-known that truthful bidding is a dominant strategy for  sellers in the one-sided VCG auction. It is also shown by PK that  the maximal regret for buyers from bidding truthfully in this   mechanism is ub(θ∗  ) − ci∗ (θ∗  ) − (ub(˜θ) − ˆc˜i(˜θ)), that is, the marginal  product of the efficient seller.  Usually in iterative auctions the VCG outcome is only nearly  achieved, but the deviation is bounded by the minimal price change.  We show a similar result, and therefore define δ-VCG payments.  DEFINITION 12. Sell-side δ-VCG payment for MAP is a   payment p such that  V CG(ˆub, ˆci) − δ ≤ p ≤ V CG(ˆub, ˆci) + δ.  When payment is guaranteed to be δ-VCG sellers can only affect  their payment within that range, therefore their gain by falsely   reporting their cost is bounded by 2δ.  LEMMA 18. When sellers are SB, the payment in the end of  GAI auction is sell-side (e + 2) -VCG.  THEOREM 19. SB is an (3e + 5) ex-post Nash Equilibrium  for sellers in GAI auction. That is, sellers cannot gain more than  (3e + 5) by deviating.  In practice, however, sellers are unlikely to have the information  that would let them exploit that potential gain. They are much more  likely to lose from bidding on their less attractive configurations.  5.5 Computation and Complexity  The size of the price space maintained in the auction is equal to  the total number of sub-configurations, meaning it is exponential in  maxr |Ir|. This is also equivalent to the tree-width (plus one) of the  original CDI-map. For the purpose of the computational analysis  let dj denote the domain of attribute aj, and I =  Sg  r=1  Q  j∈Ir  dj,  the collection of all sub-configurations. The first purpose of this  sub-section is to show that the complexity of all the computations  required for the auction depends only on |I|, i.e., no computation  depends on the size of the full exponential domain.  We are first concerned with the computation of Mt  . Since Mt  grows monotonically with t, a naive application of optimization  algorithm to generate the best outcomes sequentially might end up  enumerating significant portions of the fully exponential domain.  However as shown below this plain enumeration can be avoided.  PROPOSITION 20. The computation of Mt  can be done in time  O(|I|2  ). Moreover, the total time spent on this task throughout the  auction is O(|I|(|I| + T)).  The bounds are in practice significantly lower, based on results on  similar problems from the probabilistic reasoning literature [18].  One of the benefits of the compact pricing structure is the   compact representation it lends for bids: sellers submit only sub-bids,  and therefore the number of them submitted and stored per seller  is bounded by |I|. Since the computation tasks: Bt  i = ∅, rule  [SWITCH] and choice of ηi are all involving the set Bt  i , it is   important to note that their performance only depend on the size of  the set Bt  i , since they are all subsumed by the combinatorial   optimization task over Bt  i or Bt  i ∩ Mt  .  Next, we analyze the number of rounds it takes for the auction  to terminate. Phase B requires maxi=1,...n πT  i (ηi)1  . Since this is  equivalent to price-only auctions, the concern is only with the time  complexity of phase A. Since prices cannot go below fb,r(θr), an  upper bound on the number of rounds required is  T ≤  X  θr∈I  (p1  (θr) − fb,r(θr))  g  However phase A may converge faster. Let the initial negative  profit chosen by the auctioneer be m = maxθ∈Θ π1  b (θ). In the  worst case phase A needs to run until ∀θ ∈ Θ.πb(θ) = m. This  happens for example when ∀θr ∈ I.pt  (θr) = fb,r(θr) + m  g  . In  general, the closer the initial prices reflect buyer valuation, the  faster phase A converges. One extreme is to choose p1  (θr) =  234  I1 I2  a1  b1  a2  b1  a1  b2  a2  b2  b1  c1  b2  c1  b1  c2  b2  c2  fb 65 50 55 70 50 85 60 75  f1 35 20 30 70 65 65 70 61  f2 35 20 25 25 55 110 70 95  Table 1: GAI utility functions for the example domain. fb   represents the buyer"s valuation, and f1 and f2 costs of the sellers  s1 and s2.  fb,r(θr) + m  g  . That would make phase A redundant, at the cost of  full initial revelation of buyer"s valuation as done in other   mechanisms discussed below. Between this option and the other extreme,  which is ∀α, ˆα ∈ I, p1  (α) = p1  (ˆα) the auctioneer has a range of  choices to determine the right tradeoff between convergence time  and information revelation. In the example below the choice of a  lower initial price for the domain of I1 provides some speedup by  revealing a harmless amount of information.  Another potential concern is the communication cost associated  with the Japanese auction style. The sellers need to send their bids  over and over again at each round. A simple change can be made  to avoid much of the redundant communication: the auction can  retain sub-bids from previous rounds on sub-configurations whose  price did not change. Since combinations of sub-bids from different  rounds can yield sub-optimal configurations, each sub-bid should  be tagged with the number of the latest round in which it was   submitted, and only consistent combinations from the same round are  considered to be full bids. With this implementation sellers need  not resubmit their bid until a price of at least one sub-configuration  has changed.  5.6 Example  We use the example settings introduced in Section 5.2. Recall  that the GAI structure is I1 = {a, b}, I2 = {b, c} (note that e = 1).  Table 1 shows the GAI utilities for the buyer and the two sellers  s1, s2. The efficient allocation is (s1, a1  b2  c1  ) with a surplus of 45.  The maximal surplus of the second best seller, s2, is 25, achieved  by a1  b1  c1  , a2  b1  c1  , and a2  b2  c2  . We set all initial prices over I1  to 75, and all initial prices over I2 to 90. We set = 8, meaning  that price reduction for sub-configurations is 4. Though with these  numbers it is not guaranteed by Theorem 17, we expect s1 to win on  either the efficient allocation or on a1  b2  c2  which provides a surplus  of 39. The reason is that these are the only two configurations  which are within (e + 1) = 16 of being efficient for s1 (therefore  one of them must be chosen by Phase A), and both provide more  than surplus over s2"s most efficient configuration (and this is  sufficient in order to win in Phase B).  Table 2 shows the progress of phase A. Initially all configuration  have the same cost (165), so sellers bid on their lowest cost   configuration which is a2  b1  c1  for both (with profit 80 to s1 and 90 to s2),  and that translates to sub-bids on a2  b1  and b1  c1  . M1  contains the  sub-configurations a2  b2  and b2  c1  of the highest value configuration  a2  b2  c1  . Price is therefore decreased on a2  b1  and b1  c1  . After the  price change, s1 has higher profit (74) on a1  b2  c2  and she therefore  bids on a1  b2  and b2  c2  . Now (round 2) their prices go down,   reducing the profit on a1  b2  c2  to 66 and therefore in round 3 s1 prefers  a2  b1  c2  (profit 67). After the next price change the configurations  a1  b2  c1  and a1  b2  c2  both become optimal (profit 66), and the   subbids a1  b2  , b2  c1  and b2  c2  capture the two. These configurations stay  optimal for another round (5), with profit 62. At this point s1 has  a full bid (in fact two full bids: a1  b2  c2  and a1  b2  c1  ) in M5  , and  I1 I2  t a1b1 a2b1 a1b2 a2b2 b1c1 b2c1 b1c2 b2c2  1 75 75 75 75 90 90 90 90  s1, s2 ∗ s1, s2 ∗  2 75 71 75 75 86 90 90 90  s2 s1 ∗ s2 ∗ s1  3 75 67 71 75 82 90 90 86  s1, s2 ∗ s2 ∗ s1 ∗  4 75 63 71 75 78 90 86 86  s2 s1 ∗ s2 ∗, s1 ∗, s1  5 75 59 67 75 74 90 86 86  s2 ∗, s1 ∗ s2 ∗, s1 ∗, s1  6 71 59 67 75 70 90 86 86  s2 ∗, s1 ∗ ∗, s1 s2 ∗, s1  7 71 55 67 75 70 90 82 86  s2 ∗, s1 ∗ s2 ∗, s1 ∗, s1  8 67 55 67 75 66 90 82 86  ∗ s2 ∗, s1 ∗ ∗ ∗, s1 s2 ∗, s1  9 67 51 67 75 66 90 78 86  ∗, s2 ∗, s1 ∗ ∗, s2 ∗, s1 ∗, s1  Table 2: Auction progression in phase A. Sell bids and   designation of Mt  (using ∗) are shown below the price of each   subconfiguration.  therefore she no longer changes her bids since the price of her   optimal configurations does not decrease. s2 sticks to a2  b1  c1  during  the first four rounds, switching to a1  b1  c1  in round 5. It takes four  more rounds for s2 and Mt  to converge (M10  ∩B10  2 = {a1  b1  c1  }).  After round 9 the auction sets η1 = a1  b2  c1  (which yields more  buyer profit than a1  b2  c2  ) and η2 = a1  b1  c1  . For the next round  (10) Δ = 8, increased by 8 for each subsequent round. Note that  p9  (a1  b1  c1  ) = 133, and c2(a1  b1  c1  ) = 90, therefore πT  2 (η2) =  43. In round 15, Δ = 48 meaning p15  (a1  b1  c1  ) = 85 and that  causes s2 to drop out, setting the final allocation to (s1, a1  b2  c1  )  and p15  (a1  b2  c1  ) = 157 − 48 = 109. That leaves the buyer with a  profit of 31 and s1 with a profit of 14, less than below the VCG  profit 20.  The welfare achieved in this case is optimal. To illustrate how  some efficiency loss could occur consider the case that c1(b2  c2  ) =  60. In that case, in round 3 the configuration a1  b2  c2  provides the  same profit (67) as a2  b1  c2  , and s1 bids on both. While a2  b1  c2  is  no longer optimal after the price change, a1  b2  c2  remains optimal  on subsequent rounds because b2  c2  ∈ Mt  , and the price change  of a1  b2  affects both a1  b2  c2  and the efficient configuration a1  b2  c1  .  When phase A ends B10  1 ∩ M10  = {a1  b2  c2  } so the auction   terminates with the slightly suboptimal configuration and surplus 40.  6. DISCUSSION  6.1 Preferential Assumptions  A key aspect in implementing GAI based auctions is the choice  of the preference structure, that is, the elements {I1, . . . , Ig}. In  some domains the structure can be more or less robust over time  and over different decision makers. When this is not the case,   extracting reliable structure from sellers (in the form of CDI   conditions) is a serious challenge. This could have been a deal breaker  for such domains, but in fact it can be overcome. It turns out that  we can run this auction without any assumptions on sellers"   preference structure. The only place where this assumption is used in our  analysis is for Lemma 8. If sellers whose preference structure does  not agree with the one used by the auction are guided to submit  only one full bid at each round, or a set of bids that does not yield  undesired consistent combinations, all the properties of the auction  235  still hold. Locally, the sellers can optimize their profit functions  using the union of their GAI structure with the auction"s structure.  It is therefore essential only that the buyer"s preference structure is  accurately modeled. Of course, capturing sellers" structures as well  is still preferred since it can speed up the execution and let sellers  take advantage of the compact bid representation.  In both cases the choice of clusters may significantly affect the  complexity of the price structure and the runtime of the auction.  It is sometimes better to ignore some weaker interdependencies in  order to reduce dimensionality. The complexity of the structure  also affects the efficiency of the auction through the value of e.  6.2 Information Revelation Properties  In considering information properties of this mechanism we   compare to the standard approach for iterative multiattribute auctions,  which is based on the theoretical foundations of Che [7]. In most of  these mechanisms the buyer reveals a scoring function and then the  mechanism solicits bids from the sellers [3, 22, 8, 21] (the   mechanisms suggested by Beil and Wein [2] is different since buyers  can modify their scoring function each round, but the goal there is  to maximize the buyer"s profit). Whereas these iterative   procurement mechanisms tend to relieve the burden of information   revelation from the sellers, a major drawback is that the buyer"s   utility function must be revealed to the sellers before receiving any  commitment. In the mechanisms suggested by PK and in our GAI  auction above, buyer information is revealed only in exchange for  sell commitments. In particular, sellers learn nothing (beyond the  initial price upper bound, which can be arbitrarily loose) about the  utility of configurations for which no bid was submitted. When  bids are submitted for a configuration θ, sellers would be able to  infer its utility relative to the current preferred configurations only  after the price of θ is driven down sufficiently to make it a preferred  configuration as well.  6.3 Conclusions  We propose a novel exploitation of preference structure in   multiattribute auctions. Rather than assuming full additivity, or no   structure at all, we model preferences using the GAI decomposition.  We developed an iterative auction mechanism directly relying on  the decomposition, and also provided direct means of constructing  the representation from relatively simple statements of   willingnessto-pay. Our auction mechanism generalizes PK"s preference   modeling, while in essence retaining their information revelation   properties. It allows for a range of tradeoffs between accuracy of   preference representation and both the complexity of the pricing structure  and efficiency of the auction, as well as tradeoffs between buyer"s  information revelation and the time required for convergence.  7. ACKNOWLEDGMENTS  This work was supported in part by NSF grants IIS-0205435  and IIS-0414710, and the STIET program under NSF IGERT grant  0114368. We are grateful to comments from anonymous reviewers.  8. REFERENCES  [1] F. Bacchus and A. Grove. Graphical models for preference  and utility. In Eleventh Conference on Uncertainty in  Artificial Intelligence, pages 3-10, Montreal, 1995.  [2] D. R. Beil and L. M. Wein. An inverse-optimization-based  auction for multiattribute RFQs. Management Science,  49:1529-1545, 2003.  [3] M. Bichler. The Future of e-Markets: Multi-Dimensional  Market Mechanisms. Cambridge University Press, 2001.  [4] C. Boutilier, F. Bacchus, and R. I. Brafman. UCP-networks:  A directed graphical representation of conditional utilities. In  Seventeenth Conference on Uncertainty in Artificial  Intelligence, pages 56-64, Seattle, 2001.  [5] R. I. Brafman, C. Domshlak, and T. Kogan. Compact  value-function representations for qualitative preferences. In  Twentieth Conference on Uncertainty in Artificial  Intelligence, pages 51-59, Banff, 2004.  [6] D. Braziunas and C. Boutilier. Local utility elicitation in GAI  models. In Twenty-first Conference on Uncertainty in  Artificial Intelligence, pages 42-49, Edinburgh, 2005.  [7] Y.-K. Che. Design competition through multidimensional  auctions. RAND Journal of Economics, 24(4):668-680,  1993.  [8] E. David, R. Azoulay-Schwartz, and S. Kraus. An English  auction protocol for multi-attribute items. In Agent Mediated  Electronic Commerce IV: Designing Mechanisms and  Systems, volume 2531 of Lecture Notes in Artificial  Intelligence, pages 52-68. Springer, 2002.  [9] G. Debreu. Topological methods in cardinal utility theory. In  K. Arrow, S. Karlin, and P. Suppes, editors, Mathematical  Methods in the Social Sciences. Stanford Univ. Press, 1959.  [10] J. S. Dyer and R. K. Sarin. An axiomatization of cardinal  additive conjoint measurement theory. Working Paper 265,  WMSI, UCLA, February 1977.  [11] J. S. Dyer and R. K. Sarin. Measurable multiattribute value  functions. Operations Research, 27:810-822, 1979.  [12] Y. Engel, M. P. Wellman, and K. M. Lochner. Bid  expressiveness and clearing algorithms in multiattribute  double auctions. In Seventh ACM Conference on Electronic  Commerce, pages 110-119, Ann Arbor, MI, 2006.  [13] P. C. Fishburn. Interdependence and additivity in  multivariate, unidimensional expected utility theory. Intl.  Economic Review, 8:335-342, 1967.  [14] C. Gonzales and P. Perny. GAI networks for utility  elicitation. In Ninth Intl. Conf. on the Principles of  Knowledge Representation and Reasoning, pages 224-234,  Whistler, BC, 2004.  [15] C. Gonzales and P. Perny. GAI networks for decision making  under certainty. In IJCAI-05 Workshop on Advances in  Preference Handling, Edinburgh, 2005.  [16] N. Hyafil and C. Boutilier. Regret-based incremental partial  revelation mechanisms. In Twenty-first National Conference  on Artificial Intelligence, pages 672-678, Boston, MA, 2006.  [17] R. L. Keeney and H. Raiffa. Decisions with Multiple  Objectives: Preferences and Value Tradeoffs. Wiley, 1976.  [18] D. Nilsson. An efficient algorithm for finding the M most  probable configurations in probabilistic expert systems.  Statistics and Computinge, 8(2):159-173, 1998.  [19] D. C. Parkes and J. Kalagnanam. Models for iterative  multiattribute procurement auctions. Management Science,  51:435-451, 2005.  [20] J. Pearl and A. Paz. Graphoids: A graph based logic for  reasoning about relevance relations. In B. Du Boulay, editor,  Advances in Artificial Intelligence II. 1989.  [21] J. Shachat and J. T. Swarthout. Procurement auctions for  differentiated goods. IBM Research Report RC22587, IBM  T.J. Watson Research Laboratory, 2002.  [22] N. Vulkan and N. R. Jennings. Efficient mechanisms for the  supply of services in multi-agent environments. Decision  Support Systems, 28:5-19, 2000.  236