Generalized Trade Reduction Mechanisms  Mira Gonen  Electrical Engineering Dept.  Tel Aviv University  Ramat Aviv 69978, Israel  gonenmir@post.tau.ac.il  Rica Gonen∗  Yahoo! Research  Yahoo!  Sunnyvale, CA 94089  gonenr@yahoo-inc.com  Elan Pavlov  Media Lab  MIT  Cambridge MA, 02149  elan@mit.edu  ABSTRACT  When designing a mechanism there are several desirable  properties to maintain such as incentive compatibility (IC),  individual rationality (IR), and budget balance (BB). It is  well known [15] that it is impossible for a mechanism to  maximize social welfare whilst also being IR, IC, and BB.  There have been several attempts to circumvent [15] by   trading welfare for BB, e.g., in domains such as double-sided  auctions[13], distributed markets[3] and supply chain   problems[2, 4].  In this paper we provide a procedure called a   Generalized Trade Reduction (GTR) for single-value players, which  given an IR and IC mechanism, outputs a mechanism which  is IR, IC and BB with a loss of welfare. We bound the  welfare achieved by our procedure for a wide range of   domains. In particular, our results improve on existing   solutions for problems such as double sided markets with   homogenous goods, distributed markets and several kinds of  supply chains. Furthermore, our solution provides   budget balanced mechanisms for several open problems such as  combinatorial double-sided auctions and distributed   markets with strategic transportation edges.  Categories and Subject Descriptors  J.4 [Social and Behavioral Sciences]: Economics; K.4.4  [Electronic Commerce]: Payment scheme    1. INTRODUCTION  When designing a mechanism there are several key   properties that are desirable to maintain. Some of the more  important ones are individual rationality (IR) - to make it  worthwhile for all players to participate, incentive   compatibility (IC) - to give incentive to players to report their true  value to the mechanism and budget balance (BB) - not to  run the mechanism on a loss. In many of the mechanisms  the goal function that a mechanism designer attempts to  maximize is the social welfare1  - the total benefit to society.  However, it is well known from [15] that any mechanism that  maximizes social welfare while maintaining individual   rationality and incentive compatibility runs a deficit perforce,  i.e., is not budget balanced.  Of course, for many applications of practical importance  we lack the will and the capability to allow the mechanism  to run a deficit and hence one must balance the payments  made by the mechanism. To maintain the BB property in  an IR and IC mechanism it is necessary to compromise on  the optimality of the social welfare.  1.1 Related Work and Specific Solutions  There have been several attempts to design budget   balanced mechanisms for particular domains2  . For instance,  for double-sided auctions where both the buyers and sellers  are strategic and the goods are homogeneous [13] (or when  the goods are heterogeneous [5]). [13] developed a   mechanism that given valuations of buyers and sellers produces an  allocation (which are the trading players) and a matching  between buyers and sellers such that the mechanism is IR,  IC, and BB while retaining most of the social welfare. In the  distributed markets problem (and closely related problems)  goods are transported between geographic locations while  incurring some constant cost for transportation. [16, 9,  3] present mechanisms that approximate the social welfare  while achieving an IR, IC and BB mechanism. For supply  chain problems [2, 4] bounds the loss of social welfare that  is necessary to inflict on the mechanism in order to achieve  the desired combination of IR, IC, and BB.  Despite the works discussed above, the question of how to  design a general mechanism that achieves IR, IC, and BB  independently of the problem domain remains open.   Furthermore, there are several domains where the question of  how to design an IR, IC and BB mechanism which   approx1  Social Welfare is also referred to as efficiency in the   economics literature.  2  A brief reminder of all of the problems used in this paper  can be found in Appendix B  20  imates the social welfare remains an open problem. For  example, in the important domain of combinatorial   doublesided auctions there is no known result that bounds the loss  of social welfare needed to achieve budget balance. Another  interesting example is the open question left by [3]:How can  one bound the loss in social welfare that is needed to achieve  budget balance in an IR and IC distributed market where  the transportation edges are strategic. Naturally an answer  to the BB distributed market with strategic edges has vast  practical implications, for example to transportation   networks.  1.2 Our Contribution  In this paper we unify all the problems discussed above  (both the solved as well as the open ones) into one solution  concept procedure. The solution procedure called the   Generalized Trade Reduction (GTR). GTR accepts an IR and  IC mechanism for single-valued players and outputs an IR,  IC and BB mechanism. The output mechanism may suffer  some welfare loss as a tradeoff of achieving BB. There are  problem instances in which no welfare loss is necessary but  by [15] there are problem instances in which there is welfare  loss. Nevertheless for a wide class of problems we are able to  bound the loss in welfare. A particularly interesting case is  one in which the input mechanism is an efficient allocation.  In addition to unifying many of the BB problems under  a single solution concept, the GTR procedure improves on  existing results and solves several open problems in the   literature. The existing solutions our GTR procedure improves  are homogeneous double-sided auctions, distributed markets  [3], and supply chain [2, 4]. For the homogeneous   doublesided auctions the GTR solution procedure improves on the  well known solution [13] by allowing for some cases of no  trade reduction at all. For the distributed markets [3] and  the supply chain [2, 4] the GTR solution procedure improves  on the welfare losses" bound, i.e., allows one to achieve an  IR, IC and BB mechanism with smaller loss on the social  welfare. Recently we also learned that the GTR procedure  allows one to turn the model newly presented [6] into a  BB mechanism. The open problems that are answered by  GTR are distributed markets with strategic transportation  edges and bounded paths, combinatorial double-sided   auctions with bounded size of the trading group i.e., a buyer and  its bundle goods" sellers, combinatorial double-sided   auctions with bounded number of possible trading groups.  In addition to the main contribution described above, this  paper also defines an important classification of problem   domains. We define class based domain and procurement class  based domains. The above definitions build on the   different competition powers of players in a mechanisms called  internal and external competition. Most of the studied   problem domains are of the more restrictive procurement class  domains and we believe that the more general setting will  inspire more research.  2. PRELIMINARIES  2.1 The Model  In this paper we design a method which given any IR  and IC mechanism outputs a mechanism that maintains the  IC and IR properties while achieving BB. For some classes  of mechanisms we bound the competitive approximation of  welfare.  In our model there are N players divided into sets of trade.  The sets of trade are called procurement sets and are defined  (following [2]) as follows:  Definition 2.1. A procurement set s is the smallest set  of players that is required for trade to occur.  For example, in a double-sided auction, a procurement set  is a pair consisting of a buyer and a seller. In a   combinatorial double-sided auction a procurement set can consist of a  buyer and several sellers. We mark the set of all   procurement sets as S and assume that any allocation is a disjoint  union of procurement sets.  Each player i, 1 ≤ i ≤ n, assigns a real value vi(s) to  each possible procurement set s ∈ S. Namely, vi(s) is the  valuation of player i on procurement set s. We assume that  for each player i vi(s) is i"s private value and that i is a single  value player, meaning that if vi(sj) > 0 then for every other  sk, k = j, either vi(sk) = vi(sj) or vi(sk) = 0. For the  ease of notation we will mark by vi the value of player i  for any procurement set s such that vi(s) > 0. The set  Vi ⊆ R is the set of all possible valuations vi. The set  of all possible valuations of all the players is denoted by  V = V1 × ... × Vn. Let v−i = (v1, ..., vi−1, vi+1, ..., vn) be the  vector of valuations of all the players besides player i, and  let V−i be the set of all possible vectors v−i.  We denote by W(s) the value of a procurement set s ∈  S such that W(s) = i∈s vi(s) + F(s), where F is some  function that assigns a constant to procurement sets. For  example, F can be a (non-strategic) transportation cost in  a distributed market problem. Let the size of a procurement  set s be denoted as |s|.  It is assumed that any allocation is a disjoint union of  procurement sets and therefore one can say that an   allocation partitions the players into two sets; a set of players that  trade and a set of players that do not trade.  The paper denotes by O the set of possible partitions of an  allocation A into procurement sets. The value W(A) of an  allocation A is the sum of the values of its most efficient   partition to procurement sets, that is W(A) = maxS∈O s∈S W(s).  This means that W(A) = i∈A vi +maxS∈O s∈S F(s). In  the case where F is identically zero, then W(A) = i∈A vi.  An optimal partition S∗  (A) is a partition that maximizes  the above sum for an allocation A. Let the value of A be  W(S∗  (A)) (note that the value can depend on F). We say  that the allocation A is efficient if there is no other allocation  with a higher value. The efficiency of the allocation ˆA is  W ( ˆA)  W (A)  , where A is a maximal valued allocation. We assume  w.l.o.g. that there are no two allocations with the same  value3  .  A mechanism M defines an allocation and payment rules,  M = (R, P). A payment rule P decides i"s payment pi where  P is a function P : V → RN  . We work with mechanisms  3  Ties can be broken using the identities of the players.  21  in which players are required to report their values. An  example of such a mechanism is the VCG mechanism [17,  8, 10]. The reported value bi ∈ Vi of player i is called a  bid and might be different from his private value vi. Let  b ∈ V be the bids of all players. An allocation rule R decides  the allocation according to the reported values b ∈ V . We  make the standard assumption that players have quasi-linear  utility so that when player i trades and pays pi then his  utility is ui(vi, b−i) = vi − pi, ui : V ⇒ R. We also assume  that players are rational utility maximizers.  Mechanism M is Budget Balanced (BB) if i∈N pi ≥ 0  for any bids b ∈ V . M is Incentive-Compatible (IC) in   dominant strategies if for any player i, value vi and any b−i ∈ V−i,  ui(vi, b−i) ≥ ui(b) meaning that for any player i, bidding vi  maximized i"s utility over all possible bids of the other   players. M is (ex-post) Individually Rational (IR) if for any  player i value vi, and any b−i ∈ V−i ui(vi, b−i) ≥ 0   meaning that for all possible bids of the other players, player"s i  utility is non-negative. Note that since our mechanisms are  normalized IR, if a player does not trade then the player  pays 0 and has utility 0.  Our algorithm presented in the next section employs a  commonly used payment scheme, the critical value payment  scheme.  Definition 2.2. Critical value payment scheme: A   mechanism uses a critical value payment scheme if given an   allocation it charges players the minimum value they need to  report to the mechanism in order to remain allocated.  We denote by Ci the critical value price computed for player  i.  2.2 Competitions and Domains  In this paper we present two generalized trade reduction  algorithms. The two algorithms are such that given an IR  and IC mechanism M that solves a problem in some   domain (different domains are formally defined below), turns  M into IR, IC and BB mechanism. The algorithm presented  finds procurement sets and removes them in iterations until  the right conditions are fulfilled and the mechanism M is  turned into a BB one. The right conditions that need to  be met are conditions of competition among the players in  the given problem. The following definitions leads us to the  competition conditions we are looking for.  Definition 2.3. For any player i ∈ N, we say that the  set Ri ⊆ N \ {i} is a replacing set of i, if for any   procurement set s ∈ S such that i ∈ s and Ri∩s = ∅, s\{i}∪Ri ∈ S.  For example, in a (homogeneous) double-sided auction  (see problem B.1) the replacement set for any buyer is simply  any other buyer. In an auction for transportation slots (see  problem B.7), the replacement set of an edge is a path   between the endpoints of the edge. Note that a set can replace  a single player. Furthermore, this relationship is transitive  but not necessarily symmetric. If i is a replacement set for  j, it is not necessarily true that j is a replacement set for i.  Definition 2.4. For any allocation A, procurement set  s ⊆ A, and any i ∈ s we say Ri(A, s) is an internal   competition for i with respect to A and s, if Ri(A, s) ⊆ N \ A  is a replacement set for i s.t. T = s \ {i} ∪ Ri(A, s) ∈ S and  W(T) ≥ 0.  Definition 2.5. For any allocation A and procurement  set s ⊆ A and any i ∈ s we say that Ei(A, s) is an external  competition for i with respect to A and s, if Ei(A, s) ⊆  N \ A is a set s.t., T = {i} ∪ Ei(A, s) ∈ S and W(T) ≥ 0.  We will assume, without loss of generality, that there are  no ties between the values of any allocations, and in   particular there are no ties between values of procurement sets.  In case of ties, these can be broken by using the identities  of the players4  . So for any allocation A, procurement set s  and player i with external competition Ei(A, s), there exists  exactly one set representing the maximally valued external  competition.  Definition 2.6. A set X ⊂ N is closed under   replacement if ∀i ∈ X then Ri ⊂ X  The following defines the required competition needed to  maintain IC, IR and BB. The set X5  denotes this   competition and is closed under replacement. In the remainder of  the paper we will assume that all of our sets which define  competition in a mechanism are closed under replacement.  Definition 2.7. Let X ⊂ N be a set that is closed under  replacement, we say that the mechanism is an X-external  mechanism, if  1. Each player i ∈ X has an external competition.  2. Each player i /∈ X has an internal competition.  3. For all players i1, . . . , it ∈ s \ X there exist  Ri1 (A, s), . . . , Rit (A, s)  such that for every iz = iq, Riz (A, s) ∩ Riq (A, s) = ∅  4. for every procurement set s ∈ S it holds that s∩X = ∅  For general domains the choice of X can be crucial. In  fact even for the same domain the welfare (and revenue) can  vary widely depending on how X is defined. In appendix C  we give an example where two possible choices of X yield  greatly different results. Although we show that X should  be chosen as small as possible we do not give any   characterization of the optimality of X and this is an important open  problem.  Our two generalized trade reduction algorithms will   ensure that for any allocation we have the desired types of  competition. So given a mechanism M that is IC and IR  with allocation A, the goal of the algorithms is to turn M  into an X-external mechanism. The two generalized trade  reduction algorithms utilize a dividing function D which   divides allocation A into disjoint procurement sets. The   algorithms order the procurements sets defined by D in order  of increasing value. For any procurement set there is a   desired type of competition that depends only on the players  who compose the procurement set. The generalized trade  reduction algorithms go over the procurement sets in order  (from the smallest to the largest) and remove any   procurement set that does not have the desired competition when  the set is reached. The reduction of procurement sets will  also be referred to as a trade reduction.  Formally,  4  The details of how to break ties in allocations are standard  and are omitted.  5  We present some tradeoffs between the different possible  sets in Appendix C.  22  Definition 2.8. D is a dividing function if for any   allocation A and the players" value vector v, D divides the   allocation into disjoint procurements sets s1, . . . , sk s.t. ∪sj =  A and for any player i with value vi if i ∈ sj1 and t ∈ sj2 s.t.  j1 ≥ j2 then for any value vi > vi of player i and division by  D into s1, . . . , sk such that i ∈ sj1  and t ∈ sj2  then j1 > j2.  The two generalized trade reduction algorithms presented  accept problems in different domains. The formal domain  definitions follow:  Definition 2.9. A domain is a class domain if for all  i ∈ N and all replacement sets of i, Ri, |Ri| = 1 and for all  i, j, i = j if j = Ri then i = Rj.  Intuitively, this means that replacement sets are of size 1  and the replacing relationship is symmetric.  We define the class of a player i as the set of the player"s  replacement sets and denote the class of player i by [i]. It is  important to note that since replacement sets are transitive  relations and since class domains also impose symmetric   relations on the replacement sets, the class of a player i, [i] is  actually an equivalence class for i.  Definition 2.10. A domain is a procurement-class   domain if the domain is a class-based domain and if for any  player i such that there exists two procurement sets s1, s2  (not necessarily trading simultaneously in any allocation)  such that i ∈ s1 and i ∈ s2 then there exists a bijection  f : s1 → s2 such that for any j ∈ s1, f(j) is a replacement  set for j in s2.  Example 2.1. A (homogeneous) double-sided auction (see  problem B.1) is a procurement-class based domain. For the  (homogeneous) double-sided auction each procurement set  consists of a buyer and a seller.  The double sided combinatorial auction consisting of a   single multi-minded buyer and multiple sellers of heterogenous  goods (see problem B.9), is a class based domain (as we have  a single buyer) but not a procurement-class based domain.  In this case, the buyer is a class and each set of sellers of  the same good is a class. However, for a buyer there is no  bijection between the different the procurement sets of the  bundles of goods the buyer is interested in.  The spatial-distributed market with strategic edges (see  problem B.6) is not a class-based domain (and therefore not  a procurement-class domain). For example, even for a fixed  buyer and a fixed seller there are two different procurement  sets consisting of different paths between the buyers and   sellers.  The next sections present two algorithms GTR-1 and   GTR2. GTR-1 accepts problems in procurement-class based   domains, its properties are proved with a general dividing   function D. The GTR-2 algorithm accepts problems in any   domain. We prove the GTR-2"s properties with specific   dividing function D0. The function will be defined in section  4. Since the dividing function can have a large practical  impact on welfare (and revenue) the generality of GTR − 1  (albeit in special domains) can be an important practical  consideration.  3. PROCUREMENT-CLASS BASED  DOMAINS  This section focuses on the problems that are   procurementclass based domains. For this domain, we present an   algorithm called GTR-1, which given a mechanism that is IR  and IC outputs a mechanism with reduced welfare which is  IR, IC and budget balanced.  Although procurement class domains appear to be a   relatively restricted model, in fact many domains studied in the  literature are procurement class domains.  Example 3.1. The following domains are procurement  class domains:  • double-sided auctions with homogenous goods   [13](problem B.1). In this domain there are two classes. The  class of buyers and the class of sellers. Each   procurement set consists of a single buyer and a single seller.  Since every pair of (buyer, seller) is a valid   procurement set (albeit possible with negative value) this is a  procurement class domain. In this domain the constant  assigned to the procurement sets is F = 0.  • Spatially distributed markets with non strategic edges  [3, 9](problem B.3). Like the double-sided auctions  with homogenous goods, their are two classes in the   domain. Class of buyers and class of sellers with   procurement sets consisting of single buyer and single seller.  The sellers and buyers are nodes in a graph and the  function F is the distance of two nodes (length of the  edge) which represent transport costs. These costs   differ between different (buyer, seller) pairs.  • Supply chains [2, 4] (problem B.5). The assumption  of unique manufactory by [2, 4] can best be understood  as turning general supply chains (which need not be  a procurement class domain) into a procurement class  domain.  • Single minded combinatorial auctions [11] (problem B.8).  In this context each seller sells a single good and each  buyer wants a set of goods. The classes are the sets of  sellers selling the same good as well as the buyers who  desire the same bundle. A procurement set consists of  a single buyer as well as a set of sellers who can satisfy  that buyer.  A definition of the mechanism follows:  Definition 3.1. The GTR-1 algorithm - given a   mechanism M, a set X ⊂ N which is closed under replacement,  a dividing function D, and allocation A, GTR-1 operates as  follows:  1. Use the dividing function D to divide A into   procurement sets s1, . . . , sk ∈ S.  2. Order the procurement sets by increasing value.  3. For each sj, starting from the lowest value procurement  set:  If for every i ∈ sj ∩ X there is external competition  and every i ∈ sj \ X there is internal competition then  23  keep sj. Otherwise reduce the trade sj (i.e., remove  every i ∈ sj from the allocation).6  4. All trading players are charged the critical value for  trading. All non trading players are charged nothing.  Remark 3.1. The special case where X = N has received  attention under different guises in various special cases, such  as ([13, 3, 4]).  3.1 The GTR-1 Produces an X-external  Mechanism that is IR, IC and BB  In this subsection we prove that the GTR-1 algorithm  produces an X-external mechanism that is IR, IC and BB.  To prove GTR-1"s properties we make use of theorem 3.1  which is a well known result (e.g., [14, 11]). Theorem 3.1  characterizes necessary and sufficient conditions for a   mechanism for single value players to be IR and IC:  Definition 3.2. An allocation rule R is Bid Monotonic  if for any player i, any bids of the other players b−i ∈ V−i,  and any two possible bids of i, ˆbi > bi, if i trades under the  allocation rule R when reporting bi, then i also trades when  reporting ˆbi.  Intuitively, a bid monotonic allocation rule ensures that  no trading player can become a non-trading player by   improving his bid.  Theorem 3.1. An IR mechanism M with allocation rule  R is IC if and only if R is Bid Monotonic and each trading  player i pays his critical value Ci (pi = Ci).  So for normalized IR7  and IC mechanisms, the allocation  rule which is bid monotonic uniquely defines the critical   values for all the players and thus the payments.  Observation 3.1. Let M1 and M2 be two IR and IC  mechanisms with the same allocation rule. Then M1 and  M2 must have the same payment rule.  In the following we prove that the X-external GTR-1   algorithm produces a IR, IC and BB mechanism, but first a  subsidiary lemma is shown.  Lemma 3.1. For procurement class domains if there   exists a procurement set sj s.t. i ∈ sj and i has external  competition than all t = i t ∈ sj, t has internal competition.  Proof. This follows from the definition of procurement  class domains. Suppose that i has external competition,  then there exists a set of players Ei(A, s) such that {i} ∪  Ei(A, s) ∈ S. Let us denote by sj = {i} ∪ Ei(A, s). Since  the domain is a procurement-class domain there exists a   bijection function f between sj and sj. f defines the required  internal competition.  We start by proving IR and IC:  6  Although the definition of an X-external mechanism   requires that X intersects every procurement set, this is not  strictly necessary. It is possible to define an X that does  not intersect every possible procurement set. In this case,  any procurement set s ∈ S s.t. s ∩ X = ∅ will be reduced.  7  Note that this is not true for mechanisms which are not  normalized e.g., [7, 12]  Lemma 3.2. For any X, the X-external mechanism with  a critical value pricing scheme produced by the GTR-1   algorithm is an IR and IC mechanism.  Proof. By the definition of a critical value pricing scheme  2.2 and the GTR-1 algorithm 3.1 it follows that for every  trading player i, vi ≥ 0. By the GTR-1 algorithm 3.1   nontrading players i have a payment of zero. Thus for every  player i, value vi, and any b−i ∈ V−i ui(vi, b−i) ≥ 0,   meaning the produced X-external mechanism is IR.  As the X-external GTR-1 algorithm is IR and applies  the critical value payment scheme according to theorem 3.1,  in order to show that the produced X-external mechanism  with the critical value payment scheme is IC, it remains to  show that the produced mechanism"s allocation rule is bid  monotonic.  Since GTR-1 orders the procurement sets according to   increasing value, if player i increases his bid from bi to bi > bi  then for any division function D of procurement sets, the  procurement set s containing i always appears later with  the bid bi than with the bid bi. So the likelihood of   competition can only increase if i appears in later procurement  sets. This follows as GTR-1 can reduce more of the lower  value procurement sets which will result in more non-trading  players.  Therefore if s has the required competition and is not  reduced with bi then it will have the required competition  with bi and will not be reduced.  Finally we prove BB:  Lemma 3.3. For any X, the X-external mechanism with  critical value pricing scheme produced by the GTR-1   algorithm is a BB mechanism.  Proof. In order to show that the produced mechanism is  BB we show that each procurement set that is not reduced  has a positive budget (i.e., the sum of payments is positive).  Let s ∈ S be a procurement set that is not reduced. Let  i ∈ s ∩ X then according to the definition of X-external  definition 2.7 and the GTR-1 algorithm 3.1 i has an external  competition. Assume w.l.o.g.8  that i is the only player with  external competition in s and all other players j = i, j ∈ s  have internal competition.  Let A be the allocation after the procurement sets   reduction by the GTR-1 algorithm. According to the definition of  external competition 2.5, there exists a set Ei(A, s) ⊂ N \A  such that i ∪ Ei(A, s) ∈ S and W(i ∪ Ei(A, s)) ≥ 0. Since  W(i∪Ei(A, s)) = vi +W(Ei(A, s)) then vi ≥ −W(Ei(A, s)).  By the critical value pricing scheme definition 2.2 it means  that if player i bids any less than −W(Ei(A, s)) he will  not have external competition and therefore will be removed  from trading. Thus i pays no less than min −W(Ei(A, s)).  Since all other players j ∈ s have internal competition their  critical price can not be less than their maximal value   internal competitor (set) i.e., max W(Rj(A, s)). If any player  j ∈ s bids less then its maximal internal competitor (set)  then he will not be in s but his maximal internal competitor  (set) will.  As a possible Ei(A, s) is ∪j∈sRj(A, s) one can bound the  maximal value of i"s external competition W(Ei(A, s)) by  the sum of the maximal values of the rest of the players in s  8  since the domain is a procurement class domain we can use  lemma 3.1  24  internal competition i.e., j∈s max W(Rj(A, s)). Therefore  min −W(Ei(A, s)) = −( j∈s max W(Rj(A, s))). As the F  function is defined to be a positive constant we get that  W(s) = min −W(Ei(A, s))+( j∈s max W(Rj(A, s)))+F(s) ≥  0 and thus s is at least budget balanced. As each   procurement set that is not reduced is at least budget balanced, it  follows that the produced X-external mechanism is BB.  The above two lemmas yield the following theorem:  Theorem 3.2. For procurement class domains for any  X, the X-external mechanism with critical value pricing  scheme produced by the GTR-1 algorithm is an IR, IC and  BB mechanism.  Remark 3.2. The proof of the theorem yields bounds on  the payments any player has to make to the mechanism.  4. NON PROCUREMENT-CLASS BASED  DOMAINS  The main reason that GTR-1 works for the   procurementclass domains is that each player"s possibility of being   reduced is monotonic. By the definition of a dividing function  if a player i ∈ sj increases his value, i can only appear in  later procurement set sj and hence has a higher chance of  having the desired competition.  Therefore, the chance of i lacking the requisite   competition is decreased. Since the domain is a procurement class  domain, all other players t = i,t ∈ sj are also more likely  to have competition since members of their class continue  to appear before i and hence the likelihood that i will be  reduced is decreased. Since by theorem 3.1 a necessary and  sufficient condition for the mechanism to be IC is   monotonicity. GTR-1 is IC for procurement-class domains.  However, for domains that are not procurement class   domains this does not suffice even if the domain is a class based  domain. Although, all members of sj continue to have the  required competition it is possible that there are members of  sj who do not have analogues in sj who do not have   competition. Hence i might be reduced after increasing his value  which by lemma 3.1 means the mechanism is not IC.  We therefore define a different algorithm for non   procurement class domains.  Our modified algorithm requires a special dividing   function in order to maintain the IC property. Although our  restriction to this special dividing function appears   stringent, the dividing function we use is a generalization of the  way that procurement sets are chosen in procurement-class  based domains e.g., [13, 16, 9, 3, 2, 4].  For ease of presentation in this section we assume that  F = 0.  The dividing function for general domains is defined by  looking at all possible dividing functions. For each   dividing function Di and each set of bids, the GTR-1 algorithm  yields a welfare that is a function of the bids and the   dividing function9  . We denote by D0 the dividing function that  divides the players into sets s.t. the welfare that GTR-1  finds is maximal10  .  9  Note that for any particular Di this might not be IC as  GTR-1 is IC only for procurement class domains and not  for general domains  10  In Appendix A we show how to calculate D0 in   polynoFormally,  Let D be the set of all dividing functions D. Denote  the welfare achieved by the mechanism produced by   GTR1 when using dividing function D and a set of bids ¯b by  GTR1(D,¯b). Denote by D0(¯b) = argmaxD∈D(GTR1(D,¯b)).  For ease of presentation we denote D0(¯b) by D0 when the  dependence on b is clear from the context.  Remark 4.1. D0 is an element of the set of dividing   functions, and therefore is a dividing function.  The second generalized trade reduction algorithm GTR-2  follows.  Definition 4.1. The GTR-2 algorithm - Given   mechanism M, allocation A, and a set X ⊂ N closed under   replacement, GTR-2 operates as follows:  1. Calculate the dividing function D0 as defined above.  2. Use the dividing function D0 to divide A into   procurement sets s1, . . . , sk ∈ S.  3. For each sj, starting from the lowest value   procurement set, do the following:  If for i ∈ sj ∩ X there is an external competition and  there is at most one i ∈ sj that does not have an   internal competition then keep sj. Otherwise, reduce the  trade sj.  4. All trading players are charged the critical value for  trading. All non trading players are charged zero.  11  We will prove that the mechanism produced by GTR-2  maintains the desired properties of IR, IC, and BB. The   following lemma shows that the GTR-2 produced mechanism  is IR, and IC.  Lemma 4.1. For any X, the X-external mechanism with  critical value pricing scheme produced by the GTR-2   algorithm is an IR and IC mechanism.  Proof. By theorem 3.1 it suffices to prove that the   produced mechanism by the GTR-2 algorithm is bid monotonic  for every player i. Suppose that i was not reduced when   bidding bi we need to prove that i will not be reduced when   bidding bi > bi. Denote by D1 = D0(b) the dividing function  used by GTR-2 when i reported bi and the rest of the   players reported b−i. Denote by D1 = D0(bi, b−i) the dividing  function used by GTR-2 when i reported bi and the rest of  the players reported b−i. Denote by ¯D1(b) a maximal   dividing function that results in GTR-1 reducing i when   reporting bi. Assume to the contrary that GTR-2 reduced i from  the trade when i reported bi then GTR1(D1, (bi, b−i)) =  GTR1( ¯D1, b). Since D1 ∈ D it follows that GTR1(D1, b) >  GTR1( ¯D1, b) and therefore  GTR1(D1, b) > GTR1(D1, (bi, b−i)). However according to  the definition D1 ∈ D, GTR-2 should not have reduced i  mial time for procurement-class domains. Calculating D0 in  polynomial time for general domains is an important open  problem.  11  In the full version GTR-2 is extend such that it suffices  that there exists some time in which the third step holds.  That extension is omitted from current version due to lack  of space.  25  with the dividing function D1 and gained a greater welfare  than GTR1(D1, b). Thus a contradiction arises and and  GTR-2 does not reduce i from the trade when i reports  bi > bi.  Lemma 4.2. For any X, the X-external mechanism with  critical value pricing scheme produced by the GTR-2   algorithm is a BB mechanism.  Proof. This proof is similar to the proof of lemma 3.3.  Combining the two lemmas above we get:  Theorem 4.1. For any X closed under replacement, the  X-external mechanism with critical value pricing scheme  produced by the GTR-2 algorithm is an IR, IC and BB   mechanism.  Appendix A shows how to calculate D0 for procurement  class domains in polynomial time, it is not generally known  how to easily calculate D0. Creating a general method for  calculating the needed dividing function in polynomial time  remains as an open question.  4.1 Bounding the Welfare for   ProcurementClass Based Domains and other General  Domains Cases  This section shows that in addition to producing a   mechanism with the desired properties, GTR-2 also produces a  mechanism that maintains high welfare. Since the GTR-2  algorithm finds a budget balanced mechanism in arbitrary  domains we are unable to bound the welfare for general  cases. However we can bound the welfare for   procurementclass based domain and a wide variety of cases in general  domains which includes many cases previously studied.  Definition 4.2. Denote freqk([i], sj) to indicate that a  class [i] appears in a procurement set sj, k times and there  are k members of [i] in sj.  Definition 4.3. Denote by freqk([i], S) the maximal k  s.t. there are k members of [i] in sj. I.e., freqk([i], S) =  maxsj ∈S freqk([i], sj).  Let the set of equivalence classes in procurement class  based domain mechanism be ec and |ec| be the number of  those equivalence classes.  Using the definition of class appearance frequency we can  bound the welfare achieved by the GTR-2 produced   mechanism for procurement class domains12  :  Lemma 4.3. For procurement class domains with F = 0,  the number of procurement sets that are reduced by GTR-213  is at most |ec| times the maximal frequency of each class.  Formally, the maximal number of procurement sets that is  reduced is O( [i]∈ec  freqk([i], S))  Proof. Let D be an arbitrary dividing function. We  note that by definition any procurement set sj will not be  reduced if every i ∈ sj has both internal competition and  external competition.  12  The welfare achieved by GTR-1 can also be bounded for  the cases presented in this section. However, we focus on  GTR-2 as it always achieves better welfare.  13  or GTR-1  Every procurement set s that is reduced has at least one  player i who has no competition. Once s is reduced all  players of [i] have internal competition. So by reducing the  number of equivalence classes |ec| procurement sets we cover  all the remaining players with internal competition.  If the maximal frequency of every equivalence classes was  one then each remaining player t in procurement set sk also  have external competition as all the internal competitors of  players ¯t = t, ¯t ∈ sk are an external competition for t.  If we have freqk([t], S) players from class [t] who were  reduced then there is sufficient external competition for all  players in sk.  Therefore it suffices to reduce O( [i]∈ec  freqk([i], S))   procurement sets in order to ensure that both the requisite   internal and external competition exists.  The next theorem follows as an immediate corollary for  lemma 4.3:  Theorem 4.2. Given procurement-class based domain   mechanisms with H procurement sets, the efficiency is at least a  1 − O(  O( [i]∈ec  freqk([i],S))  H  ) fraction of the optimal welfare.  The following corollaries are direct results of theorem 4.2.  All of these corollaries either improve prior results or achieve  the same welfare as prior results.  Corollary 4.1. Using GTR-2 for homogenous   doublesided auctions (problem B.1) at most14  one procurement set  must be reduced.  Similarly, for spatially distributed markets without   strategic edges (problem B.3) using GTR-2 improves the result of  [3] where a minimum cycle including a buyer and seller is  reduced.  Corollary 4.2. Using GTR-2 for spatially distributed  markets without strategic edges at most one cycle per   connected component15  will be reduced.  For supply chains (problem B.5) using GTR-2 improves  the result of [2, 4] similar to corollary 4.2.  Corollary 4.3. Using GTR-2 for supply chains at most  one cycle per connected component16  will be reduced.  The following corollary solves the open problem at [3].  Corollary 4.4. For distributed markets on n nodes with  strategic agents and paths of bounded length K (problem B.6)  it suffices to remove at most K ∗ n procurements sets.  Proof. Sketch: These will create at least K spanning  trees, hence we can disjointly cover every remaining   procurement set. This improves the naive algorithm of reducing n2  procurement sets.  We provide results for two special cases of double sided  CA with single value players (problem B.8).  14  It is possible that no reductions will be made, for instance  when there is a non-trading player who is the requisite   external competition.  15  Similar to the double-sided auctions, sometimes there will  be enough competition without a reduction.  16  Similar to double-sided auctions, sometimes there will be  enough competition without a reduction.  26  Corollary 4.5. if there are at most M different kinds of  procurement sets it suffices to remove M procurement sets.  Corollary 4.6. If there are K types of goods and each  procurement set consists of at most one of each type it   suffices to remove at most K procurement sets.  5. CONCLUSIONS AND FUTURE WORK  In this paper we presented a general solution procedure  called the Generalized Trade Reduction (GTR). GTR   accepts an IR and IC mechanism as an input and outputs  mechanisms that are IR, IC and BB. The output   mechanisms achieves welfare that is close to optimal for a wide  range of domains.  The GTR procedure improves on existing results such  as homogeneous double-sided auctions, distributed markets,  and supply chains, and solves several open problems such as  distributed markets with strategic transportation edges and  bounded paths, combinatorial double-sided auctions with  bounded size procurements sets, and combinatorial   doublesided auctions with a bounded number of procurement sets.  The question of the quality of welfare approximation both  in general and in class domains that are not procurement  class domains is an important and interesting open   question. We also leave open the question of upper bounds for  the quality of approximation of welfare. Although we know  that it is impossible to have IR, IC and BB in an efficient  mechanism it would be interesting to have an upper bound  on the approximation to welfare achievable in an IR, IC and  BB mechanism.  The GTR procedure outputs a mechanism which depends  on a set X ⊂ N. Another interesting question is what the  quality of approximation is when X is chosen randomly from  N before valuations are declared.  Acknowledgements  The authors wish to thank Eva Tardos et al for sharing their  results with us. The authors also wish to express their   gratitude to the helpful comments of the anonymous reviewers.  6. REFERENCES  [1] A. Archer and E. Tardos. Frugal path mechanisms.  Symposium on Discrete Algorithms, Proceedings of the  thirteenth annual ACM-SIAM symposium on Discrete  algorithms,2002.  [2] M. Babaioff and N. Nisan. Concurrent Auctions  Across the Supply Chain. Journal of Artificial  Intelligence Research,2004.  [3] Babaioff M., Nisan N. and Pavlov E. Mechanisms for  a Spatially Distributed Market. In proceedings of the  5th ACM Conference on Electronic Commerce,2004.  [4] M. Babaioff and W. E. Walsh. Incentive-Compatible,  Budget-Balanced, yet Highly Efficient Auctions for  Supply Chain Formation. In proceedings of Fourth  ACM Conference on Electronic Commerce,2003.  [5] Y. Bartal, R. Gonen and P. La Mura.  Negotiation-range mechanisms: exploring the limits of  truthful efficient markets. EC "04: Proceedings of the  5th ACM conference on Electronic commerce, 2004.  [6] Blume L, Easley D., Kleinberg J. and Tardos E.  Trading Networks with Price-Setting Agents. In  proceedings of the 8th ACM conference on Electronic  commerce,2007.  [7] Cavallo R. Optimal decision-making with minimal  waste: Strategyproof redistribution of VCG payments.  In Proc. 5th Int. Conf. on Auton. Agents and  Multi-Agent Systems (AAMAS06).  [8] E. H. Clarke Multipart Pricing of Public Goods. In  journal Public Choice 1971, vol. 2, pp. 17-33.  [9] Chu L. Y. and Shen Zuo-Jun M. Agent Competition  Double Auction Mechanism. Management Science,vol  52(8),2006.  [10] T. Groves Incentives in teams. In journal  Econometrica 1973, vol. 41, pp. 617-631.  [11] D. Lehmann, L. I. O"Callaghan, and Y. Shoham.  Truth Revelation in Approximately Efficient  Combinatorial Auctions. In Journal of ACM 2002,  vol. 49(5), pp. 577-602.  [12] Leonard H. Elicitation of Honest Preferences for the  Assignment of Individuals to Positions. Journal of  political econ,1983.  [13] McAfee R. P. A Dominant Strategy Double Auction.  Journal of Economic Theory,vol 56, 434-450, 1992.  [14] A. Mu"alem, and N. Nisan. Truthful Approximation  Mechanisms for Restricted Combinatorial Auctions.  Proceeding of AAAI 2002.  [15] Myerson R. B. and Satterthwaite M. A. Efficient  Mechanisms for Bilateral Trading. Journal of  Economic Theory,vol 29, 265-281, 1983.  [16] Roundy R., Chen R., Janakriraman G. and Zhang R.  Q. Efficient Auction Mechanisms for Supply Chain  Procurement. School of Operations Research and  Industrial Engineering, Cornell University,2001.  [17] W. Vickrey Counterspeculation, Auctions and  Competitive Sealed Tenders. In Journal of Finance  1961, vol. 16, pp. 8-37.  APPENDIX  A. CALCULATING THE  OPTIMAL DIVIDING FUNCTION IN  PROCUREMENT CLASS DOMAINS IN  POLYNOMIAL TIME  In this section we show how to calculate the optimal   dividing function for procurement class domains in polynomial  time. We first define a special dividing function D0 which  is easy to calculate:  We define the dividing function D0 recursively as follows:  At stage j, D0 divides the trading players into two sets Aj  and Aj s.t.  • Aj is a procurement set  • Aj can be divided into a disjoint union of procurement  sets.  • Aj has minimal value from all possible such partitions.  Define sj = Aj and recursively invoke D0 and Aj until  Aj = ∅.  We now prove that D0 is the required dividing function.  Lemma A.1. For procurement class domains D0 = D0.  Proof. Since the domain is a procurement class domain,  for every reduced procurement set the set of players which  achieve competition (either internal or external) is fixed.  27  Therefore, the number of procurement sets which are   reduced is independent of the dividing function D. Since  the goal is to optimize welfare by reducing procurement  sets with the least value we can optimize welfare. This is  achieved by D0.  B. PROBLEMS AND EXAMPLES  For completeness we present in this section the formal   definitions of the problems that we use to illustrate our   mechanism.  The first problem that we define is the double-sided   auction with homogeneous goods.  Problem B.1. Double-sided auction with   homogeneous goods: There are m sellers each of which have a  single good (all goods are identical) and n buyers each of  which are interested in receiving a good. We denote the set  of sellers by S and the set of buyers by B. Every player  i ∈ S ∪ B (both buyers and sellers) has a value vi for the  good. In this model a procurement set consists of a single  buyer and a single seller, i.e., |s| = 2. The value of a   procurement set is W(s) = vj − vi where j ∈ B and i ∈ S, i.e.,  the gain from trade.  If procurement sets are created by matching the highest  value buyer to the lowest value seller then [13]"s   deterministic trade reduction mechanism17  reduces the lowest value  procurement set.  A related model is the pair related costs [9] model.  Problem B.2. The pair related costs: A double-sided  auction B.1 in which every pair of players i ∈ S and j ∈ B  has a related cost F(i, j) ≥ 0 in order to trade. F(i, j) is a  friction cost which should be minimized in order to maximize  welfare.  [9] defines two budget-balanced mechanisms for this case.  One of [9]"s mechanisms has the set of buyers B as the X  set for the X-external mechanism and the other has the set  of sellers S as the X set for the X-external mechanism.  A similar model is the spatially distributed markets (SDM)  model [3] in which there is a graph imposing relationships  on the cost.  Problem B.3. Spatially distributed markets: there  is a graph G = (V, E) such that each v ∈ V has a set of  sellers Sv  and a set of buyers Bv  . Each edge e ∈ E has an  associated cost which is the cost to transport a single unit  of good along the edge. The edges are non strategic but all  players are strategic.  [3] defines a budget balanced mechanism for this case. Our  paper improves on [3] result.  Another graph model is the model defined in [6].  Problem B.4. Trading Networks: Given a graph and  buyers and sellers who are situated on nodes of the graph.  All trade must pass through a trader. In this case   procurement sets are of the form (buyer, seller, trader) where the  possible sets of this form are defined by a graph.  The supply chain model [2, 4] can be seen as a   generalization of [6] in which procurement sets consist of the form  (producer, consumer, trader1, . . . , traderk).  17  It is also possible to randomize the reduction of   procurements sets so as to achieve an expected budget of zero similar  to [13], details are obvious and omitted.  Problem B.5. Supply Chain: There is a set D of agents  and a set G of goods and a graph G = (V, E) which defines  possible trading relationships. Agents can require an input of  multiple quantities of goods in order to output a single good.  The producer type of player can produce goods out of   nothing, the consumer has a valuation and an entire chain of  interim traders is necessary to create a viable procurement  set.  [2, 4] consider unique manufacturing technology in which the  graph defining possible relationships is a tree.  All of the above problems are procurement-class domains.  We also consider several problems which are not   procurement class domains and generally the questions of budget  balance have been left as open problems.  An open problem raised in [3] is the SDM model in which  edges are strategic.  Problem B.6. Spatially distributed markets with  strategic edges: there is a graph G = (V, E) such that  each v ∈ V has a set of sellers Sv  and a set of buyers  Bv  . Each edge e ∈ E has an associated cost which is the  cost to transport a single unit of good along the edge. Each  buyer,seller and edge has a value for the trade, i.e., all   entities are strategic.  [2, 4] left open the question of budget balanced   mechanisms for supply chains where there is no unique   manufacturing technology. It is easy to see that this problem is not  a procurement class domain.  Another interesting problem is transport networks.  Problem B.7. Transport networks: A graph G = (V, E)  where the edges are strategic players with costs and the goal  is to find a minimum cost transportation route between a  pair of privileged nodes Source, Target ∈ V .  It was shown in [1] that the efficient allocation can have  a budget deficit that is linear in the number of players.  Clearly, this problem is not a procurement class domain and  [1] left the question of a budget balanced mechanism open.  Another non procurement-class based domain mechanism  is the double-sided combinatorial auction (CA) with   singlevalue players.  Problem B.8. Double-sided combinatorial auction  (CA) with single value players: There exists a set S of  sellers each selling a single good. There also exists a set B  of buyers each interested in bundles of 2S18  .  There are two variants of this problem. In the single  minded case each buyer has a positive value for only a   single subset whereas in the multi minded case each buyer can  have multiple bundles with positive valuation but all of the  values are the same. In both cases we assume free disposal  so that all bundles containing the desired bundle have the  same value for the buyer.  We also consider problems that are non class domains.  Problem B.9. Double-sided combinatorial auction  (CA) with general multi-minded players: same as B.8  but each buyer can have multiple bundles with positive   valuation which are not necessarily the same.  18  We abuse notation and identify the seller with the good.  28  C. COMPARING DIFFERENT CHOICES  OF X  The choice of X can have a large impact on the welfare  (and revenue) of the reduced mechanism and therefore the  question arises of how one should choose the set X.  As the X-external mechanism is required to maintain IC  clearly the choice of X can not depend on the value of  the players as otherwise the reduced mechanism will not  be truthful.  In this section we motivate the choice of small X sets for  procurement class domains and give intuition that it may  also be the case for some other domains.  We start by illustrating the effect of the set X over the  welfare and revenue in the double-sided auction with   homogeneous goods problem B.1. Similar examples can be  constructed for the other problems defined is B.  The following example shows an effect on the welfare.  Example C.1. There are two buyers and two sellers and  two non intersecting (incomparable) sets X = {buyers} and  Y = {sellers}. If the values of the buyers are 101, 100 and  the sellers are 150, 1 then the X-external mechanism will  yield a gain from trade of 0 and the Y -external mechanism  will yield a gain from trade of 100.  Conversely, if the buyers values are 100, 1 and the sellers  are 2, 3 the X-external mechanism will yield a gain from  trade of 98 and and the Y -external mechanism will yield a  gain from trade of zero.  The example clearly shows that the difference between  the X-external and the Y -external mechanism is unbounded  although as shown above the fraction each of them reduces  can be bound and therefore the multiplicative ratio between  them can be bound (as a function of the number of trades).  On the revenue side we can not even bound the ratio as  seen from the following example:  Example C.2. Consider k buyers with value 100 and k+  1 sellers with value 1.  If X = {buyers} then there is no need to reduce any trade  and all of the buyer receive the good and pay 1. k + 1 of  the sellers sell and each of them receive 1. This yields a net  revenue of zero.  If Y = {sellers} then one must reduce a trade! This  means that all of the buyers pay 100 while all of the   sellers still receive 1. the revenue is then 99k.  Similarly, an example can be constructed that yields much  higher revenue for the X-external mechanism as compared  to the Y -external mechanism.  The above examples refer to sets X and Y which do not  intersect and are incomparable. The following theorem   compares the X-external and Y -external mechanisms for   procurement class domains where X is a subset of Y .  Theorem C.1. For procurement class domains, if X ⊂  Y and for any s ∈ S, s ∩ X ∩ Y = ∅ then:  1. The efficiency of the X external mechanism in GTR-1  (and hence GTR-2) is at least that of the Y -external  mechanism.  2. Any winning player that wins in both the X-external  and Y -external mechanisms pays no less in the Y -external  than in the X-external and therefore the ratio of   budget to welfare is no worse in the Y external then the  X-external.  Proof. 1. For any dividing function D if there is a  procurement set sj that is reduced in the X-external  mechanism there are two possible reasons:  (a) sj lacks external competition in the X-external   mechanism. In this case sj lacks external competition  in the internal mechanism.  (b) sj has all required external competitions in X-external.  In this case sj has all required internal   competitions in Y -external by lemma 3.1 but might lack  some external competition for sj ∪ {Y \ X} and be  reduced,  2. This follows from the fact that for any ordering D any  procurement set s that is reduced in the X-external  mechanism is also reduced in the Y -external   mechanism. Therefore, the critical value is no less in the   Yexternal mechanism than the X-external mechanism.  Remark C.1. For any two sets X, Y it is easy to build  an example in which the X-external and Y -external   mechanisms reduce the same procurement sets so the inequality is  weak.  Theorem C.1 shows an inequality in welfare as well as for  payments but it is easy to construct an example in which  the revenue can increase for X as compared to Y as well as  the opposite. This suggests that in general we want X to  be as small as possible although in some domains it is not  possible to compare different X"s.  29