Towards Truthful Mechanisms for Binary Demand Games: A General Framework Ming-Yang Kao ∗ Dept. of Computer Science Northwestern University Evanston, IL, USA kao@cs.northwestern.edu Xiang-Yang Li † Dept. of Computer Science Illinois Institute of Technology Chicago, IL, USA xli@cs.iit.edu WeiZhao Wang Dept. of Computer Science Illinois Institute of Technology Chicago, IL, USA wangwei4@iit.edu ABSTRACT The family of Vickrey-Clarke-Groves (VCG) mechanisms is arguably the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to optimization problems with a utilitarian (or affine) objective function, and their output should optimize the objective function. For many optimization problems, finding the optimal output is computationally intractable. If we apply VCG mechanisms to polynomial-time algorithms that approximate the optimal solution, the resulting mechanisms may no longer be truthful. In light of these limitations, it is useful to study whether we can design a truthful non-VCG payment scheme that is computationally tractable for a given allocation rule O. In this paper, we focus our attention on binary demand games in which the agents" only available actions are to take part in the a game or not to. For these problems, we prove that a truthful mechanism M = (O, P) exists with a proper payment method P iff the allocation rule O satisfies a certain monotonicity property. We provide a general framework to design such P. We further propose several general composition-based techniques to compute P efficiently for various types of output. In particular, we show how P can be computed through or/and combinations, round-based combinations, and some more complex combinations of the outputs from subgames. Categories and Subject Descriptors F.2 [Analysis of Algorithms and Problem Complexity]: General; J.4 [Social and Behavioral Sciences]: Economics; K.4.4 [Computer and Society]: Electronic Commerce General Terms Algorithms, Economics, Theory 1. INTRODUCTION In recent years, with the rapid development of the Internet, many protocols and algorithms have been proposed to make the Internet more efficient and reliable. The Internet is a complex distributed system where a multitude of heterogeneous agents cooperate to achieve some common goals, and the existing protocols and algorithms often assume that all agents will follow the prescribed rules without deviation. However, in some settings where the agents are selfish instead of altruistic, it is more reasonable to assume these agents are rational - maximize their own profits - according to the neoclassic economics, and new models are needed to cope with the selfish behavior of such agents. Towards this end, Nisan and Ronen [14] proposed the framework of algorithmic mechanism design and applied VCG mechanisms to some fundamental problems in computer science, including shortest paths, minimum spanning trees, and scheduling on unrelated machines. The VCG mechanisms [5, 11, 21] are applicable to mechanism design problems whose outputs optimize the utilitarian objective function, which is simply the sum of all agents" valuations. Unfortunately, some objective functions are not utilitarian; even for those problems with a utilitarian objective function, sometimes it is impossible to find the optimal output in polynomial time unless P=NP. Some mechanisms other than VCG mechanism are needed to address these issues. Archer and Tardos [2] studied a scheduling problem where it is NP-Hard to find the optimal output. They pointed out that a certain monotonicity property of the output work load is a necessary and sufficient condition for the existence of a truthful mechanism for their scheduling problem. Auletta et al. [3] studied a similar scheduling problem. They provided a family of deterministic truthful (2 + )-approximation mechanisms for any fixed number of machines and several (1 + )-truthful mechanisms for some NP-hard restrictions of their scheduling problem. Lehmann et al. [12] studied the single-minded combinatorial auction and gave a√ m-approximation truthful mechanism, where m is the number of goods. They also pointed out that a certain monotonicity in the allocation rule can lead to a truthful mechanism. The work of Mu"alem and Nisan [13] is the closest in spirit to our work. They characterized all truthful mechanisms based on a certain monotonicity property in a single-minded auction setting. They also showed how to used MAX and IF-THEN-ELSE to combine outputs from subproblems. As shown in this paper, the MAX and IF-THEN-ELSE combinations are special cases of the composition-based techniques that we present in this paper for computing the payments in polynomial time under mild assumptions. More generally, we study how to design truthful mechanisms for binary demand games where the allocation of an agent is either selected or not selected. We also assume that the valuations 213 of agents are uncorrelated, i.e., the valuation of an agent only depends on its own allocation and type. Recall that a mechanism M = (O, P) consists of two parts, an allocation rule O and a payment scheme P. Previously, it is often assumed that there is an objective function g and an allocation rule O, that either optimizes g exactly or approximately. In contrast to the VCG mechanisms, we do not require that the allocation should optimize the objective function. In fact, we do not even require the existence of an objective function. Given any allocation rule O for a binary demand game, we showed that a truthful mechanism M = (O, P) exists for the game if and only if O satisfies a certain monotonicity property. The monotonicity property only guarantees the existence of a payment scheme P such that (O, P) is truthful. We complement this existence theorem with a general framework to design such a payment scheme P. Furthermore, we present general techniques to compute the payment when the output is a composition of the outputs of subgames through the operators or and and; through round-based combinations; or through intermediate results, which may be themselves computed from other subproblems. The remainder of the paper is organized as follows. In Section 2, we discuss preliminaries and previous works, define binary demand games and discuss the basic assumptions about binary demand games. In Section 3, we show that O satisfying a certain monotonicity property is a necessary and sufficient condition for the existence of a truthful mechanism M = (O, P). A framework is then proposed in Section 4 to compute the payment P in polynomial time for several types of allocation rules O. In Section 5, we provide several examples to demonstrate the effectiveness of our general framework. We conclude our paper in Section 6 with some possible future directions. 2. PRELIMINARIES 2.1 Mechanism Design As usually done in the literatures about the designing of algorithms or protocols with inputs from individual agents, we adopt the assumption in neoclassic economics that all agents are rational, i.e., they respond to well-defined incentives and will deviate from the protocol only if the deviation improves their gain. A standard model for mechanism design is as follows. There are n agents 1, . . . , n and each agent i has some private information ti, called its type, only known to itself. For example, the type ti can be the cost that agent i incurs for forwarding a packet in a network or can be a payment that the agent is willing to pay for a good in an auction. The agents" types define the type vector t = (t1, t2, . . . , tn). Each agent i has a set of strategies Ai from which it can choose. For each input vector a = (a1, . . . , an) where agent i plays strategy ai ∈ Ai, the mechanism M = (O, P) computes an output o = O(a) and a payment vector p(a) = (p1(a), . . . , pn(a)). Here the payment pi(·) is the money given to agent i and depends on the strategies used by the agents. A game is defined as G = (S, M), where S is the setting for the game G. Here, S consists the parameters of the game that are set before the game starts and do not depend on the players" strategies. For example, in a unicast routing game [14], the setting consists of the topology of the network, the source node and the destination node. Throughout this paper, unless explicitly mentioned otherwise, the setting S of the game is fixed and we are only interested in how to design P for a given allocation rule O. A valuation function v(ti, o) assigns a monetary amount to agent i for each possible output o. Everything about a game S, M , including the setting S, the allocation rule O and the payment scheme P, is public knowledge except the agent i"s actual type ti, which is private information to agent i. Let ui(ti, o) denote the utility of agent i at the outcome of the game o, given its preferences ti. Here, following a common assumption in the literature, we assume the utility for agent i is quasi-linear, i.e., ui(ti, o) = v(ti, o) + Pi(a). Let a|i ai = (a1, · · · , ai−1, ai, ai+1, · · · , an), i.e., each agent j = i plays an action aj except that the agent i plays ai. Let a−i = (a1, · · · , ai−1, ai+1, · · · , an) denote the actions of all agents except i. Sometimes, we write (a−i, bi) as a|i bi. An action ai is called dominant for i if it (weakly) maximizes the utility of i for all possible strategies b−i of other agents, i.e., ui(ti, O(b−i, ai)) ≥ ui(ti, O(b−i, ai)) for all ai = ai and b−i. A direct-revelation mechanism is a mechanism in which the only actions available to each agent are to report its private type either truthfully or falsely to the mechanism. An incentive compatible (IC) mechanism is a direct-revelation mechanism in which if an agent reports its type ti truthfully, then it will maximize its utility. Then, in a direct-revelation mechanism satisfying IC, the payment scheme should satisfy the property that, for each agent i, v(ti, O(t)) + pi(t) ≥ v(ti, O(t|i ti)) + pi(t|i ti). Another common requirement in the literature for mechanism design is so called individual rationality or voluntary participation: the agent"s utility of participating in the output of the mechanism is not less than the utility of the agent of not participating. A direct-revelation mechanism is strategproof if it satisfies both IC and IR properties. Arguably the most important positive result in mechanism design is the generalized Vickrey-Clarke-Groves (VCG) mechanism by Vickrey [21], Clarke [5], and Groves [11]. The VCG mechanism applies to (affine) maximization problems where the objective function is utilitarian g(o, t) = P i v(ti, o) (i.e., the sum of all agents" valuations) and the set of possible outputs is assumed to be finite. A direct revelation mechanism M = (O(t), P(t)) belongs to the VCG family if (1) the allocation O(t) maximizesP i v(ti, o), and (2) the payment to agent i is pi(t) = P j=i vj(tj, O(t))+ hi (t−i), where hi () is an arbitrary function of t−i. Under mild assumptions, VCG mechanisms are the only truthful implementations for utilitarian problems [10]. The allocation rule of a VCG mechanism is required to maximize the objective function in the range of the allocation function. This makes the mechanism computationally intractable in many cases. Furthermore, replacing an optimal algorithm for computing the output with an approximation algorithm usually leads to untruthful mechanisms if a VCG payment scheme is used. In this paper, we study how to design a truthful mechanism that does not optimize a utilitarian objective function. 2.2 Binary Demand Games A binary demand game is a game G = (S, M), where M = (O, P) and the range of O is {0, 1}n . In other words, the output is a n-tuple vector O(t) = (O1(t), O2(t), . . . , On(t)), where Oi(t) = 1 (respectively, 0) means that agent i is (respectively, is not) selected. Examples of binary demand games include: unicast [14, 22, 9] and multicast [23, 24, 8] (generally subgraph construction by selecting some links/nodes to satisfy some property), facility location [7], and a certain auction [12, 2, 13]. Hereafter, we make the following further assumptions. 1. The valuation of the agents are not correlated, i.e., v(ti, o) is a function of v(ti, oi) only is denoted as v(ti, oi). 2. The valuation v(ti, oi) is a publicly known value and is normalized to 0. This assumption is needed to guarantee the IR property. Thus, throughout his paper, we only consider these direct-revelation mechanisms in which every agent only needs to reveal its valuation vi = v(ti, 1). 214 Notice that in applications where agents providing service and receiving payment, e.g., unicast and job scheduling, the valuation vi of an agent i is usually negative. For the convenience of presentation, we define the cost of agent as ci = −v(ti, 1), i.e., it costs agent i ci to provide the service. Throughout this paper, we will use ci instead of vi in our analysis. All our results can apply to the case where the agents receive the service rather than provide by setting ci to negative, as in auction. In a binary demand game, if we want to optimize an objective function g(o, t), then we call it a binary optimization demand game. The main differences between the binary demand games and those problems that can be solved by VCG mechanisms are: 1. The objective function is utilitarian (or affine maximization problem) for a problem solvable by VCG while there is no restriction on the objective function for a binary demand game. 2. The allocation rule O studied here does not necessarily optimize an objective function, while a VCG mechanism only uses the output that optimizes the objective function. We even do not require the existence of an objective function. 3. We assume that the agents" valuations are not correlated in a binary demand game, while the agents" valuations may be correlated in a VCG mechanism. In this paper, we assume for technical convenience that the objective function g(o, c), if exists, is continuous with respect to the cost ci, but most of our results are directly applicable to the discrete case without any modification. 2.3 Previous Work Lehmann et al. [12] studied how to design an efficient truthful mechanism for single-minded combinatorial auction. In a singleminded combinatorial auction, each agent i (1 ≤ i ≤ n) only wants to buy a subset Si ⊆ S with private price ci. A single-minded bidder i declares a bid bi = Si, ai with Si ⊆ S and ai ∈ R+ . In [12], it is assumed that the set of goods allocated to an agent i is either Si or ∅, which is known as exactness. Lehmann et al. gave a greedy round-based allocation algorithm, based on the rank ai |Si|1/2 , that has an approximation ratio √ m, where m is the number of goods in S. Based on the approximation algorithm, they gave a truthful payment scheme. For an allocation rule satisfying (1) exactness: the set of goods allocated to an agent i is either Si or ∅; (2) monotonicity: proposing more money for fewer goods cannot cause a bidder to lose its bid, they proposed a truthful payment scheme as follows: (1) charge a winning bidder a certain amount that does not depend on its own bidding; (2) charge a losing bidder 0. Notice the assumption of exactness reveals that the single minded auction is indeed a binary demand game. Their payment scheme inspired our payment scheme for binary demand game. In [1], Archer et al. studied the combinatorial auctions where multiple copies of many different items are on sale, and each bidder i desires only one subset Si. They devised a randomized rounding method that is incentive compatible and gave a truthful mechanism for combinatorial auctions with single parameter agents that approximately maximizes the social value of the auction. As they pointed out, their method is strongly truthful in sense that it is truthful with high probability 1 − , where is an error probability. On the contrary, in this paper, we study how to design a deterministic mechanism that is truthful based on some given allocation rules. In [2], Archer and Tardos showed how to design truthful mechanisms for several combinatorial problems where each agent"s private information is naturally expressed by a single positive real number, which will always be the cost incurred per unit load. The mechanism"s output could be arbitrary real number but their valuation is a quasi-linear function t · w, where t is the private per unit cost and w is the work load. Archer and Tardos characterized that all truthful mechanism should have decreasing work curves w and that the truthful payment should be Pi(bi) = Pi(0) + biwi(bi) − R bi 0 wi(u)du Using this model, Archer and Tardos designed truthful mechanisms for several scheduling related problems, including minimizing the span, maximizing flow and minimizing the weighted sum of completion time problems. Notice when the load of the problems is w = {0, 1}, it is indeed a binary demand game. If we apply their characterization of the truthful mechanism, their decreasing work curves w implies exactly the monotonicity property of the output. But notice that their proof is heavily based on the assumption that the output is a continuous function of the cost, thus their conclusion can"t directly apply to binary demand games. The paper of Ahuva Mu"alem and Noam Nisan [13] is closest in spirit to our work. They clearly stated that we only discussed a limited class of bidders, single minded bidders, that was introduced by [12]. They proved that all truthful mechanisms should have a monotonicity output and their payment scheme is based on the cut value. With a simple generalization, we get our conclusion for general binary demand game. They proposed several combination methods including MAX, IF-THEN-ELSE construction to perform partial search. All of their methods required the welfare function associated with the output satisfying bitonic property. Distinction between our contributions and previous results: It has been shown in [2, 6, 12, 13] that for the single minded combinatorial auction, there exists a payment scheme which results in a truthful mechanism if the allocation rule satisfies a certain monotonicity property. Theorem 4 also depends on the monotonicity property, but it is applicable to a broader setting than the single minded combinatorial auction. In addition, the binary demand game studied here is different from the traditional packing IP"s: we only require that the allocation to each agent is binary and the allocation rule satisfies a certain monotonicity property; we do not put any restrictions on the objective function. Furthermore, the main focus of this paper is to design some general techniques to find the truthful payment scheme for a given allocation rule O satisfying a certain monotonicity property. 3. GENERAL APPROACHES 3.1 Properties of Strategyproof Mechanisms We discuss several properties that mechanisms need to satisfy in order to be truthful. THEOREM 1. If a mechanism M = (O, P) satisfies IC, then ∀i, if Oi(t|i ti1 ) = Oi(t|i ti2 ), then pi(t|i ti1 ) = pi(t|i ti2 ). COROLLARY 2. For any strategy-proof mechanism for a binary demand game G with setting S, if we fix the cost c−i of all agents other than i, the payment to agent i is a constant p1 i if Oi(c) = 1, and it is another constant p0 i if Oi(c) = 0. THEOREM 3. Fixed the setting S for a binary demand game, if mechanism M = (O, P) satisfies IC, then mechanism M = (O, P ) with the same output method O and pi(c) = pi(c) − δi(c−i) for any function δi(c−i) also satisfies IC. The proofs of above theorems are straightforward and thus omitted due to space limit. This theorem implies that for the binary demand games we can always normalize the payment to an agent i such that the payment to the agent is 0 when it is not selected. Hereafter, we will only consider normalized payment schemes. 215 3.2 Existence of Strategyproof Mechanisms Notice, given the setting S, a mechanism design problem is composed of two parts: the allocation rule O and a payment scheme P. In this paper, given an allocation rule O we focus our attention on how to design a truthful payment scheme based on O. Given an allocation rule O for a binary demand game, we first present a sufficient and necessary condition for the existence of a truthful payment scheme P. DEFINITION 1 (MONOTONE NON-INCREASING PROPERTY (MP)). An output method O is said to satisfy the monotone non-increasing property if for every agent i and two of its possible costs ci1 < ci2 , Oi(c|i ci2 ) ≤ Oi(c|i ci1 ). This definition is not restricted only to binary demand games. For binary demand games, this definition implies that if Oi(c|i ci2 ) = 1 then Oi(c|i ci1 ) = 1. THEOREM 4. Fix the setting S, c−i in a binary demand game G with the allocation rule O, the following three conditions are equivalent: 1. There exists a value κi(O, c−i)(which we will call a cut value, such that Oi(c) = 1 if ci < κi(O, c−i) and Oi(c) = 0 if ci > κi(O, c−i). When ci = κi(O, c−i), Oi(c) can be either 0 or 1 depending on the tie-breaker of the allocation rule O. Hereafter, we will not consider the tie-breaker scenario in our proofs. 2. The allocation rule O satisfies MP. 3. There exists a truthful payment scheme P for this binary demand game. PROOF. The proof that Condition 2 implies Condition is straightforward and is omitted here. We then show Condition 3 implies Condition 2. The proof of this is similar to a proof in [13]. To prove this direction, we assume there exists an agent i and two valuation vectors c|i ci1 and c|i ci2 , where ci1 < ci2 , Oi(c|i ci2 ) = 1 and Oi(c|i ci1 ) = 0. From corollary 2, we know that pi(c|i ci1 ) = p0 i and pi(c|i ci2 ) = p1 i . Now fix c−i, the utility for i when ci = ci1 is ui(ci1 ) = p0 i . When agent i lies its valuation to ci2 , its utility is p1 i − ci1 . Since M = (O, P) is truthful, we have p0 i > p1 i − ci1 . Now consider the scenario when the actual valuation of agent i is ci = ci2 . Its utility is p1 i − ci2 when it reports its true valuation. Similarly, if it lies its valuation to ci1 , its utility is p0 i . Since M = (O, P) is truthful, we have p0 i < p1 i − ci2 . Consequently, we have p1 i −ci2 > p0 i > p1 i −ci1 . This inequality implies that ci1 > ci2 , which is a contradiction. We then show Condition 1 implies Condition 3. We prove this by constructing a payment scheme and proving that this payment scheme is truthful. The payment scheme is: If Oi(c) = 1, then agent i gets payment pi(c) = κi(O, c−i); else it gets payment pi(c) = 0. From condition 1, if Oi(c) = 1 then ci > κi(O, c−i). Thus, its utility is κi(O, c−i) − ci > 0, which implies that the payment scheme satisfies the IR. In the following we prove that this payment scheme also satisfies IC property. There are two cases here. Case 1: ci < κ(O, c−i). In this case, when i declares its true cost ci, its utility is κi(O, c−i) − ci > 0. Now consider the situation when i declares a cost di = ci. If di < κi(O, c−i), then i gets the same payment and utility since it is still selected. If di > κi(O, c−i), then its utility becomes 0 since it is not selected anymore. Thus, it has no incentive to lie in this case. Case 2: ci ≥ κ(O, c−i). In this case, when i reveals its true valuation, its payment is 0 and the utility is 0. Now consider the situation when i declares a valuation di = ci. If di > κi(O, c−i), then i gets the same payment and utility since it is still not selected. If di ≤ κi(O, c−i), then its utility becomes κi(O, c−i) − ci ≤ 0 since it is selected now. Thus, it has no incentive to lie. The equivalence of the monotonicity property of the allocation rule O and the existence of a truthful mechanism using O can be extended to games beyond binary demand games. The details are omitted here due to space limit. We now summarize the process to design a truthful payment scheme for a binary demand game based on an output method O. General Framework 1 Truthful mechanism design for a binary demand game Stage 1: Check whether the allocation rule O satisfies MP. If it does not, then there is no payment scheme P such that mechanism M = (O, P) is truthful. Otherwise, define the payment scheme P as follows. Stage 2: Based on the allocation rule O, find the cut value κi(O, c−i) for agent i such that Oi(c|i di) = 1 when di < κi(O, c−i), and Oi(c|i di) = 0 when di > κi(O, c−i). Stage 3: The payment for agent i is 0 if Oi(c) = 0; the payment is κi(O, c−i) if Oi(c) = 1. THEOREM 5. The payment defined by our general framework is minimum among all truthful payment schemes using O as output. 4. COMPUTING CUT VALUE FUNCTIONS To find the truthful payment scheme by using General Framework 1, the most difficult stage seems to be the stage 2. Notice that binary search does not work generally since the valuations of agents may be continuous. We give some general techniques that can help with finding the cut value function under certain circumstances. Our basic approach is as follows. First, we decompose the allocation rule into several allocation rules. Next find the cut value function for each of these new allocation rules. Then, we compute the original cut value function by combining these cut value functions of the new allocation rules. 4.1 Simple Combinations In this subsection, we introduce techniques to compute the cut value function by combining multiple allocation rules with conjunctions or disconjunctions. For simplicity, given an allocation rule O, we will use κ(O, c) to denote a n-tuple vector (κ1(O, c−1), κ2(O, c−2), . . . , κn(O, c−n)). Here, κi(O, c−i) is the cut value for agent i when the allocation rule is O and the costs c−i of all other agents are fixed. THEOREM 6. With a fixed setting S of a binary demand game, assume that there are m allocation rules O1 , O2 , · · · , Om satisfying the monotonicity property, and κ(Oi , c) is the cut value vector for Oi . Then the allocation rule O(c) = Wm i=1 Oi (c) satisfies the monotonicity property. Moreover, the cut value for O is κ(O, c) = maxm i=1{κ(Oi , c)} Here κ(O, c) = maxm i=1{κ(Oi , c)} means, ∀j ∈ [1, n], κj(O, c−j) = maxm i=1{κj(Oi , c−j)} and O(c) =Wm i=1 Oi (c) means, ∀j ∈ [1, n], Oj(c) = O1 j (c) ∨ O2 j (c) ∨ · · · ∨ Om j (c). PROOF. Assume that ci > ci and Oi(c) = 1. Without loss of generality, we assume that Ok i (c) = 1 for some k, 1 ≤ k ≤ m. From the assumption that Ok i (c) satisfies MP, we obtain that 216 Ok i (c|i ci) = 1. Thus, Oi(c|i ci) = Wm j=1 Oj (c) = 1. This proves that O(c) satisfies MP. The correctness of the cut value function follows directly from Theorem 4. Many algorithms indeed fall into this category. To demonstrate the usefulness of Theorem 6, we discuss a concrete example here. In a network, sometimes we want to deliver a packet to a set of nodes instead of one. This problem is known as multicast. The most commonly used structure in multicast routing is so called shortest path tree (SPT). Consider a network G = (V, E, c), where V is the set of nodes, and vector c is the actual cost of the nodes forwarding the data. Assume that the source node is s and the receivers are Q ⊂ V . For each receiver qi ∈ Q, we compute the shortest path (least cost path), denoted by LCP(s, qi, d), from the source s to qi under the reported cost profile d. The union of all such shortest paths forms the shortest path tree. We then use General Framework 1 to design the truthful payment scheme P when the SPT structure is used as the output for multicast, i.e., we design a mechanism M = (SPT, P). Notice that VCG mechanisms cannot be applied here since SPT is not an affine maximization. We define LCP(s,qi) as the allocation corresponds to the path LCP(s, qi, d), i.e., LCP (s,qi) k (d) = 1 if and only if node vk is in LCP(s, qi, d). Then the output SPT is defined as W qi∈Q LCP(s,qi) . In other words, SPTk(d) = 1 if and only if qk is selected in some LCP(s, qi, d). The shortest path allocation rule is a utilitarian and satisfies MP. Thus, from Theorem 6, SPT also satisfies MP, and the cut value function vector for SPT can be calculated as κ(SPT, c) = maxqi∈Q κ(LCP(s,qi) , c), where κ(LCP(s,qi) , c) is the cut value function vector for the shortest path LCP(s, qi, c). Consequently, the payment scheme above is truthful and the minimum among all truthful payment schemes when the allocation rule is SPT. THEOREM 7. Fixed the setting S of a binary demand game, assume that there are m output methods O1 , O2 , · · · , Om satisfying MP, and κ(Oi , c) are the cut value functions respectively for Oi where i = 1, 2, · · · , m. Then the allocation rule O(c) =Vm i=1 Oi (c) satisfies MP. Moreover, the cut value function for O is κ(O, c) = minm i=1{κ(Oi , c)}. We show that our simple combination generalizes the IF-THENELSE function defined in [13]. For an agent i, assume that there are two allocation rules O1 and O2 satisfying MP. Let κi(O1 , c−i), κi(O2 , c−i) be the cut value functions for O1 , O2 respectively. Then the IF-THEN-ELSE function Oi(c) is actually Oi(c) = [(ci ≤ κi(O1 , c−i) + δ1(c−i)) ∧ O2 (c−i, ci)] ∨ (ci < κi(O1 , c−i) − δ2(c−i)) where δ1(c−i) and δ2(c−i) are two positive functions. By applying Theorems 6 and 7, we know that the allocation rule O satisfies MP and consequently κi(O, c−i) = max{min(κi(O1 , c−i)+ δ1(c−i), κi(O2 , c−i)), κi(O1 , c−i) − δ2(c−i))}. 4.2 Round-Based Allocations Some approximation algorithms are round-based, where each round of an algorithm selects some agents and updates the setting and the cost profile if necessary. For example, several approximation algorithms for minimum weight vertex cover [19], maximum weight independent set, minimum weight set cover [4], and minimum weight Steiner [18] tree fall into this category. As an example, we discuss the minimum weighted vertex cover problem (MWVC) [16, 15] to show how to compute the cut value for a round-based output. Given a graph G = (V, E), where the nodes v1, v2, . . . , vn are the agents and each agent vi has a weight ci, we want to find a node set V ⊆ V such that for every edge (u, v) ∈ E at least one of u and v is in V . Such V is called a vertex cover of G. The valuation of a node i is −ci if it is selected; otherwise its valuation is 0. For a subset of nodes V ∈ V , we define its weight as c(V ) = P i∈V ci. We want to find a vertex cover with the minimum weight. Hence, the objective function to be implemented is utilitarian. To use the VCG mechanism, we need to find the vertex cover with the minimum weight, which is NP-hard [16]. Since we are interested in mechanisms that can be computed in polynomial time, we must use polynomial-time computable allocation rules. Many algorithms have been proposed in the literature to approximate the optimal solution. In this paper, we use a 2-approximation algorithm given in [16]. For the sake of completeness, we briefly review this algorithm here. The algorithm is round-based. Each round selects some vertices and discards some vertices. For each node i, w(i) is initialized to its weight ci, and when w(i) drops to 0, i is included in the vertex cover. To make the presentation clear, we say an edge (i1, j1) is lexicographically smaller than edge (i2, j2) if (1) min(i1, j1) < min(i2, j2), or (2) min(i1, j1) = min(i2, j2) and max(i1, j1) < max(i2, j2). Algorithm 2 Approximate Minimum Weighted Vertex Cover Input: A node weighted graph G = (V, E, c). Output: A vertex cover V . 1: Set V = ∅. For each i ∈ V , set w(i) = ci. 2: while V is not a vertex cover do 3: Pick an uncovered edge (i, j) with the least lexicographic order among all uncovered edges. 4: Let m = min(w(i), w(j)). 5: Update w(i) to w(i) − m and w(j) to w(j) − m. 6: If w(i) = 0, add i to V . If w(j) = 0, add j to V . Notice, selecting an edge using the lexicographic order is crutial to guarantee the monotonicity property. Algorithm 2 outputs a vertex cover V whose weight is within 2 times of the optimum. For convenience, we use VC(c) to denote the vertex cover computed by Algorithm 2 when the cost vector of vertices is c. Below we generalize Algorithm 2 to a more general scenario. Typically, a round-based output can be characterized as follows (Algorithm 3). DEFINITION 2. An updating rule Ur is said to be crossingindependent if, for any agent i not selected in round r, (1) Sr+1 and cr+1 −i do not depend on cr j (2) for fixed cr −i, cr i1 ≤ cr i2 implies that cr+1 i1 ≤ cr+1 i2 . We have the following theorem about the existence of a truthful payment using a round based allocation rule A. THEOREM 8. A round-based output A, with the framework defined in Algorithm 3, satisfies MP if the output methods Or satisfy MP and all updating rules Ur are crossing-independent. PROOF. Consider an agent i and fixed c−i. We prove that when an agent i is selected with cost ci, then it is also selected with cost di < ci. Assume that i is selected in round r with cost ci. Then under cost di, if agent i is selected in a round before r, our claim holds. Otherwise, consider in round r. Clearly, the setting Sr and the costs of all other agents are the same as what if agent i had cost ci since i is not selected in the previous rounds due to the crossindependent property. Since i is selected in round r with cost ci, i is also selected in round r with di < ci due to the reason that Or satisfies MP. This finishes the proof. 217 Algorithm 3 A General Round-Based Allocation Rule A 1: Set r = 0, c0 = c, and G0 = G initially. 2: repeat 3: Compute an output or using a deterministic algorithm Or : Sr × cr → {0, 1}n . Here Or , cr and Sr are allocation rule, cost vector and game setting in game Gr , respectively. Remark: Or is often a simple greedy algorithm such as selecting the agents that minimize some utilitarian function. For the example of vertex cover, Or will always select the light-weighted node on the lexicographically least uncovered edge (i, j). 4: Let r = r + 1. Update the game Gr−1 to obtain a new game Gr with setting Sr and cost vector cr according to some rule Ur : Or−1 × (Sr−1 , cr−1 ) → (Sr , cr ). Here we updates the cost and setting of the game. Remark: For the example of vertex cover, the updating rule will decrease the weight of vertices i and j by min(w(i), w(j)). 5: until a valid output is found 6: Return the union of the set of selected players of each round as the final output. For the example of vertex cover, it is the union of nodes selected in all rounds. Algorithm 4 Compute Cut Value for Round-Based Algorithms Input: A round-based output A, a game G1 = G, and a updating function vector U. Output: The cut value x for agent k. 1: Set r = 0 and ck = ζ. Recall that ζ is a value that can guarantee Ak = 0 when an agent reports the cost ζ. 2: repeat 3: Compute an output or using a deterministic algorithm based on setting Sr using allocation rule Or : Sr ×cr → {0, 1}n . 4: Find the cut value for agent k based on the allocation rule Or for costs cr −k. Let r = κk(Or , cr −k) be the cut value. 5: Set r = r + 1 and obtain a new game Gr from Gr−1 and or according to the updating rule Ur . 6: Let cr be the new cost vector for game Gr . 7: until a valid output is found. 8: Let gi(x) be the cost of ci k when the original cost vector is c|k x. 9: Find the minimum value x such that 8 >>>>>< >>>>>: g1(x) ≥ 1; g2(x) ≥ 2; ... gt−1(x) ≥ t−1; gt(x) ≥ t. Here, t is the total number of rounds. 10: Output the value x as the cut value. If the round-based output satisfies monotonicity property, the cut-value always exists. We then show how to find the cut value for a selected agent k in Algorithm 4. The correctness of Algorithm 4 is straightforward. To compute the cut value, we assume that (1) the cut value r for each round r can be computed in polynomial time; (2) we can solve the equation gr(x) = r to find x in polynomial time when the cost vector c−i and b are given. Now we consider the vertex cover problem. For each round r, we select a vertex with the least weight and that is incident on the lexicographically least uncovered edge. The output satisfies MP. For agent i, we update its cost to cr i − cr j iff edge (i, j) is selected. It is easy to verify this updating rule is crossing-independent, thus we can apply Algorithm 4 to compute the cut value for the set cover game as shown in Algorithm 5. Algorithm 5 Compute Cut Value for MVC. Input: A node weighted graph G = (V, E, c) and a node k selected by Algorithm 2. Output: The cut value κk(V C, c−k). 1: For each i ∈ V , set w(i) = ci. 2: Set w(k) = ∞, pk = 0 and V = ∅. 3: while V is not a vertex cover do 4: Pick an uncovered edge (i, j) with the least lexicographic order among all uncovered edges. 5: Set m = min(w(i), w(j)). 6: Update w(i) = w(i) − m and w(j) = w(j) − m. 7: If w(i) = 0, add i to V ; else add j to V . 8: If i == k or j == k then set pk = pk + m. 9: Output pk as the cut value κk(V C, c−k). 4.3 Complex Combinations In subsection 4.1, we discussed how to find the cut value function when the output of the binary demand game is a simple combination of some outputs, whose cut values can be computed through other means (typically VCG). However, some algorithms cannot be decomposed in the way described in subsection 4.1. Next we present a more complex way to combine allocation rules, and as we may expected, the way to find the cut value is also more complicated. Assume that there are n agents 1 ≤ i ≤ n with cost vector c, and there are m binary demand games Gi with objective functions fi(o, c), setting Si and allocation rule ψi where i = 1, 2, · · · , m. There is another binary demand game with setting S and allocation rule O, whose input is a cost vector d = (d1, d2, · · · , dm). Let f be the function vector (f1, f2, · · · , fm), ψ be the allocation rule vector (ψ1 , ψ2 , · · · , ψm ) and ∫ be the setting vector (S1, S2, · · · , Sm). For notation simplicity, we define Fi(c) = fi(ψi (c), c), for each 1 ≤ i ≤ m, and F(c) = (F1(c), F2(c), · · · , Fm(c)). Let us see a concrete example of these combinations. Consider a link weighted graph G = (V, E, c), and a subset of q nodes Q ⊆ V . The Steiner tree problem is to find a set of links with minimum total cost to connect Q. One way to find an approximation of the Steiner tree is as follows: (1) we build a virtual complete graph H using Q as its vertices, and the cost of each edge (i, j) is the cost of LCP(i, j, c) in graph G; (2) build the minimum spanning tree of H, denoted as MST(H); (3) an edge of G is selected iff it is selected in some LCP(i, j, c) and edge (i, j) of H is selected to MST(H). In this game, we define q(q − 1)/2 games Gi,j, where i, j ∈ Q, with objective functions fi,j(o, c) being the minimum cost of 218 connecting i and j in graph G, setting Si being the original graph G and allocation rule is LCP(i, j, c). The game G corresponds to the MST game on graph H. The cost of the pair-wise q(q − 1)/2 shortest paths defines the input vector d = (d1, d2, · · · , dm) for game MST. More details will be given in Section 5.2. DEFINITION 3. Given an allocation rule O and setting S, an objective function vector f, an allocation rule vector ψ and setting vector ∫, we define a compound binary demand game with setting S and output O ◦ F as (O ◦ F)i(c) = Wm j=1(Oj(F(c)) ∧ ψj i (c)). The allocation rule of the above definition can be interpreted as follows. An agent i is selected if and only if there is a j such that (1) i is selected in ψj (c), and (2) the allocation rule O will select index j under cost profile F(c). For simplicity, we will use O ◦ F to denote the output of this compound binary demand game. Notice that a truthful payment scheme using O ◦ F as output exists if and only if it satisfies the monotonicity property. To study when O ◦F satisfies MP, several necessary definitions are in order. DEFINITION 4. Function Monotonicity Property (FMP) Given an objective function g and an allocation rule O, a function H(c) = g(O(c), c) is said to satisfy the function monotonicity property, if, given fixed c−i, it satisfies: 1. When Oi(c) = 0, H(c) does not increase over ci. 2. When Oi(c) = 1, H(c) does not decrease over ci. DEFINITION 5. Strong Monotonicity Property (SMP) An allocation rule O is said to satisfy the strong monotonicity property if O satisfies MP, and for any agent i with Oi(c) = 1 and agent j = i, Oi(c|j cj) = 1 if cj ≥ cj or Oj(c|j cj) = 0. LEMMA 1. For a given allocation rule O satisfying SMP and cost vectors c, c with ci = ci, if Oi(c) = 1 and Oi(c ) = 0, then there must exist j = i such that cj < cj and Oj(c ) = 1. From the definition of the strong monotonicity property, we have Lemma 1 directly. We now can give a sufficient condition when O ◦ F satisfies the monotonicity property. THEOREM 9. If ∀i ∈ [1, m], Fi satisfies FMP, ψi satisfies MP, and the output O satisfies SMP, then O ◦ F satisfies MP. PROOF. Assuming for cost vector c we have (O ◦ F)i(c) = 1, we should prove for any cost vector c = c|i ci with ci < ci, (O ◦ F)i(c ) = 1. Noticing that (O ◦ F)i(c) = 1, without loss of generality, we assume that Ok(F(c)) = 1 and ψk i (c) = 1 for some index 1 ≤ k ≤ m. Now consider the output O with the cost vector F(c )|k Fk(c). There are two scenarios, which will be studied one by one as follows. One scenario is that index k is not chosen by the output function O. From Lemma 1, there must exist j = k such that Fj(c ) < Fj(c) (1) Oj(F(c )|k Fk(c)) = 1 (2) We then prove that agent i will be selected in the output ψj (c ), i.e., ψj i (c ) = 1. If it is not, since ψj (c) satisfies MP, we have ψj i (c) = ψj i (c ) = 0 from ci < ci. Since Fj satisfies FMP, we know Fj(c ) ≥ Fj(c), which is a contradiction to the inequality (1). Consequently, we have ψj i (c ) = 1. From Equation (2), the fact that index k is not selected by allocation rule O and the definition of SMP, we have Oj(F(c )) = 1, Thus, agent i is selected by O ◦ F because of Oj(F(c )) = 1 and ψj i (c ) = 1. The other scenario is that index k is chosen by the output function O. First, agent i is chosen in ψk (c ) since the output ψk (c) satisfies the monotonicity property and ci < ci and ψk i (c) = 1. Secondly, since the function Fk satisfies FMP, we know that Fk(c ) ≤ Fk(c). Remember that output O satisfies the SMP, thus we can obtain Ok(F(c )) = 1 from the fact that Ok(F(c )|k Fk(c)) = 1 and Fk(c ) ≤ Fk(c). Consequently, agent i will also be selected in the final output O ◦ F. This finishes our proof. This theorem implies that there is a cut value for the compound output O ◦ F. We then discuss how to find the cut value for this output. Below we will give an algorithm to calculate κi(O ◦ F) when (1) O satisfies SMP, (2) ψj satisfies MP, and (3) for fixed c−i, Fj(c) is a constant, say hj, when ψj i (c) = 0, and Fj(c) increases when ψj i (c) = 1. Notice that here hj can be easily computed by setting ci = ∞ since ψj satisfies the monotonicity property. When given i and fixed c−i, we define (Fi j )−1 (y) as the smallest x such that Fj(c|i x) = y. For simplicity, we denote (Fi j )−1 as F−1 j if no confusion is caused when i is a fixed agent. In this paper, we assume that given any y, we can find such x in polynomial time. Algorithm 6 Find Cut Value for Compound Method O ◦ F Input: allocation rule O, objective function vector F and inverse function vector F−1 = {F−1 1 , · · · , F−1 m }, allocation rule vector ψ and fixed c−i. Output: Cut value for agent i based on O ◦ F. 1: for 1 ≤ j ≤ m do 2: Compute the outputs ψj (ci). 3: Compute hj = Fj(c|i ∞). 4: Use h = (h1, h2, · · · , hm) as the input for the output function O. Denote τj = κj(O, h−j) as the cut value function of output O based on input h. 5: for 1 ≤ j ≤ m do 6: Set κi,j = F−1 j (min{τj, hj}). 7: The cut value for i is κi(O ◦ F, c−i) = maxm j=1 κi,j. THEOREM 10. Algorithm 6 computes the correct cut value for agent i based on the allocation rule O ◦ F. PROOF. In order to prove the correctness of the cut value function calculated by Algorithm 6, we prove the following two cases. For our convenience, we will use κi to represent κi(O ◦ F, c−i) if no confusion caused. First, if di < κi then (O ◦ F)i(c|i di) = 1. Without loss of generality, we assume that κi = κi,j for some j. Since function Fj satisfies FMP and ψj i (c|i di) = 1, we have Fj(c|i di) < Fj(κi). Notice di < κi,j, from the definition of κi,j = F−1 j (min{τj, hj}) we have (1) ψj i (c|i di) = 1, (2) Fj(c|i di) < τj due to the fact that Fj(x) is a non-decreasing function when j is selected. Thus, from the monotonicity property of O and τj is the cut value for output O, we have Oj(h|j Fj(c|i di)) = 1. (3) If Oj(F(c|i di)) = 1 then (O◦F)i(c|i di) = 1. Otherwise, since O satisfies SMP, Lemma 1 and equation 3 imply that there exists at least one index k such that Ok(F(c|i di)) = 1 and Fk(c|i di) < hk. Note Fk(c|i di) < hk implies that i is selected in ψk (c|i di) since hk = Fk(ci|i ∞). In other words, agent i is selected in O◦F. 219 Second, if di ≥ κi(O ◦ F, c−i) then (O ◦ F)i(c|i di) = 0. Assume for the sake of contradiction that (O ◦ F)i(c|i di) = 1. Then there exists an index 1 ≤ j ≤ m such that Oj(F(c|i di)) = 1 and ψj i (c|i di) = 1. Remember that hk ≥ Fk(c|i di) for any k. Thus, from the fact that O satisfies SMP, when changing the cost vector from F(c|i di) to h|j Fj(c|i di), we still have Oj(h|j Fj(c|i di)) = 1. This implies that Fj(c|i di) < τj. Combining the above inequality and the fact that Fj(c|i c|i di) < hj, we have Fj(c|i di) < min{hj, τj}. This implies di < F−1 j (min{hj, τj}) = κi,j < κi(O ◦ F, c−i). which is a contradiction. This finishes our proof. In most applications, the allocation rule ψj implements the objective function fj and fj is utilitarian. Thus, we can compute the inverse of F−1 j efficiently. Another issue is that it seems the conditions when we can apply Algorithm 6 are restrictive. However, lots of games in practice satisfy these properties and here we show how to deduct the MAX combination in [13]. Assume A1 and A2 are two allocation rules for single minded combinatorial auction, then the combination MAX(A1, A2) returns the allocation with the larger welfare. If algorithm A1 and A2 satisfy MP and FMP, the operation max(x, y) which returns the larger element of x and y satisfies SMP. From Theorem 9 we obtain that combination MAX(A1, A2) also satisfies MP. Further, the cut value of the MAX combination can be found by Algorithm 6. As we will show in Section 5, the complex combination can apply to some more complicated problems. 5. CONCRETE EXAMPLES 5.1 Set Cover In the set cover problem, there is a set U of m elements needed to be covered, and each agent 1 ≤ i ≤ n can cover a subset of elements Si with a cost ci. Let S = {S1, S2, · · · , Sn} and c = (c1, c2, · · · , cn). We want to find a subset of agents D such that U ⊆ S i∈D Si. The selected subsets is called the set cover for U. The social efficiency of the output D is defined as P i∈D ci, which is the objective function to be minimized. Clearly, this is a utilitarian and thus VCG mechanism can be applied if we can find the subset of S that covers U with the minimum cost. It is well-known that finding the optimal solution is NP-hard. In [4], an algorithm of approximation ratio of Hm has been proposed and it has been proved that this is the best ratio possible for the set cover problem. For the completeness of presentation, we review their method here. Algorithm 7 Greedy Set Cover (GSC) Input: Agent i"s subset Si covered and cost ci. (1 ≤ i ≤ n). Output: A set of agents that can cover all elements. 1: Initialize r = 1, T0 = ∅, and R = ∅. 2: while R = U do 3: Find the set Sj with the minimum density cj |Sj −Tr| . 4: Set Tr+1 = Tr S Sj and R = R S j. 5: r = r + 1 6: Output R. Let GSC(S) be the sets selected by the Algorithm 7.Notice that the output set is a function of S and c. Some works assume that the type of an agent could be ci, i.e., Si is assumed to be a public knowledge. Here, we consider a more general case in which the type of an agent is (Si, ci). In other words, we assume that every agent i can not only lie about its cost ci but also can lie about the set Si. This problem now looks similar to the combinatorial auction with single minded bidder studied in [12], but with the following differences: in the set cover problem we want to cover all the elements and the sets chosen can have some overlap while in combinatorial auction the chosen sets are disjoint. We can show that the mechanism M = (GSC, PV CG ), using Algorithm 7 to find a set cover and apply VCG mechanism to compute the payment to the selected agents, is not truthful. Obviously, the set cover problem is a binary demand game. For the moment, we assume that agent i won"t be able to lie about Si. We will drop this assumption later. We show how to design a truthful mechanism by applying our general framework. 1. Check the monotonicity property: The output of Algorithm 7 is a round-based output. Thus, for an agent i, we first focus on the output of one round r. In round r, if i is selected by Algorithm 7, then it has the minimum ratio ci |Si−Tr| among all remaining agents. Now consider the case when i lies its cost to ci < ci, obviously ci |Si−Tr| is still minimum among all remaining agents. Consequently, agent i is still selected in round r, which means the output of round r satisfies MP. Now we look into the updating rules. For every round, we only update the Tr+1 = Tr S Sj and R = R S j, which is obviously cross-independent. Thus, by applying Theorem 8, we know the output by Algorithm 7 satisfies MP. 2. Find the cut value: To calculate the cut value for agent i with fixed cost vector c−i, we follow the steps in Algorithm 4. First, we set ci = ∞ and apply Algorithm 7. Let ir be the agent selected in round r and T−i r+1 be the corresponding set. Then the cut value of round r is r = cir |Sir − T−i r | · |Si − T−i r |. Remember the updating rule only updates the game setting but not the cost of the agent, thus we have gr(x) = x ≥ r for 1 ≤ r ≤ t. Therefore, the final cut value for agent i is κi(GSC, c−i) = max r { cir |Sir − T−i r | · |Si − T−i r |} The payment to an agent i is κi if i is selected; otherwise its payment is 0. We now consider the scenario when agent i can lie about Si. Assume that agent i cannot lie upward, i.e., it can only report a set Si ⊆ Si. We argue that agent i will not lie about its elements Si. Notice that the cut value computed for round r is r = cir |Sir −T −i r | · |Si − T−i r |. Obviously |Si − T−i r | ≤ |Si − T−i r | for any Si ⊆ Si. Thus, lying its set as Si will not increase the cut value for each round. Thus lying about Si will not improve agent i"s utility. 5.2 Link Weighted Steiner Trees Consider any link weighted network G = (V, E, c), where E = {e1, e2, · · · , em} are the set of links and ci is the weight of the link ei. The link weighted Steiner tree problem is to find a tree rooted at source node s spanning a given set of nodes Q = {q1, q2, · · · , qk} ⊂ V . For simplicity, we assume that qi = vi, for 1 ≤ i ≤ k. Here the links are agents. The total cost of links in a graph H ⊆ G is called the weight of H, denoted as ω(H). It is NP-hard to find the minimum cost multicast tree when given an arbitrary link weighted 220 graph G [17, 20]. The currently best polynomial time method has approximation ratio 1 + ln 3 2 [17]. Here, we review and discuss the first approximation method by Takahashi and Matsuyama [20]. Algorithm 8 Find LinkWeighted SteinerTree (LST) Input: Network G = (V, E, c) where c is the cost vector for link set E. Source node s and receiver set Q. Output: A tree LST rooted at s and spanned all receivers. 1: Set r = 1, G1 = G, Q1 = Q and s1 = s. 2: repeat 3: In graph Gr, find the receiver, say qi, that is closest to the source s, i.e., LCP(s, qi, c) has the least cost among the shortest paths from s to all receivers in Qr . 4: Select all links on LCP(s, qi, c) as relay links and set their cost to 0. The new graph is denoted as Gr+1. 5: Set tr as qi and Pr = LCP(s, qi, c). 6: Set Qr+1 = Qr \qi and r = r + 1. 7: until all receivers are spanned. Hereafter, let LST(G) be the final tree constructed using the above method. It is shown in [24] that mechanism M = (LST, pV CG ) is not truthful, where pV CG is the payment calculated based on VCG mechanism. We then show how to design a truthful payment scheme using our general framework. Observe that the output Pr, for any round r, satisfies MP, and the update rule for every round satisfies crossing-independence. Thus, from Theorem 8, the roundbased output LST satisfies MP. In round r, the cut value for a link ei can be obtained by using the VCG mechanism. Now we set ci = ∞ and execute Algorithm 8. Let w−i r (ci) be the cost of the path Pr(ci) selected in the rth round and Πi r(ci) be the shortest path selected in round r if the cost of ci is temporarily set to −∞. Then the cut value for round r is r = wi r(c−i) − |Πi r(c−i)| where |Πi r(c−i)| is the cost of the path Πi r(c−i) excluding node vi. Using Algorithm 4, we obtain the final cut value for agent i: κi(LST, c−i) = maxr{ r}. Thus, the payment to a link ei is κi(LST, c−i) if its reported cost is di < κi(LST, d−i); otherwise, its payment is 0. 5.3 Virtual Minimal Spanning Trees To connect the given set of receivers to the source node, besides the Steiner tree constructed by the algorithms described before, a virtual minimum spanning tree is also often used. Assume that Q is the set of receivers, including the sender. Assume that the nodes in a node-weighted graph are all agents. The virtual minimum spanning tree is constructed as follows. Algorithm 9 Construct VMST 1: for all pairs of receivers qi, qj ∈ Q do 2: Calculate the least cost path LCP(qi, qj, d). 3: Construct a virtual complete link weighted graph K(d) using Q as its node set, where the link qiqj corresponds to the least cost path LCP(qi, qj, d), and its weight is w(qiqj) = |LCP(qi, qj, d)|. 4: Build the minimum spanning tree on K(d), denoted as V MST(d). 5: for every virtual link qiqj in V MST(d) do 6: Find the corresponding least cost path LCP(qi, qj, d) in the original network. 7: Mark the agents on LCP(qi, qj, d) selected. The mechanism M = (V MST, pV CG ) is not truthful [24], where the payment pV CG to a node is based on the VCG mechanism. We then show how to design a truthful mechanism based on the framework we described. 1. Check the monotonicity property: Remember that in the complete graph K(d), the weight of a link qiqj is |LCP(qi, qj, d)|. In other words, we implicitly defined |Q|(|Q| − 1)/2 functions fi,j, for all i < j and qi ∈ Q and qj ∈ Q, with fi,j(d) = |LCP(qi, qj, d)|. We can show that the function fi,j(d) = |LCP(qi, qj, d)| satisfies FMP, LCP satisfies MP, and the output MST satisfies SMP. From Theorem 9, the allocation rule VMST satisfies the monotonicity property. 2. Find the cut value: Notice VMST is the combination of MST and function fi,j, so cut value for VMST can be computed based on Algorithm 6 as follows. (a) Given a link weighted complete graph K(d) on Q, we should find the cut value function for edge ek = (qi, qj) based on MST. Given a spanning tree T and a pair of terminals p and q, clearly there is a unique path connecting them on T. We denote this path as ΠT (p, q), and the edge with the maximum length on this path as LE(p, q, T). Thus, the cut value can be represented as κk(MST, d) = LE(qi, qj, MST(d|k ∞)) (b) We find the value-cost function for LCP. Assume vk ∈ LCP(qi, qj, d), then the value-cost function is xk = yk − |LCPvk (qi, qj, d|k 0)|. Here, LCPvk (qi, qj, d) is the least cost path between qi and qj with node vk on this path. (c) Remove vk and calculate the value K(d|k ∞). Set h(i,j) = |LCP(qi, qj, d|∞ ))| for every pair of node i = j and let h = {h(i,j)} be the vector. Then it is easy to show that τ(i,j) = |LE(qi, qj, MST(h|(i,j) ∞))| is the cut value for output VMST. It easy to verify that min{h(i,j), τ(i,j)} = |LE(qi, qj, MST(h)|. Thus, we know κ (i,j) k (V MST, d) is |LE(qi, qj, MST(h)|− |LCPvk (qi, qj, d|k 0)|. The cut value for agent k is κk(V MST, d−k) = max0≤i,j≤r κij k (V MST, d−k). 3. We pay agent k κk(V MST, d−k) if and only if k is selected in V MST(d); else we pay it 0. 5.4 Combinatorial Auctions Lehmann et al. [12] studied how to design an efficient truthful mechanism for single-minded combinatorial auction. In a singleminded combinatorial auction, there is a set of items S to be sold and there is a set of agents 1 ≤ i ≤ n who wants to buy some of the items: agent i wants to buy a subset Si ⊆ S with maximum price mi. A single-minded bidder i declares a bid bi = Si, ai with Si ⊆ S and ai ∈ R+ . Two bids Si, ai and Sj, aj conflict if Si ∩ Sj = ∅. Given the bids b1, b2, · · · , bn, they gave a greedy round-based algorithm as follows. First the bids are sorted by some criterion ( ai |Si|1/2 is used in[12]) in an increasing order and let L be the list of sorted bids. The first bid is granted. Then the algorithm exams each bid of L in order and grants the bid if it does not conflict with any of the bids previously granted. If it does, it is denied. They proved that this greedy allocation scheme using criterion ai |Si|1/2 approximates the optimal allocation within a factor of √ m, where m is the number of goods in S. In the auction settings, we have ci = −ai. It is easy to verify the output of the greedy algorithm is a round-based output. Remember after bidder j is selected for round r, every bidder has conflict 221 with j will not be selected in the rounds after. This equals to update the cost of every bidder having conflict with j to 0, which satisfies crossing-independence. In addition, in any round, if bidder i is selected with ai then it will still be selected when it declares ai > ai. Thus, for every round, it satisfies MP and the cut value is |Si|1/2 · ajr |Sjr |1/2 where jr is the bidder selected in round r if we did not consider the agent i at all. Notice ajr |Sjr |1/2 does not increase when round r increases, so the final cut value is |Si|1/2 · aj |Sj |1/2 where bj is the first bid that has been denied but would have been selected were it not only for the presence of bidder i. Thus, the payment by agent i is |Si|1/2 · aj |Sj |1/2 if ai ≥ |Si|1/2 · aj |Sj |1/2 , and 0 otherwise. This payment scheme is exactly the same as the payment scheme in [12]. 6. CONCLUSIONS In this paper, we have studied how to design a truthful mechanism M = (O, P) for a given allocation rule O for a binary demand game. We first showed that the allocation rule O satisfying the MP is a necessary and sufficient condition for a truthful mechanism M to exist. We then formulate a general framework for designing payment P such that the mechanism M = (O, P) is truthful and computable in polynomial time. We further presented several general composition-based techniques to compute P efficiently for various allocation rules O. Several concrete examples were discussed to demonstrate our general framework for designing P and for composition-based techniques of computing P in polynomial time. In this paper, we have concentrated on how to compute P in polynomial time. Our algorithms do not necessarily have the optimal running time for computing P given O. It would be of interest to design algorithms to compute P in optimal time. We have made some progress in this research direction in [22] by providing an algorithm to compute the payments for unicast in a node weighted graph in optimal O(n log n + m) time. Another research direction is to design an approximation allocation rule O satisfying MP with a good approximation ratio for a given binary demand game. Many works [12, 13] in the mechanism design literature are in this direction. We point out here that the goal of this paper is not to design a better allocation rule for a problem, but to design an algorithm to compute the payments efficiently when O is given. It would be of significance to design allocation rules with good approximation ratios such that a given binary demand game has a computationally efficient payment scheme. In this paper, we have studied mechanism design for binary demand games. However, some problems cannot be directly formulated as binary demand games. The job scheduling problem in [2] is such an example. For this problem, a truthful payment scheme P exists for an allocation rule O if and only if the workload assigned by O is monotonic in a certain manner. It wound be of interest to generalize our framework for designing a truthful payment scheme for a binary demand game to non-binary demand games. Towards this research direction, Theorem 4 can be extended to a general allocation rule O, whose range is R+ . The remaining difficulty is then how to compute the payment P under mild assumptions about the valuations if a truthful mechanism M = (O, P) does exist. Acknowledgements We would like to thank Rakesh Vohra, Tuomas Sandholm, and anonymous reviewers for helpful comments and discussions. 7. REFERENCES [1] A. ARCHER, C. PAPADIMITRIOU, K. T., AND TARDOS, E. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In ACM-SIAM SODA (2003), pp. 205-214. [2] ARCHER, A., AND TARDOS, E. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd IEEE FOCS (2001), IEEE Computer Society, p. 482. [3] AULETTA, V., PRISCO, R. D., PENNA, P., AND PERSIANO, P. Deterministic truthful approximation schemes for scheduling related machines. [4] CHVATAL, V. A greedy heuristic for the set covering problem. Mathematics of Operations Research 4, 3 (1979), 233-235. [5] CLARKE, E. H. Multipart pricing of public goods. Public Choice (1971), 17-33. [6] R. Muller, and R. V. Vohra. On Dominant Strategy Mechanisms. Working paper, 2003. [7] DEVANUR, N. R., MIHAIL, M., AND VAZIRANI, V. V. Strategyproof cost-sharing mechanisms for set cover and facility location games. In ACM Electronic Commerce (EC03) (2003). [8] FEIGENBAUM, J., KRISHNAMURTHY, A., SAMI, R., AND SHENKER, S. Approximation and collusion in multicast cost sharing (abstract). In ACM Economic Conference (2001). [9] FEIGENBAUM, J., PAPADIMITRIOU, C., SAMI, R., AND SHENKER, S. A BGP-based mechanism for lowest-cost routing. In Proceedings of the 2002 ACM Symposium on Principles of Distributed Computing. (2002), pp. 173-182. [10] GREEN, J., AND LAFFONT, J. J. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica (1977), 427-438. [11] GROVES, T. Incentives in teams. Econometrica (1973), 617-631. [12] LEHMANN, D., OCALLAGHAN, L. I., AND SHOHAM, Y. Truth revelation in approximately efficient combinatorial auctions. Journal of ACM 49, 5 (2002), 577-602. [13] MU"ALEM, A., AND NISAN, N. Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract. In 18th National Conference on Artificial intelligence (2002), American Association for Artificial Intelligence, pp. 379-384. [14] NISAN, N., AND RONEN, A. Algorithmic mechanism design. In Proc. 31st Annual ACM STOC (1999), pp. 129-140. [15] E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 329-337, 2000. [16] R. Bar-Yehuda and S. Even. A local ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, Volume 25: Analysis and Design of Algorithms for Combinatorial Problems, pages 27-46, 1985. Editor: G. Ausiello and M. Lucertini [17] ROBINS, G., AND ZELIKOVSKY, A. Improved steiner tree approximation in graphs. In Proceedings of the 11th annual ACM-SIAM SODA (2000), pp. 770-779. [18] A. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9(5):463-470, 1993. [19] D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems, Discrete Applied Mathematics, 6:243-254, 1983. [20] TAKAHASHI, H., AND MATSUYAMA, A. An approximate solution for the steiner problem in graphs. Math. Japonica 24 (1980), 573-577. [21] VICKREY, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance (1961), 8-37. [22] WANG, W., AND LI, X.-Y. Truthful low-cost unicast in selfish wireless networks. In 4th IEEE Transactions on Mobile Computing (2005), to appear. [23] WANG, W., LI, X.-Y., AND SUN, Z. Design multicast protocols for non-cooperative networks. IEEE INFOCOM 2005, to appear. [24] WANG, W., LI, X.-Y., AND WANG, Y. Truthful multicast in selfish wireless networks. ACM MobiCom, 2005. 222
truthful mechanism binary demand game objective function combination mechanism design pricing monotonicity property cut value function price demand game
vickrey-clarke-grove composition-based technique selfish wireless network selfish agent