Frugality Ratios And Improved Truthful Mechanisms for  Vertex Cover  ∗  Edith Elkind  Hebrew University of  Jerusalem, Israel, and  University of Southampton,  Southampton, SO17 1BJ, U.K.  Leslie Ann Goldberg  University of Liverpool  Liverpool L69 3BX, U.K.  Paul Goldberg  University of Liverpool  Liverpool L69 3BX, U.K.  ABSTRACT  In set-system auctions, there are several overlapping teams of agents,  and a task that can be completed by any of these teams. The   auctioneer"s goal is to hire a team and pay as little as possible.   Examples of this setting include shortest-path auctions and vertex-cover  auctions. Recently, Karlin, Kempe and Tamir introduced a new   definition of frugality ratio for this problem. Informally, the frugality  ratio is the ratio of the total payment of a mechanism to a desired  payment bound. The ratio captures the extent to which the   mechanism overpays, relative to perceived fair cost in a truthful auction.  In this paper, we propose a new truthful polynomial-time auction  for the vertex cover problem and bound its frugality ratio. We show  that the solution quality is with a constant factor of optimal and  the frugality ratio is within a constant factor of the best possible  worst-case bound; this is the first auction for this problem to have  these properties. Moreover, we show how to transform any   truthful auction into a frugal one while preserving the approximation  ratio. Also, we consider two natural modifications of the definition  of Karlin et al., and we analyse the properties of the resulting   payment bounds, such as monotonicity, computational hardness, and  robustness with respect to the draw-resolution rule. We study the  relationships between the different payment bounds, both for   general set systems and for specific set-system auctions, such as path  auctions and vertex-cover auctions. We use these new definitions  in the proof of our main result for vertex-cover auctions via a   bootstrapping technique, which may be of independent interest.  Categories and Subject Descriptors  F.2 [Theory of Computation]: Analysis of Algorithms and   Problem Complexity; J.4 [Computer Applications]: Social and   Behavioral Sciences-economics    1. INTRODUCTION  In a set system auction there is a single buyer and many vendors  that can provide various services. It is assumed that the buyer"s   requirements can be satisfied by various subsets of the vendors; these  subsets are called the feasible sets. A widely-studied class of   setsystem auctions is path auctions, where each vendor is able to sell  access to a link in a network, and the feasible sets are those sets  whose links contain a path from a given source to a given   destination; the study of these auctions has been initiated in the seminal  paper by Nisan and Ronen [19] (see also [1, 10, 9, 6, 15, 7, 20]).  We assume that each vendor has a cost of providing his services,  but submits a possibly larger bid to the auctioneer. Based on these  bids, the auctioneer selects a feasible subset of vendors, and makes  payments to the vendors in this subset. Each selected vendor enjoys  a profit of payment minus cost. Vendors want to maximise profit,  while the buyer wants to minimise the amount he pays. A natural  goal in this setting is to design a truthful auction, in which vendors  have an incentive to bid their true cost. This can be achieved by  paying each selected vendor a premium above her bid in such a  way that the vendor has no incentive to overbid. An interesting  question in mechanism design is how much the auctioneer will have  to overpay in order to ensure truthful bids.  In the context of path auctions this topic was first addressed by  Archer and Tardos [1]. They define the frugality ratio of a   mechanism as the ratio between its total payment and the cost of the  cheapest path disjoint from the path selected by the mechanism.  They show that, for a large class of truthful mechanisms for this  problem, the frugality ratio is as large as the number of edges in the  shortest path. Talwar [21] extends this definition of frugality ratio  to general set systems, and studies the frugality ratio of the classical  VCG mechanism [22, 4, 14] for many specific set systems, such as  minimum spanning trees and set covers.  While the definition of frugality ratio proposed by [1] is   wellmotivated and has been instrumental in studying truthful   mechanisms for set systems, it is not completely satisfactory. Consider,  for example, the graph of Figure 1 with the costs cAB = cBC =  A B  C  D  Figure 1: The diamond graph  336  cCD = 0, cAC = cBD = 1. This graph is 2-connected and the  VCG payment to the winning path ABCD is bounded. However,  the graph contains no A-D path that is disjoint from ABCD, and  hence the frugality ratio of VCG on this graph remains undefined.  At the same time, there is no monopoly, that is, there is no   vendor that appears in all feasible sets. In auctions for other types of  set systems, the requirement that there exist a feasible solution   disjoint from the selected one is even more severe: for example, for  vertex-cover auctions (where vendors correspond to the vertices of  some underlying graph, and the feasible sets are vertex covers) the  requirement means that the graph must be bipartite. To deal with  this problem, Karlin et al. [16] suggest a better benchmark, which  is defined for any monopoly-free set system. This quantity, which  they denote by ν, intuitively corresponds to the value of a cheapest  Nash equilibrium. Based on this new definition, the authors   construct new mechanisms for the shortest path problem and show that  the overpayment of these mechanisms is within a constant factor of  optimal.  1.1 Our results  Vertex cover auctions We propose a truthful polynomial-time  auction for vertex cover that outputs a solution whose cost is within  a factor of 2 of optimal, and whose frugality ratio is at most 2Δ,  where Δ is the maximum degree of the graph (Theorem 4). We  complement this result by proving (Theorem 5) that for any Δ and  n, there are graphs of maximum degree Δ and size Θ(n) for which  any truthful mechanism has frugality ratio at least Δ/2. This means  that the solution quality of our auction is with a factor of 2 of   optimal and the frugality ratio is within a factor of 4 of the best   possible bound for worst-case inputs. To the best of our knowledge,  this is the first auction for this problem that enjoys these   properties. Moreover, we show how to transform any truthful mechanism  for the vertex-cover problem into a frugal one while preserving the  approximation ratio.  Frugality ratios Our vertex cover results naturally suggest two  modifications of the definition of ν in [16]. These modifications  can be made independently of each other, resulting in four   different payment bounds TUmax, TUmin, NTUmax, and NTUmin,  where NTUmin is equal to the original payment bound ν of in [16].  All four payment bounds arise as Nash equilibria of certain games  (see the full version of this paper [8]); the differences between  them can be seen as the price of initiative and the price of   cooperation (see Section 3). While our main result about vertex  cover auctions (Theorem 4) is with respect to NTUmin = ν, we  make use of the new definitions by first comparing the payment of  our mechanism to a weaker bound NTUmax, and then   bootstrapping from this result to obtain the desired bound.  Inspired by this application, we embark on a further study of  these payment bounds. Our results here are as follows:  1. We observe (Proposition 1) that the four payment bounds   always obey a particular order that is independent of the choice of  the set system and the cost vector, namely, TUmin ≤ NTUmin ≤  NTUmax ≤ TUmax. We provide examples (Proposition 5 and  Corollaries 1 and 2) showing that for the vertex cover problem any  two consecutive bounds can differ by a factor of n − 2, where n is  the number of agents. We then show (Theorem 2) that this   separation is almost best possible for general set systems by proving that  for any set system TUmax/TUmin ≤ n. In contrast, we   demonstrate (Theorem 3) that for path auctions TUmax/TUmin ≤ 2.  We provide examples (Propositions 2, 3 and 4) showing that this  bound is tight. We see this as an argument for the study of   vertexcover auctions, as they appear to be more representative of the   general team -selection problem than the widely studied path auctions.  2. We show (Theorem 1) that for any set system, if there is a cost  vector for which TUmin and NTUmin differ by a factor of α,  there is another cost vector that separates NTUmin and NTUmax  by the same factor and vice versa; the same is true for the pairs  (NTUmin, NTUmax) and (NTUmax, TUmax). This   symmetry is quite surprising, since, e.g., TUmin and NTUmax are   obtained from NTUmin by two very different transformations. This  observation suggests that the four payment bounds should be   studied in a unified framework; moreover, it leads us to believe that the  bootstrapping technique of Theorem 4 may have other applications.  3. We evaluate the payment bounds introduced here with respect  to a checklist of desirable features. In particular, we note that the  payment bound ν = NTUmin of [16] exhibits some   counterintuitive properties, such as nonmonotonicity with respect to adding a  new feasible set (Proposition 7), and is NP-hard to compute   (Theorem 6), while some of the other payment bounds do not suffer from  these problems. This can be seen as an argument in favour of using  weaker but efficiently computable bounds NTUmax and TUmax.  Related work  Vertex-cover auctions have been studied in the past by Talwar [21]  and Calinescu [5]. Both of these papers are based on the definition  of frugality ratio used in [1]; as mentioned before, this means that  their results only apply to bipartite graphs. Talwar [21] shows that  the frugality ratio of VCG is at most Δ. However, since finding  the cheapest vertex cover is an NP-hard problem, the VCG   mechanism is computationally infeasible. The first (and, to the best of  our knowledge, only) paper to investigate polynomial-time truthful  mechanisms for vertex cover is [5]. This paper studies an auction  that is based on the greedy allocation algorithm, which has an   approximation ratio of log n. While the main focus of [5] is the more  general set cover problem, the results of [5] imply a frugality ratio  of 2Δ2  for vertex cover. Our results improve on those of [21] as  our mechanism is polynomial-time computable, as well as on those  of [5], as our mechanism has a better approximation ratio, and we  prove a stronger bound on the frugality ratio; moreover, this bound  also applies to the mechanism of [5].  2. PRELIMINARIES  In most of this paper, we discuss auctions for set systems. A  set system is a pair (E, F), where E is the ground set, |E| = n,  and F is a collection of feasible sets, which are subsets of E. Two  particular types of set systems are of interest to us - shortest path  systems, in which the ground set consists of all edges of a network,  and the feasible sets are paths between two specified vertices s and  t, and vertex cover systems, in which the elements of the ground set  are the vertices of a graph, and the feasible sets are vertex covers of  this graph.  In set system auctions, each element e of the ground set is owned  by an independent agent and has an associated non-negative cost ce.  The goal of the centre is to select (purchase) a feasible set. Each  element e in the selected set incurs a cost of ce. The elements that  are not selected incur no costs.  The auction proceeds as follows: all elements of the ground set  make their bids, the centre selects a feasible set based on the bids  and makes payments to the agents. Formally, an auction is defined  by an allocation rule A : Rn  → F and a payment rule P : Rn  →  Rn  . The allocation rule takes as input a vector of bids and decides  which of the sets in F should be selected. The payment rule also  takes as input a vector of bids and decides how much to pay to each  agent. The standard requirements are individual rationality, i.e.,  the payment to each agent should be at least as high as his incurred  cost (0 for agents not in the selected set and ce for agents in the  337  selected set) and incentive compatibility, or truthfulness, i.e., each  agent"s dominant strategy is to bid his true cost.  An allocation rule is monotone if an agent cannot increase his  chance of getting selected by raising his bid. Formally, for any bid  vector b and any e ∈ E, if e ∈ A(b) then e ∈ A(b1, . . . , be, . . . , bn)  for any be > be. Given a monotone allocation rule A and a bid  vector b, the threshold bid te of an agent e ∈ A(b) is the highest  bid of this agent that still wins the auction, given that the bids of  other participants remain the same. Formally, te = sup{be ∈ R |  e ∈ A(b1, . . . , be, . . . , bn)}. It is well known (see, e.g. [19, 13])  that any auction that has a monotone allocation rule and pays each  agent his threshold bid is truthful; conversely, any truthful auction  has a monotone allocation rule.  The VCG mechanism is a truthful mechanism that maximises  the social welfare and pays 0 to the losing agents. For set system  auctions, this simply means picking a cheapest feasible set, paying  each agent in the selected set his threshold bid, and paying 0 to  all other agents. Note, however, that the VCG mechanism may be  difficult to implement, since finding a cheapest feasible set may be  intractable.  If U is a set of agents, c(U) denotes  P  w∈U cw. Similarly, b(U)  denotes  P  w∈U bw.  3. FRUGALITY RATIOS  We start by reproducing the definition of the quantity ν from [16,  Definition 4].  Let (E, F) be a set system and let S be a cheapest feasible set  with respect to the true costs ce. Then ν(c, S) is the solution to the  following optimisation problem.  Minimise B =  P  e∈S be subject to  (1) be ≥ ce for all e ∈ E  (2)  P  e∈S\T be ≤  P  e∈T \S ce for all T ∈ F  (3) for every e ∈ S, there is a Te ∈ F such that e ∈ Te andP  e ∈S\Te  be =  P  e ∈Te\S ce  The bound ν(c, S) can be seen as an outcome of a two-stage  process, where first each agent e ∈ S makes a bid be stating how  much it wants to be paid, and then the centre decides whether to  accept these bids. The behaviour of both parties is affected by the  following considerations. From the centre"s point of view, the set  S must remain the most attractive choice, i.e., it must be among  the cheapest feasible sets under the new costs ce = ce for e ∈ S,  ce = be for e ∈ S (condition (2)). The reason for that is that  if (2) is violated for some set T, the centre would prefer T to S.  On the other hand, no agent would agree to a payment that does  not cover his costs (condition (1)), and moreover, each agent tries  to maximise his profit by bidding as high as possible, i.e., none  of the agents can increase his bid without violating condition (2)  (condition (3)). The centre wants to minimise the total payout, so  ν(c, S) corresponds to the best possible outcome from the centre"s  point of view.  This definition captures many important aspects of our intuition  about ‘fair" payments. However, it can be modified in two ways,  both of which are still quite natural, but result in different payment  bounds.  First, we can consider the worst rather than the best possible   outcome for the centre. That is, we can consider the maximum total  payment that the agents can extract by jointly selecting their bids  subject to (1), (2), and (3). Such a bound corresponds to   maximising B subject to (1), (2), and (3) rather than minimising it. If it  is the agents who make the original bids (rather than the centre),  this kind of bidding behaviour is plausible. On the other hand, in a  game in which the centre proposes payments to the agents in S and  the agents accept them as long as (1), (2) and (3) are satisfied, we  would be likely to observe a total payment of ν(c, S). Hence, the  difference between these two definitions can be seen as the price  of initiative.  Second, the agents may be able to make payments to each other.  In this case, if they can extract more money from the centre by  agreeing on a vector of bids that violates individual rationality (i.e.,  condition (1)) for some bidders, they might be willing to do so, as  the agents who are paid below their costs will be compensated by  other members of the group. The bids must still be realistic, i.e.,  they have to satisfy be ≥ 0. The resulting change in payments can  be seen as the price of co-operation and corresponds to replacing  condition (1) with the following weaker condition (1∗  ):  be ≥ 0 for all e ∈ E. (1∗  )  By considering all possible combinations of these modifications,  we obtain four different payment bounds, namely  • TUmin(c, S), which is the solution to the optimisation   problem Minimise B subject to (1∗  ), (2), and (3).  • TUmax(c, S), which is the solution to the optimisation   problem Maximise B subject to (1∗  ), (2), and (3).  • NTUmin(c, S), which is the solution to the optimisation  problem Minimise B subject to (1), (2), and (3).  • NTUmax(c, S), which is the solution to the optimisation  problem Maximise B subject to (1), (2), (3).  The abbreviations TU and NTU correspond, respectively, to   transferable utility and non-transferable utility, i.e., the agents"   ability/inability to make payments to each other. For concreteness,  we will take TUmin(c) to be TUmin(c, S) where S is the   lexicographically least amongst the cheapest feasible sets. We   define TUmax(c), NTUmin(c), NTUmax(c) and ν(c) similarly,  though we will see in Section 6.3 that, in fact, NTUmin(c, S) and  NTUmax(c, S) are independent of the choice of S. Note that the  quantity ν(c) from [16] is NTUmin(c).  The second modification (transferable utility) is more intuitively  appealing in the context of the maximisation problem, as both   assume some degree of co-operation between the agents. While the  second modification can be made without the first, the resulting  payment bound TUmin(c, S) is too strong to be a realistic   benchmark, at least for general set systems. In particular, it can be smaller  than the total cost of the cheapest feasible set S (see Section 6).  Nevertheless, we provide the definition as well as some results  about TUmin(c, S) in the paper, both for completeness and   because we believe that it may help to understand which properties  of the payment bounds are important for our proofs. Another   possibility would be to introduce an additional constraint  P  e∈S be ≥P  e∈S ce in the definition of TUmin(c, S) (note that this   condition holds automatically for TUmax(c, S), as TUmax(c, S) ≥  NTUmax(c, S)); however, such a definition would have no direct  game-theoretic interpretation, and some of our results (in   particular, the ones in Section 4) would no longer be true.  REMARK 1. For the payment bounds that are derived from   maximisation problems, (i.e., TUmax(c, S) and NTUmax(c, S)),   constraints of type (3) are redundant and can be dropped. Hence,  TUmax(c, S) and NTUmax(c, S) are solutions to linear   programs, and therefore can be computed in polynomial time as long  as we have a separation oracle for constraints in (2). In contrast,  338  NTUmin(c, S) can be NP-hard to compute even if the size of F is  polynomial (see Section 6).  The first and third inequalities in the following observation   follow from the fact that condition (1∗  ) is strictly weaker than   condition (1).  PROPOSITION 1.  TUmin(c, S) ≤ NTUmin(c, S) ≤  NTUmax(c, S) ≤ TUmax(c, S).  Let M be a truthful mechanism for (E, F). Let pM(c) denote  the total payments of M when the actual costs are c. A frugality  ratio of M with respect to a payment bound is the ratio between  the payment of M and this payment bound. In particular,  φTUmin(M) = sup  c  pM(c)/TUmin(c),  φTUmax(M) = sup  c  pM(c)/TUmax(c),  φNTUmin(M) = sup  c  pM(c)/NTUmin(c),  φNTUmax(M) = sup  c  pM(c)/NTUmax(c).  We conclude this section by showing that there exist set systems  and respective cost vectors for which all four payment bounds are  different. In the next section, we quantify this difference, both for  general set systems, and for specific types of set systems, such as  path auctions or vertex cover auctions.  EXAMPLE 1. Consider the shortest-path auction on the graph  of Figure 1. The cheapest feasible sets are all paths from A to D. It  can be verified, using the reasoning of Propositions 2 and 3 below,  that for the cost vector cAB = cCD = 2, cBC = 1, cAC = cBD =  5, we have  • TUmax(c) = 10 (with bAB = bCD = 5, bBC = 0),  • NTUmax(c) = 9 (with bAB = bCD = 4, bBC = 1),  • NTUmin(c) = 7 (with bAB = bCD = 2, bBC = 3),  • TUmin(c) = 5 (with bAB = bCD = 0, bBC = 5).  4. COMPARING PAYMENT BOUNDS  4.1 Path auctions  We start by showing that for path auctions any two consecutive  payment bounds can differ by at least a factor of 2.  PROPOSITION 2. There is an instance of the shortest-path   problem for which we have NTUmax(c)/NTUmin(c) ≥ 2.  PROOF. This construction is due to David Kempe [17].   Consider the graph of Figure 1 with the edge costs cAB = cBC =  cCD = 0, cAC = cBD = 1. Under these costs, ABCD is the  cheapest path. The inequalities in (2) are bAB + bBC ≤ cAC = 1,  bBC + bCD ≤ cBD = 1. By condition (3), both of these   inequalities must be tight (the former one is the only inequality   involving bAB, and the latter one is the only inequality involving bCD).  The inequalities in (1) are bAB ≥ 0, bBC ≥ 0, bCD ≥ 0. Now,  if the goal is to maximise bAB + bBC + bCD, the best choice is  bAB = bCD = 1, bBC = 0, so NTUmax(c) = 2. On the other  hand, if the goal is to minimise bAB + bBC + bCD, one should set  bAB = bCD = 0, bBC = 1, so NTUmin(c) = 1.  PROPOSITION 3. There is an instance of the shortest-path   problem for which we have TUmax(c)/NTUmax(c) ≥ 2.  PROOF. Again, consider the graph of Figure 1. Let the edge  costs be cAB = cCD = 0, cBC = 1, cAC = cBD = 1. ABCD  is the lexicographically-least cheapest path, so we can assume that  S = {AB, BC, CD}. The inequalities in (2) are the same as in  the previous example, and by the same argument both of them are,  in fact, equalities. The inequalities in (1) are bAB ≥ 0, bBC ≥ 1,  bCD ≥ 0. Our goal is to maximise bAB + bBC + bCD. If we have  to respect the inequalities in (1), we have to set bAB = bCD = 0,  bBC = 1, so NTUmax(c) = 1. Otherwise, we can set bAB =  bCD = 1, bBC = 0, so TUmax(c) ≥ 2.  PROPOSITION 4. There is an instance of the shortest-path   problem for which we have NTUmin(c)/TUmin(c) ≥ 2.  PROOF. This construction is also based on the graph of Figure 1.  The edge costs are cAB = cCD = 1, cBC = 0, cAC = cBD =  1. ABCD is the lexicographically least cheapest path, so we can  assume that S = {AB, BC, CD}. Again, the inequalities in (2)  are the same, and both are, in fact, equalities. The inequalities in (1)  are bAB ≥ 1, bBC ≥ 0, bCD ≥ 1. Our goal is to minimise bAB +  bBC +bCD. If we have to respect the inequalities in (1), we have to  set bAB = bCD = 1, bBC = 0, so NTUmin(c) = 2. Otherwise,  we can set bAB = bCD = 0, bBC = 1, so TUmin(c) ≤ 1.  In Section 4.4 (Theorem 3), we show that the separation results  in Propositions 2, 3, and 4 are optimal.  4.2 Connections between separation results  The separation results for path auctions are obtained on the same  graph using very similar cost vectors. It turns out that this is not  coincidental. Namely, we can prove the following theorem.  THEOREM 1. For any set system (E, F), and any feasible set S,  max  c  TUmax(c, S)  NTUmax(c, S)  = max  c  NTUmax(c, S)  NTUmin(c, S)  ,  max  c  NTUmax(c, S)  NTUmin(c, S)  = max  c  NTUmin(c, S)  TUmin(c, S)  ,  where the maximum is over all cost vectors c for which S is a  cheapest feasible set.  The proof of the theorem follows directly from the four lemmas  proved below; more precisely, the first equality in Theorem 1 is  obtained by combining Lemmas 1 and 2, and the second equality is  obtained by combining Lemmas 3 and 4. We prove Lemma 1 here;  the proofs of Lemmas 2- 4 are similar and can be found in the full  version of this paper [8].  LEMMA 1. Suppose that c is a cost vector for (E, F) such that  S is a cheapest feasible set and TUmax(c, S)/NTUmax(c, S) =  α. Then there is a cost vector c such that S is a cheapest feasible  set and NTUmax(c , S)/NTUmin(c , S) ≥ α.  PROOF. Suppose that TUmax(c, S) = X and NTUmax(c, S) =  Y where X/Y = α. Assume without loss of generality that S  consists of elements 1, . . . , k, and let b1  = (b1  1, . . . , b1  k) and b2  =  (b2  1, . . . , b2  k) be the bid vectors that correspond to TUmax(c, S)  and NTUmax(c, S), respectively.  Construct the cost vector c by setting ci = ci for i ∈ S,  ci = min{ci, b1  i } for i ∈ S. Clearly, S is a cheapest set under c .  Moreover, as the costs of elements outside of S remained the same,  the right-hand sides of all constraints in (2) did not change, so any  bid vector that satisfies (2) and (3) with respect to c, also satisfies  them with respect to c . We will construct two bid vectors b3  and  b4  that satisfy conditions (1), (2), and (3) for the cost vector c , and  339  X  X X  X X 0  X  12  3  X 4 5  6  Figure 2: Graph that separates payment bounds for vertex  cover, n = 7  have  P  i∈S b3  i = X,  P  i∈S b4  i = Y . As NTUmax(c , S) ≥ X  and NTUmin(c , S) ≤ Y , this implies the lemma.  We can set b3  i = b1  i : this bid vector satisfies conditions (2)  and (3) since b1  does, and we have b1  i ≥ min{ci, b1  i } = ci,  which means that b3  satisfies condition (1). Furthermore, we can  set b4  i = b2  i . Again, b4  satisfies conditions (2) and (3) since b2  does, and since b2  satisfies condition (1), we have b2  i ≥ ci ≥ ci,  which means that b4  satisfies condition (1).  LEMMA 2. Suppose c is a cost vector for (E, F) such that S is  a cheapest feasible set and NTUmax(c, S)/NTUmin(c, S) = α.  Then there is a cost vector c such that S is a cheapest feasible set  and TUmax(c , S)/NTUmax(c , S) ≥ α.  LEMMA 3. Suppose that c is a cost vector for (E, F) such that  S is a cheapest feasible set and NTUmax(c, S)/NTUmin(c, S) =  α. Then there is a cost vector c such that S is a cheapest feasible  set and NTUmin(c , S)/TUmin(c , S) ≥ α.  LEMMA 4. Suppose that c is a cost vector for (E, F) such that  S is a cheapest feasible set and NTUmin(c, S)/TUmin(c, S) =  α. Then there is a cost vector c such that S is a cheapest feasible  set and NTUmax(c , S)/NTUmin(c , S) ≥ α.  4.3 Vertex-cover auctions  In contrast to the case of path auctions, for vertex-cover   auctions the gap between NTUmin(c) and NTUmax(c) (and hence  between NTUmax(c) and TUmax(c), and between TUmin(c)  and NTUmin(c)) can be proportional to the size of the graph.  PROPOSITION 5. For any n ≥ 3, there is a an n-vertex graph  and a cost vector c for which TUmax(c)/NTUmax(c) ≥ n − 2.  PROOF. The underlying graph consists of an (n − 1)-clique on  the vertices X1, . . . , Xn−1, and an extra vertex X0 adjacent to  Xn−1. The costs are cX1 = cX2 = · · · = cXn−2 = 0, cX0 =  cXn−1 = 1. We can assume that S = {X0, X1, . . . , Xn−2} (this  is the lexicographically first vertex cover of cost 1). For this set  system, the constraints in (2) are bXi + bX0 ≤ cXn−1 = 1 for  i = 1, . . . , n − 2. Clearly, we can satisfy conditions (2) and (3)  by setting bXi = 1 for i = 1, . . . , n − 2, bX0 = 0. Hence,  TUmax(c) ≥ n − 2. For NTUmax(c), there is an additional  constraint bX0 ≥ 1, so the best we can do is to set bXi = 0 for  i = 1, . . . , n − 2, bX0 = 1, which implies NTUmax(c) = 1.  Combining Proposition 5 with Lemmas 1 and 3, we derive the  following corollaries.  COROLLARY 1. For any n ≥ 3, we can construct an instance  of the vertex cover problem on a graph of size n that satisfies  NTUmax(c)/NTUmin(c) ≥ n − 2.  COROLLARY 2. For any n ≥ 3, we can construct an instance  of the vertex cover problem on a graph of size n that satisfies  NTUmin(c)/TUmin(c) ≥ n − 2.  j+2ix  ij  P \ P ij+2P \ P  yijixix j  j+1  i j+2ij+1  y y  i i j+2ie j  e j+1  e  ij+1  P \ P  Figure 3: Proof of Theorem 3: constraints for ˆPij and ˆPij+2 do  not overlap  4.4 Upper bounds  It turns out that the lower bound proved in the previous   subsection is almost tight. More precisely, the following theorem shows  that no two payment bounds can differ by more than a factor of n;  moreover, this is the case not just for the vertex cover problem, but  for general set systems. We bound the gap between TUmax(c) and  TUmin(c). Since TUmin(c) ≤ NTUmin(c) ≤ NTUmax(c) ≤  TUmax(c), this bound applies to any pair of payment bounds.  THEOREM 2. For any set system (E, F) and any cost vector c,  we have TUmax(c)/TUmin(c) ≤ n.  PROOF. Assume wlog that the winning set S consists of   elements 1, . . . , k. Let c1, . . . , ck be the true costs of elements in S,  let b1, . . . , bk be their bids that correspond to TUmin(c), and let  b1 , . . . , bk be their bids that correspond to TUmax(c).  Consider the conditions (2) and (3) for S. One can pick a subset  L of at most k inequalities in (2) so that for each i = 1, . . . , k there  is at least one inequality in L that is tight for bi. Suppose that the  jth inequality in L is of the form bi1 + · · · + bit ≤ c(Tj \ S). For  bi, all inequalities in L are, in fact, equalities. Hence, by adding  up all of them we obtain k  P  i=1,...,k bi ≥  P  j=1,...,k c(Tj \ S).  On the other hand, all these inequalities appear in condition (2), so  they must hold for bi , i.e.,  P  i=1,...,k bi ≤  P  j=1,...,k c(Tj \ S).  Combining these two inequalities, we obtain  nTUmin(c) ≥ kTUmin(c) ≥ TUmax(c).  REMARK 2. The final line of the proof of Theorem 2 shows  that, in fact, the upper bound on TUmax(c)/TUmin(c) can be  strengthened to the size of the winning set, k. Note that in   Proposition 5, as well as in Corollaries 1 and 2, k = n−1, so these results  do not contradict each other.  For path auctions, this upper bound can be improved to 2,   matching the lower bounds of Section 4.1.  THEOREM 3. For any instance of the shortest path problem,  TUmax(c) ≤ 2 TUmin(c).  PROOF. Given a network (G, s, t), assume without loss of   generality that the lexicographically-least cheapest s-t path, P, in G  is {e1, . . . , ek}, where e1 = (s, v1), e2 = (v1, v2), . . . , ek =  (vk−1, t). Let c1, . . . , ck be the true costs of e1, . . . , ek, and let  b = (b1, . . . , bk) and b = (b1 , . . . , bk ) be bid vectors that   correspond to TUmin(c) and TUmax(c), respectively.  For any i = 1, . . . , k, there is a constraint in (2) that is tight for  bi with respect to the bid vector b , i.e., an s-t path Pi that avoids  ei and satisfies b (P \Pi) = c(Pi \P). We can assume without loss  of generality that Pi coincides with P up to some vertex xi, then  deviates from P to avoid ei, and finally returns to P at a vertex  340  yi and coincides with P from then on (clearly, it might happen  that s = xi or t = yi). Indeed, if Pi deviates from P more than  once, one of these deviations is not necessary to avoid ei and can  be replaced with the respective segment of P without increasing the  cost of Pi. Among all paths of this form, let ˆPi be the one with the  largest value of yi, i.e., the rightmost one. This path corresponds  to an inequality Ii of the form bxi+1 + · · · + byi  ≤ c( ˆPi \ P).  As in the proof of Theorem 2, we construct a set of tight   constraints L such that every variable bi appears in at least one of these  constraints; however, now we have to be more careful about the  choice of constraints in L. We construct L inductively as follows.  Start by setting L = {I1}. At the jth step, suppose that all   variables up to (but not including) bij  appear in at least one inequality  in L. Add Iij to L.  Note that for any j we have yij+1 > yij . This is because the  inequalities added to L during the first j steps did not cover bij+1  .  See Figure 3. Since yij+2 > yij+1 , we must also have xij+2 >  yij : otherwise, ˆPij+1 would not be the rightmost constraint for  bij+1  . Therefore, the variables in Iij+2 and Iij do not overlap, and  hence no bi can appear in more than two inequalities in L.  Now we follow the argument of the proof of Theorem 2 to finish.  By adding up all of the (tight) inequalities in L for bi we obtain  2  P  i=1,...,k bi ≥  P  j=1,...,k c( ˆPj \ P). On the other hand, all  these inequalities appear in condition (2), so they must hold for  bi , i.e.,  P  i=1,...,k bi ≤  P  j=1,...,k c( ˆPj \ P), so TUmax(c) ≤  2TUmin(c).  5. TRUTHFUL MECHANISMS FOR   VERTEX COVER  Recall that for a vertex-cover auction on a graph G = (V, E), an  allocation rule is an algorithm that takes as input a bid bv for each  vertex and returns a vertex cover ˆS of G. As explained in   Section 2, we can combine a monotone allocation rule with threshold  payments to obtain a truthful auction.  Two natural examples of monotone allocation rules are Aopt, i.e.,  the algorithm that finds an optimal vertex cover, and the greedy  algorithm AGR. However, Aopt cannot be guaranteed to run in  polynomial time unless P = NP and AGR has approximation  ratio of log n.  Another approximation algorithm for vertex cover, which has   approximation ratio 2, is the local ratio algorithm ALR [2, 3]. This  algorithm considers the edges of G one by one. Given an edge  e = (u, v), it computes = min{bu, bv} and sets bu = bu − ,  bv = bv − . After all edges have been processed, ALR returns  the set of vertices {v | bv = 0}. It is not hard to check that if  the order in which the edges are considered is independent of the  bids, then this algorithm is monotone as well. Hence, we can use it  to construct a truthful auction that is guaranteed to select a vertex  cover whose cost is within a factor of 2 from the optimal.  However, while the quality of the solution produced by ALR is  much better than that of AGR, we still need to show that its total  payment is not too high. In the next subsection, we bound the   frugality ratio of ALR (and, more generally, all algorithms that satisfy  the condition of local optimality, defined later) by 2Δ, where Δ is  the maximum degree of G. We then prove a matching lower bound  showing that for some graphs the frugality ratio of any truthful   auction is at least Δ/2.  5.1 Upper bound  We say that an allocation rule is locally optimal if whenever bv >P  w∼v bw, the vertex v is not chosen. Note that for any such rule  the threshold bid of v satisfies tv ≤  P  w∼v bw.  CLAIM 1. The algorithms Aopt, AGR, and ALR are locally  optimal.  THEOREM 4. Any vertex cover auction M that has a locally  optimal and monotone allocation rule and pays each agent his  threshold bid has frugality ratio φNTUmin(M) ≤ 2Δ.  To prove Theorem 4, we first show that the total payment of  any locally optimal mechanism does not exceed Δc(V ). We then  demonstrate that NTUmin(c) ≥ c(V )/2. By combining these  two results, the theorem follows.  LEMMA 5. Consider a graph G = (V, E) with maximum   degree Δ. Let M be a vertex-cover auction on G that satisfies the  conditions of Theorem 4. Then for any cost vector c, the total   payment of M satisfies pM(c) ≤ Δc(V ).  PROOF. First note that any such auction is truthful, so we can  assume that each agent"s bid is equal to his cost. Let ˆS be the  vertex cover selected by M. Then by local optimality  pM(c) =  X  v∈ ˆS  tv ≤  X  v∈ ˆS  X  w∼v  cw ≤  X  w∈V  Δcw = Δc(V ).  We now derive a lower bound on TUmax(c); while not essential  for the proof of Theorem 4, it helps us build the intuition necessary  for that proof.  LEMMA 6. For a vertex cover instance G = (V, E) in which S  is a minimum vertex cover, TUmax(c, S) ≥ c(V \ S)  PROOF. For a vertex w with at least one neighbour in S, let  d(w) denote the number of neighbours that w has in S. Consider  the bid vector b in which, for each v ∈ S, bv =  P  w∼v,w∈S  cw  d(w)  .  Then  P  v∈S bv =  P  v∈S  P  w∼v,w∈S cw/d(w) =  P  w /∈S cw =  c(V \ S). To finish we want to show that b is feasible in the sense  that it satisfies (2). Consider a vertex cover T, and extend the bid  vector b by assigning bv = cv for v /∈ S. Then  b(T) = c(T \S)+b(S∩T) ≥ c(T \S)+  X  v∈S∩T  X  w∈S∩T :w∼v  cw  d(w)  ,  and since all edges between S ∩ T and S go to S ∩ T, the   righthand-side is equal to  c(T \S)+  X  w∈S∩T  cw = c(T \S)+c(S ∩T) = c(V \S) = b(S).  Next, we prove a lower bound on NTUmax(c, S); we will then  use it to obtain a lower bound on NTUmin(c).  LEMMA 7. For a vertex cover instance G = (V, E) in which S  is a minimum vertex cover, NTUmax(c, S) ≥ c(V \ S)  PROOF. If c(S) ≥ c(V \ S), by condition (1) we are done.  Therefore, for the rest of the proof we assume that c(S) < c(V \  S). We show how to construct a bid vector (be)e∈S that satisfies  conditions (1) and (2) such that b(S) ≥ c(V \ S); clearly, this  implies NTUmax(c, S) ≥ c(V \ S).  Recall that a network flow problem is described by a directed  graph Γ = (VΓ, EΓ), a source node s ∈ VΓ, a sink node t ∈  VΓ, and a vector of capacity constraints ae, e ∈ EΓ. Consider a  network (VΓ, EΓ) such that VΓ = V ∪{s, t}, EΓ = E1 ∪E2 ∪E3,  where E1 = {(s, v) | v ∈ S}, E2 = {(v, w) | v ∈ S, w ∈  341  V \ S, (v, w) ∈ E}, E3 = {(w, t) | w ∈ V \ S}. Since S is  a vertex cover for G, no edge of E can have both of its endpoints  in V \ S, and by construction, E2 contains no edges with both  endpoints in S. Therefore, the graph (V, E2) is bipartite with parts  (S, V \ S).  Set the capacity constraints for e ∈ EΓ as follows: a(s,v) =  cv, a(w,t) = cw, a(v,w) = +∞ for all v ∈ S, w ∈ V \ S.  Recall that a cut is a partition of the vertices in VΓ into two sets  C1 and C2 so that s ∈ C1, t ∈ C2; we denote such a cut by  C = (C1, C2). Abusing notation, we write e = (u, v) ∈ C if  u ∈ C1, v ∈ C2 or u ∈ C2, v ∈ C1, and say that such an edge  e = (u, v) crosses the cut C. The capacity of a cut C is computed  as cap(C) =  P  (v,w)∈C a(v,w). We have cap(s, V ∪{t}) = c(S),  cap({s} ∪ V, t) = c(V \ S).  Let Cmin = ({s} ∪ S ∪ W , {t} ∪ S ∪ W ) be a minimum  cut in Γ, where S , S ⊆ S, W , W ⊆ V \ S. See Figure 4. As  cap(Cmin) ≤ cap(s, V ∪ {t}) = c(S) < +∞, and any edge in  E2 has infinite capacity, no edge (u, v) ∈ E2 crosses Cmin.  Consider the network Γ = (VΓ , EΓ ), where VΓ = {s} ∪  S ∪ W ∪ {t}, EΓ = {(u, v) ∈ EΓ | u, v ∈ VΓ }. Clearly,  C = ({s} ∪ S ∪ W , {t}) is a minimum cut in Γ (otherwise,  there would exist a smaller cut for Γ). As cap(C ) = c(W ), we  have c(S ) ≥ c(W ).  Now, consider the network Γ = (VΓ , EΓ ), where VΓ =  {s} ∪ S ∪ W ∪ {t}, EΓ = {(u, v) ∈ EΓ | u, v ∈ VΓ }.  Similarly, C = ({s}, S ∪ W ∪ {t}) is a minimum cut in Γ ,  cap(C ) = c(S ). As the size of a maximum flow from s to  t is equal to the capacity of a minimum cut separating s and t,  there exists a flow F = (fe)e∈EΓ  of size c(S ). This flow has  to saturate all edges between s and S , i.e., f(s,v) = cv for all  v ∈ S . Now, increase the capacities of all edges between s and  S to +∞. In the modified network, the capacity of a minimum cut  (and hence the size of a maximum flow) is c(W ), and a maximum  flow F = (fe)e∈EΓ  can be constructed by greedily augmenting  F.  Set bv = cv for all v ∈ S , bv = f(s,v) for all v ∈ S . As F is  constructed by augmenting F, we have bv ≥ cv for all v ∈ S, i.e.,  condition (1) is satisfied.  Now, let us check that no vertex cover T ⊆ V can violate   condition (2). Set T1 = T ∩ S , T2 = T ∩ S , T3 = T ∩ W ,  T4 = T ∩ W ; our goal is to show that b(S \ T1) + b(S \ T2) ≤  c(T3)+c(T4). Consider all edges (u, v) ∈ E such that u ∈ S \T1.  If (u, v) ∈ E2 then v ∈ T3 (no edge in E2 can cross the cut), and if  u, v ∈ S then v ∈ T1∪T2. Hence, T1∪T3∪S is a vertex cover for  G, and therefore c(T1)+ c(T3)+ c(S ) ≥ c(S) = c(T1)+ c(S \  T1) + c(S ). Consequently, c(T3) ≥ c(S \ T1) = b(S \ T1).  Now, consider the vertices in S \T2. Any edge in E2 that starts in  one of these vertices has to end in T4 (this edge has to be covered by  T, and it cannot go across the cut). Therefore, the total flow out of  S \T2 is at most the total flow out of T4, i.e., b(S \T2) ≤ c(T4).  Hence, b(S \ T1) + b(S \ T2) ≤ c(T3) + c(T4).  Finally, we derive a lower bound on the payment bound that is  of interest to us, namely, NTUmin(c).  LEMMA 8. For a vertex cover instance G = (V, E) in which S  is a minimum vertex cover, NTUmin(c, S) ≥ c(V \ S)  PROOF. Suppose for contradiction that c is a cost vector with  minimum-cost vertex cover S and NTUmin(c, S) < c(V \S). Let  b be the corresponding bid vector and let c be a new cost vector  with cv = bv for v ∈ S and cv = cv for v ∈ S. Condition (2)  guarantees that S is an optimal solution to the cost vector c . Now  compute a bid vector b corresponding to NTUmax(c , S). We  S"  W""  S""  W"  s  t  T1  T3  T2  T4  0  00  1  11  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  0000  11  1111  00  00  11  11  0  00  1  11  0  00  1  11  0  00  1  11  0000000  00000000000000  00000000000000  0000000  00000000000000  00000000000000  0000000  00000000000000  1111111  11111111111111  11111111111111  1111111  11111111111111  11111111111111  1111111  11111111111111  0000  00000000  00000000  0000  00000000  00000000  0000  00000000  1111  11111111  11111111  1111  11111111  11111111  1111  11111111  00  0000  0000  00  0000  0000  00  0000  11  1111  1111  11  1111  1111  11  1111  00  0000  0000  00  0000  0000  00  0000  11  1111  1111  11  1111  1111  11  1111  00000  0000000000  0000000000  00000  0000000000  0000000000  00000  0000000000  11111  1111111111  1111111111  11111  1111111111  1111111111  11111  1111111111  0000000  00000000000000  00000000000000  0000000  00000000000000  00000000000000  0000000  00000000000000  1111111  11111111111111  11111111111111  1111111  11111111111111  11111111111111  1111111  11111111111111  0000000  00000000000000  00000000000000  0000000  00000000000000  00000000000000  0000000  00000000000000  1111111  11111111111111  11111111111111  1111111  11111111111111  11111111111111  1111111  11111111111111  0000  00000000  00000000  0000  00000000  00000000  0000  00000000  1111  11111111  11111111  1111  11111111  11111111  1111  11111111  00  0000  0000  00  0000  0000  00  0000  11  1111  1111  11  1111  1111  11  1111000  000000  000000  000  000000  000000  000  000000  000000  000  000  111  111111  111111  111  111111  111111  111  111111  111111  111  111  0000000  00000000000000  00000000000000  0000000  00000000000000  00000000000000  0000000  00000000000000  00000000000000  0000000  00000000000000  1111111  11111111111111  11111111111111  1111111  11111111111111  11111111111111  1111111  11111111111111  11111111111111  1111111  11111111111111  000  000000  000000  000  000000  000000  000  000000  000000  000  000000  111  111111  111111  111  111111  111111  111  111111  111111  111  111111  000000  000000000000  000000000000  000000  000000000000  000000000000  000000  000000000000  000000000000  000000  000000000000  111111  111111111111  111111111111  111111  111111111111  111111111111  111111  111111111111  111111111111  111111  111111111111  000000  000000000000  000000000000  000000  000000000000  000000000000  000000  000000000000  000000000000  000000  000000000000  111111  111111111111  111111111111  111111  111111111111  111111111111  111111  111111111111  111111111111  111111  111111111111  000  000000  000000  000  000000  000000  000  000000  000000  000  000000  111  111111  111111  111  111111  111111  111  111111  111111  111  111111  Figure 4: Proof of Lemma 7. Dashed lines correspond to edges  in E \ E2  claim that bv = cv for any v ∈ S. Indeed, suppose that bv > cv  for some v ∈ S (bv = cv for v ∈ S by construction). As b satisfies  conditions (1)-(3), among the inequalities in (2) there is one that is  tight for v and the bid vector b. That is, b(S \ T) = c(T \ S). By  the construction of c , c (S \ T) = c (T \ S). Now since bw ≥ cw  for all w ∈ S, bv > cv implies b (S \T) > c (S \T) = c (T \S).  But this violates (2). So we now know b = c . Hence, we have  NTUmax(c , S) =  P  v∈S bv = NTUmin(c, S) < c(V \ S),  giving a contradiction to the fact that NTUmax(c , S) ≥ c (V \S)  which we proved in Lemma 7.  As NTUmin(c, S) satisfies condition (1), it follows that we  have NTUmin(c, S) ≥ c(S). Together will Lemma 8, this implies  NTUmin(c, S) ≥ max{c(V \ S), c(S)} ≥ c(V )/2. Combined  with Lemma 5, this completes the proof of Theorem 4.  REMARK 3. As NTUmin(c) ≤ NTUmax(c) ≤ TUmax(c),  our bound of 2Δ extends to the smaller frugality ratios that we   consider, i.e., φNTUmax(M) and φTUmax(M). It is not clear whether  it extends to the larger frugality ratio φTUmin(M). However, the  frugality ratio φTUmin(M) is not realistic because the payment  bound TUmin(c) is inappropriately low - we show in Section 6  that TUmin(c) can be significantly smaller than the total cost of a  cheapest vertex cover.  Extensions  We can also apply our results to monotone vertex-cover algorithms  that do not necessarily output locally-optimal solutions. To do so,  we simply take the vertex cover produced by any such algorithm  and transform it into a locally-optimal one, considering the vertices  in lexicographic order and replacing a vertex v with its neighbours  whenever bv >  P  u∼v bu. Note that if a vertex u has been added to  the vertex cover during this process, it means that it has a neighbour  whose bid is higher than bu, so after one pass all vertices in the   vertex cover satisfy bv ≤  P  u∼v bu. This procedure is monotone in  bids, and it can only decrease the cost of the vertex cover.   Therefore, using it on top of a monotone allocation rule with   approx342  imation ratio α, we obtain a monotone locally-optimal allocation  rule with approximation ratio α. Combining it with threshold   payments, we get an auction with φNTUmin ≤ 2Δ. Since any truthful  auction has a monotone allocation rule, this procedure transforms  any truthful mechanism for the vertex-cover problem into a frugal  one while preserving the approximation ratio.  5.2 Lower bound  In this subsection, we prove that the upper bound of Theorem 4  is essentially optimal. Our proof uses the techniques of [9], where  the authors prove a similar result for shortest-path auctions.  THEOREM 5. For any Δ > 0 and any n, there exist a graph G  of maximum degree Δ and size N > n such that for any truthful  mechanism M on G we have φNTUmin(M) ≥ Δ/2.  PROOF. Given n and Δ, set k = n/2Δ . Let G be the graph  that consists of k blocks B1, . . . , Bk of size 2Δ each, where each  Bi is a complete bipartite graph with parts Li and Ri, |Li| =  |Ri| = Δ.  We will consider two families of cost vectors for G. Under a  cost vector x ∈ X, each block Bi has one vertex of cost 1; all  other vertices cost 0. Under a cost vector y ∈ Y , there is one block  that has two vertices of cost 1, one in each part, all other blocks  have one vertex of cost 1, and all other vertices cost 0. Clearly,  |X| = (2Δ)k  , |Y | = k(2Δ)k−1  Δ2  . We will now construct a  bipartite graph W with the vertex set X ∪ Y as follows.  Consider a cost vector y ∈ Y that has two vertices of cost 1 in  Bi; let these vertices be vl ∈ Li and vr ∈ Ri. By changing the  cost of either of these vertices to 0, we obtain a cost vector in X.  Let xl and xr be the cost vectors obtained by changing the cost of  vl and vr, respectively. The vertex cover chosen by M(y) must  either contain all vertices in Li or it must contain all vertices in Ri.  In the former case, we put in W an edge from y to xl and in the  latter case we put in W an edge from y to xr (if the vertex cover  includes all of Bi, W contains both of these edges).  The graph W has at least k(2Δ)k−1  Δ2  edges, so there must  exist an x ∈ X of degree at least kΔ/2. Let y1, . . . , ykΔ/2 be  the other endpoints of the edges incident to x, and for each i =  1, . . . , kΔ/2, let vi be the vertex whose cost is different under x  and yi; note that all vi are distinct.  It is not hard to see that NTUmin(x) ≤ k: the cheapest vertex  cover contains the all-0 part of each block, and we can satisfy   conditions (1)-(3) by letting one of the vertices in the all-0 part of each  block to bid 1, while all other the vertices in the cheapest set bid 0.  On the other hand, by monotonicity of M we have vi ∈ M(x)  for i = 1, . . . , kΔ/2 (vi is in the winning set under yi, and x is  obtained from yi by decreasing the cost of vi), and moreover, the  threshold bid of each vi is at least 1, so the total payment of M on x  is at least kΔ/2. Hence, φNTUmin(M) ≥ M(x)/NTUmin(x) ≥  Δ/2.  REMARK 4. The lower bound of Theorem 5 can be generalised  to randomised mechanisms, where a randomised mechanism is   considered to be truthful if it can be represented as a probability   distribution over truthful mechanisms. In this case, instead of choosing  the vertex x ∈ X with the highest degree, we put both (y, xl)  and (y, xr) into W , label each edge with the probability that the  respective part of the block is chosen, and pick x ∈ X with the  highest weighted degree. The argument can be further extended to  a more permissive definition of truthfulness for randomised   mechanisms, but this discussion is beyond the scope of this paper.  6. PROPERTIES OF PAYMENT BOUNDS  In this section we consider several desirable properties of   payment bounds and evaluate the four payment bounds proposed in  this paper with respect to them. The particular properties that we  are interested in are independence of the choice of S (Section 6.3),  monotonicity (Section 6.4.1), computational hardness (Section 6.4.2),  and the relationship with other reasonable bounds, such as the total  cost of the cheapest set (Section 6.1), or the total VCG payment  (Section 6.2).  6.1 Comparison with total cost  Our first requirement is that a payment bound should not be less  than the total cost of the selected set. Payment bounds are used to  evaluate the performance of set-system auctions. The latter have to  satisfy individual rationality, i.e., the payment to each agent must  be at least as large as his incurred costs; it is only reasonable to  require the payment bound to satisfy the same requirement.  Clearly, NTUmax(c) and NTUmin(c) satisfy this requirement  due to condition (1), and so does TUmax(c), since TUmax(c) ≥  NTUmax(c). However, TUmin(c) fails this test. The example  of Proposition 4 shows that for path auctions, TUmin(c) can be  smaller than the total cost by a factor of 2. Moreover, there are set  systems and cost vectors for which TUmin(c) is smaller than the  cost of the cheapest set S by a factor of Ω(n). Consider, for   example, the vertex-cover auction for the graph of Proposition 5 with  the costs cX1 = · · · = cXn−2 = cXn−1 = 1, cX0 = 0. The cost  of a cheapest vertex cover is n − 2, and the lexicographically first  vertex cover of cost n−2 is {X0, X1, . . . , Xn−2}. The constraints  in (2) are bXi + bX0 ≤ cXn−1 = 1. Clearly, we can satisfy   conditions (2) and (3) by setting bX1 = · · · = bXn−2 = 0, bX0 = 1,  which means that TUmin(c) ≤ 1. This observation suggests that  the payment bound TUmin(c) is too strong to be realistic, since it  can be substantially lower than the cost of the cheapest feasible set.  Nevertheless, some of the positive results that were proved in [16]  for NTUmin(c) go through for TUmin(c) as well. In particular,  one can show that if the feasible sets are the bases of a   monopolyfree matroid, then φTUmin(VCG) = 1. To show that φTUmin(VCG)  is at most 1, one must prove that the VCG payment is at most  TUmin(c). This is shown for NTUmin(c) in the first paragraph  of the proof of Theorem 5 in [16]. Their argument does not use   condition (1) at all, so it also applies to TUmin(c). On the other hand,  φTUmin(VCG) ≥ 1 since φTUmin(VCG) ≥ φNTUmin(VCG)  and φNTUmin(VCG) ≥ 1 by Proposition 7 of [16] (and also by  Proposition 6 below).  6.2 Comparison with VCG payments  Another measure of suitability for payment bounds is that they  should not result in frugality ratios that are less then 1 for   wellknown truthful mechanisms. If this is indeed the case, the payment  bound may be too weak, as it becomes too easy to design   mechanisms that perform well with respect to it. It particular, a reasonable  requirement is that a payment bound should not exceed the total  payment of the classical VCG mechanism.  The following proposition shows that NTUmax(c), and   therefore also NTUmin(c) and TUmin(c), do not exceed the VCG  payment pVCG(c). The proof essentially follows the argument of  Proposition 7 of [16] and can be found in the full version of this  paper [8].  PROPOSITION 6. φNTUmax(VCG) ≥ 1.  Proposition 6 shows that none of the payment bounds TUmin(c),  NTUmin(c) and NTUmax(c) exceeds the payment of VCG.   However, the payment bound TUmax(c) can be larger that the total  343  VCG payment. In particular, for the instance in Proposition 5, the  VCG payment is smaller than TUmax(c) by a factor of n − 2. We  have already seen that TUmax(c) ≥ n − 2. On the other hand,  under VCG, the threshold bid of any Xi, i = 1, . . . , n − 2, is 0:  if any such vertex bids above 0, it is deleted from the winning set  together with X0 and replaced with Xn−1. Similarly, the threshold  bid of X0 is 1, because if X0 bids above 1, it can be replaced with  Xn−1. So the VCG payment is 1.  This result is not surprising: the definition of TUmax(c)   implicitly assumes there is co-operation between the agents, while  the computation of VCG payments does not take into account any  interaction between them. Indeed, co-operation enables the agents  to extract higher payments under VCG. That is, VCG is not   groupstrategyproof. This suggests that as a payment bound, TUmax(c)  may be too liberal, at least in a context where there is little or  no co-operation between agents. Perhaps TUmax(c) can be a  good benchmark for measuring the performance of mechanisms   designed for agents that can form coalitions or make side payments  to each other, in particular, group-strategyproof mechanisms.  Another setting in which bounding φTUmax is still of some   interest is when, for the underlying problem, the optimal allocation  and VCG payments are NP-hard to compute. In this case, finding  a polynomial-time computable mechanism with good frugality   ratio with respect to TUmax(c) is a non-trivial task, while bounding  the frugality ratio with respect to more challenging payment bounds  could be too difficult. To illustrate this point, compare the proofs  of Lemma 6 and Lemma 7: both require some effort, but the latter  is much more difficult than the former.  6.3 The choice of S  All payment bounds defined in this paper correspond to the total  bid of all elements in the cheapest feasible set, where ties are   broken lexicographically. While this definition ensures that our   payment bounds are well-defined, the particular choice of the   drawresolution rule appears arbitrary, and one might wonder if our   payment bounds are sufficiently robust to be independent of this choice.  It turns out that is indeed the case for NTUmin(c) and NTUmax(c),  i.e., these bounds do not depend on the draw-resolution rule. To  see this, suppose that two feasible sets S1 and S2 have the same  cost. In the computation of NTUmin(c, S1), all vertices in S1 \S2  would have to bid their true cost, since otherwise S2 would   become cheaper than S1. Hence, any bid vector for S1 can only have  be = ce for e ∈ S1 ∩ S2, and hence constitutes a valid bid vector  for S2 and vice versa. A similar argument applies to NTUmax(c).  However, for TUmin(c) and TUmax(c) this is not the case.  For example, consider the set system  E = {e1, e2, e3, e4, e5},  F = {S1 = {e1, e2}, S2 = {e2, e3, e4}, S3 = {e4, e5}}  with the costs c1 = 2, c2 = c3 = c4 = 1, c5 = 3. The cheapest  sets are S1 and S2. Now TUmax(c, S1) ≤ 4, as the total bid of  the elements in S1 cannot exceed the total cost of S3. On the other  hand, TUmax(c, S2) ≥ 5, as we can set b2 = 3, b3 = 0, b4 = 2.  Similarly, TUmin(c, S1) = 4, because the inequalities in (2) are  b1 ≤ 2 and b1 + b2 ≤ 4. But TUmin(c, S2) ≤ 3 as we can set  b2 = 1, b3 = 2, b4 = 0.  6.4 Negative results for NTUmin(c) and TUmin(c)  The results in [16] and our vertex cover results are proved for the  frugality ratio φNTUmin. Indeed, it can be argued that φNTUmin is  the best definition of frugality ratio, because among all   reasonable payment bounds (i.e., ones that are at least as large as the cost  of the cheapest feasible set), it is most demanding of the algorithm.  However, NTUmin(c) is not always the easiest or the most natural  payment bound to work with. In this subsection, we discuss several  disadvantages of NTUmin(c) (and also TUmin(c)) as compared  to NTUmax(c) and TUmax(c).  6.4.1 Nonmonotonicity  The first problem with NTUmin(c) is that it is not monotone  with respect to F, i.e., it may increase when one adds a feasible  set to F. (It is, however, monotone in the sense that a losing agent  cannot become a winner by raising his cost.) Intuitively, a good  payment bound should satisfy this monotonicity requirement, as  adding a feasible set increases the competition, so it should drive  the prices down. Note that this indeed the case for NTUmax(c)  and TUmax(c) since a new feasible set adds a constraint in (2),  thus limiting the solution space for the respective linear program.  PROPOSITION 7. Adding a feasible set to F can increase the  value of NTUmin(c) by a factor of Ω(n).  PROOF. Let E = {x, xx, y1, . . . , yn, z1, . . . , zn}. Set Y =  {y1, . . . , yn}, S = Y ∪ {x}, Ti = Y \ {yi} ∪ {zi}, i = 1, . . . , n,  and suppose that F = {S, T1, . . . , Tn}. The costs are cx = 0,  cxx = 0, cyi = 0, czi = 1 for i = 1, . . . , n. Note that S is  the cheapest feasible set. Let F = F ∪ {T0}, where T0 = Y ∪  {xx}. For F, the bid vector by1 = · · · = byn = 0, bx = 1  satisfies (1), (2), and (3), so NTUmin(c) ≤ 1. For F , S is still  the lexicographically-least cheapest set. Any optimal solution has  bx = 0 (by constraint in (2) with T0). Condition (3) for yi implies  bx + byi = czi = 1, so byi = 1 and NTUmin(c) = n.  For path auctions, it has been shown [18] that NTUmin(c) is  non-monotone in a slightly different sense, i.e., with respect to  adding a new edge (agent) rather than a new feasible set (a team  of existing agents).  REMARK 5. We can also show that NTUmin(c) is non-monotone  for vertex cover. In this case, adding a new feasible set corresponds  to deleting edges from the graph. It turns out that deleting a single  edge can increase NTUmin(c) by a factor of n − 2; the   construction is similar to that of Proposition 5.  6.4.2 NP-Hardness  Another problem with NTUmin(c, S) is that it is NP-hard to  compute even if the number of feasible sets is polynomial in n.  Again, this puts it at a disadvantage compared to NTUmax(c, S)  and TUmax(c, S) (see Remark 1).  THEOREM 6. Computing NTUmin(c) is NP-hard, even when  the lexicographically-least feasible set S is given in the input.  PROOF. We reduce EXACT COVER BY 3-SETS(X3C) to our   problem. An instance of X3C is given by a universe G = {g1, . . . , gn}  and a collection of subsets C1, . . . , Cm, Ci ⊂ G, |Ci| = 3, where  the goal is to decide whether one can cover G by n/3 of these sets.  Observe that if this is indeed the case, each element of G is   contained in exactly one set of the cover.  LEMMA 9. Consider a minimisation problem P of the following  form: Minimise  P  i=1,...,n bi under conditions (1) bi ≥ 0 for all  i = 1, . . . , n; (2) for any j = 1, . . . , k we have  P  bi∈Sj  bi ≤ aj,  where Sj ⊆ {b1, . . . , bn}; (3) for each bj , one of the constraints  in (2) involving it is tight. For any such P, one can construct a  set system S and a vector of costs c such that NTUmin(c) is the  optimal solution to P.  PROOF. The construction is straightforward: there is an element  of cost 0 for each bi, an element of cost aj for each aj, the feasible  solutions are {b1, . . . , bn}, or any set obtained from {b1, . . . , bn}  by replacing the elements in Sj by aj.  344  By this lemma, all we have to do to prove Theorem 6 is to show  how to solve X3C by using the solution to a minimisation problem  of the form given in Lemma 9. We do this as follows. For each  Ci, we introduce 4 variables xi, ¯xi, ai, and bi. Also, for each  element gj of G there is a variable dj. We use the following set of  constraints:  • In (1), we have constraints xi ≥ 0, ¯xi ≥ 0, ai ≥ 0, bi ≥ 0,  dj ≥ 0 for all i = 1, . . . , m, j = 1, . . . , n.  • In (2), for all i = 1, . . . , m, we have the following 5   constraints: xi + ¯xi ≤ 1, xi +ai ≤ 1, ¯xi +ai ≤ 1, xi +bi ≤ 1,  ¯xi + bi ≤ 1. Also, for all j = 1, . . . , n we have a constraint  of the form xi1 + · · · + xik + dj ≤ 1, where Ci1 , . . . , Cik  are the sets that contain gj.  The goal is to minimize z =  P  i(xi + ¯xi + ai + bi) +  P  j dj.  Observe that for each j, there is only one constraint involving  dj , so by condition (3) it must be tight.  Consider the two constraints involving ai. One of them must be  tight, and therefore xi +¯xi +ai +bi ≥ xi +¯xi +ai ≥ 1. Hence, for  any feasible solution to (1)-(3) we have z ≥ m. Now, suppose that  there is an exact set cover. Set dj = 0 for j = 1, . . . , n. Also, if Ci  is included in this cover, set xi = 1, ¯xi = ai = bi = 0, otherwise  set ¯xi = 1, xi = ai = bi = 0. Clearly, all inequalities in (2)  are satisfied (we use the fact that each element is covered exactly  once), and for each variable, one of the constraints involving it is  tight. This assignment results in z = m.  Conversely, suppose there is a feasible solution with z = m.  As each addend of the form xi + ¯xi + ai + bi contributes at least  1, we have xi + ¯xi + ai + bi = 1 for all i, dj = 0 for all j.  We will now show that for each i, either xi = 1 and ¯xi = 0, or  xi = 0 and ¯xi = 1. For the sake of contradiction, suppose that  xi = δ < 1, ¯xi = δ < 1. As one of the constraints involving  ai must be tight, we have ai ≥ min{1 − δ, 1 − δ }. Similarly,  bi ≥ min{1 − δ, 1 − δ }. Hence, xi + ¯xi + ai + bi = 1 =  δ +δ +2 min{1−δ, 1−δ } > 1. To finish the proof, note that for  each j = 1, . . . , m we have xi1 + · · · + xik + dj = 1 and dj = 0,  so the subsets that correspond to xi = 1 constitute a set cover.  REMARK 6. In the proofs of Proposition 7 and Theorem 6 all  constraints in (1) are of the form be ≥ 0. Hence, the same results  are true for TUmin(c).  REMARK 7. For shortest-path auctions, the size of F can be  superpolynomial. However, there is a polynomial-time separation  oracle for constraints in (2) (to construct one, use any algorithm  for finding shortest paths), so one can compute NTUmax(c) and  TUmax(c) in polynomial time. On the other hand, recently and  independently it was shown [18] that computing NTUmin(c) for  shortest-path auctions is NP-hard.  7. REFERENCES  [1] A. Archer and E. Tardos, Frugal path mechanisms. In  Proceedings of the 13th Annual ACM-SIAM Symposium on  Discrete Algorithms, pages 991-999, 2002  [2] R. Bar-Yehuda, K. Bendel, A. Freund, and D. Rawitz, Local  ratio: A unified framework for approximation algorithms. In  Memoriam: Shimon Even 1935-2004. ACM Comput. Surv.,  36(4):422-463, 2004  [3] R. Bar-Yehuda and S. Even, A local-ratio theorem for  approximating the weighted vertex cover problem. Annals of  Discrete Mathematics, 25:27-46, 1985  [4] E. Clarke, Multipart pricing of public goods. Public Choice,  8:17-33, 1971  [5] G. Calinescu, Bounding the payment of approximate truthful  mechanisms. In Proceedings of the 15th International  Symposium on Algorithms and Computation, pages 221-233,  2004  [6] A. Czumaj and A. Ronen, On the expected payment of  mechanisms for task allocation. In Proceedings of the 5th  ACM Conference on Electronic Commerce (EC"04), 2004  [7] E. Elkind, True costs of cheap labor are hard to measure: edge  deletion and VCG payments in graphs. In Proceedings of the  6th ACM Conference on Electronic Commerce (EC"05), 2005  [8] E. Elkind, L. A. Goldberg, and P. W. Goldberg, Frugality  ratios and improved truthful mechanisms for vertex cover.  Available from  http://arxiv.org/abs/cs/0606044, 2006  [9] E. Elkind, A. Sahai, and K. Steiglitz, Frugality in path  auctions. In Proceedings of the 15th Annual ACM-SIAM  Symposium on Discrete Algorithms, pages 694-702, 2004  [10] J. Feigenbaum, C. H. Papadimitriou, R. Sami, and  S. Shenker, A BGP-based mechanism for lowest-cost routing.  In Proceedings of the 21st Symposium on Principles of  Distributed Computing, pages 173-182, 2002  [11] A. Fiat, A. Goldberg, J. Hartline, and A. Karlin, Competitive  generalized auctions. In Proceedings of the 34th Annual ACM  Symposium on Theory of Computation, pages 72-81, 2002  [12] R. Garg, V. Kumar, A. Rudra and A. Verma, Coalitional  games on graphs: core structures, substitutes and frugality. In  Proceedings of the 4th ACM Conference on Electronic  Commerce (EC"03), 2005  [13] A. Goldberg, J. Hartline, and A. Wright, Competitive  auctions and digital goods. In Proceedings of the 12th Annual  ACM-SIAM Symposium on Discrete Algorithms, pages  735-744, 2001  [14] T. Groves, Incentives in teams. Econometrica,  41(4):617-631, 1973  [15] N. Immorlica, D. Karger, E. Nikolova, and R. Sami,  First-price path auctions. In Proceedings of the 6th ACM  Conference on Electronic Commerce (EC"05), 2005  [16] A. R. Karlin, D. Kempe, and T. Tamir, Beyond VCG:  frugality of truthful mechanisms. In Proceedings of the 46th  Annual IEEE Symposium on Foundations of Computer  Science, pages 615-626, 2005  [17] D. Kempe, Personal communication, 2006  [18] N. Chen, A. R. Karlin, Cheap labor can be expensive, In  Proceedings of the 18th Annual ACM-SIAM Symposium on  Discrete Algorithms, pages 735-744, 2007  [19] N. Nisan and A. Ronen, Algorithmic mechanism design. In  Proceedings of the 31st Annual ACM Symposium on Theory of  Computation, pages 129-140, 1999  [20] A. Ronen and R. Talisman, Towards generic low payment  mechanisms for decentralized task allocation. In Proceedings  of the 7th International IEEE Conference on E-Commerce  Technology, 2005  [21] K. Talwar, The price of truth: frugality in truthful  mechanisms. In Proceedings of 20th International Symposium  on Theoretical Aspects of Computer Science, 2003  [22] W. Vickrey, Counterspeculation, auctions, and competitive  sealed tenders. Journal of Finance, 16:8-37, 1961  345