Sybil-proof Answer Querying Mechanism

1 Introduction

The development of online social networks has offered many opportunities for people to collaborate remotely in real time, such as P2P file-sharing network (e.g., BitTorrent) and Q&A platforms (e.g., Quora and Stack Overflow). Inspired by these applications, there are rich theoretical studies to look at the mechanism design problems on social networks [Rahman, 2009; Emek et al., 2011; Li et al., 2017].

In this paper, we focus on the answer/resource querying mechanisms via a social network where a requester is searching for a single answer from the network. Here we have two main challenges. The first is that the requester is only connected to a few agents (her neighbours) on the network and she needs to find a way to inform the other agents on the network if her neighbours do not have the answer. This can be achieved by incentivizing her neighbours to propagate the query to their neighbours (diffusion incentives). Kleinberg and Raghavan [2005] first formulated diffusion incentives in query networks. Later on, Arcaute et al. [2007] and Kota and Narahari [2010] studied the threshold of rewards needed to incentivize the query network. Kleinberg [2007] further discussed whether agents will act as the requester expects under different reward settings. Similar approach has been applied in advertising [Li and Shiu, 2012], auctions [Zhao et al., 2018], recommendations [Margaris et al., 2016] and others.

Once the first challenge is sovled, then an immediate new challenge is Sybil attacks, where an agent pretends to be multiple agents to gain more rewards [Conitzer et al., 2010]. Sybil attack has been studied in many other applications such as multi-level marketing [Emek et al., 2011; Drucker and Fleischer, 2012; Shen et al., 2019], social choice [Conitzer and Yokoo, 2010] and blockchains [Babaioff et al., 2012; Ersoy et al., 2018]. For query networks, Sybil attack has been investigated under various settings. For example, Seuken and Parkes [2014] studied the trade-off between the transitive trust and Sybil attacks in P2P file-sharing networks. Chen et al. [2013] proposed a mechanism based on the query incentive network [Kleinberg and Raghavan, 2005] which achieves Sybil-proofness in expectation. Nath et al. [2012] identified a collusion-proof mechanism with approximated Sybilproofness. However, all the existing work has only discussed Sybil-proofness in approximation or expectation on query networks.

Therefore, in this paper, we aim to solve both challenges in a dominant strategy implementation for query networks. We first demonstrate the difficulties to solve the challenges by proving the impossibility results. We then characterize a class of mechanisms, called double geometric mechanism (DGM), to satisfy the desirable properties. Except for the diffusion incentive and Sybil-proofness, we also look at the cost minimization problem for the requester and preventing agents' collusion. We will show that Sybil-proofness and collusionproofness are not compatible.

1.1 RelatedWork

The query incentive network model was first proposed by Kleinberg and Raghavan [2005], where each agent in a dary tree network has the same probability to hold the answer and the actual query network is generated by a branching process (the cost in the query process is negligible). They considered a decentralized reward mechanism where each agent strategically chooses a fixed amount of reward to offer to her children if she can receive the answer from them. Different from the fixed reward mechanism, Cebrian et al. [2012] proposed a split contract mechanism in the same setting, which was motivated by the success of the winning strategy in the DARPA 2009 Network Challenge [Pickard et al., 2011]. In their split contract mechanism, each agent should determine the splits of the reward received from her parent to offer to her children. In both studies, they only considered the Nash equilibrium implementation, while we consider dominant strategy implementation here.

Moreover, the studies mentioned above mainly focused on propagating the query in the network and they did not consider agents' Sybil attacks. However, when we consider centralized query mechanisms where the reward distribution is decided by the requester, Sybil attack is a problem if the requester cannot verify their indenties [Douceur, 2002]. In the previous work, Chen et al. [2013] proved that split contract mechanisms cannot prevent Sybil attacks. They proposed direct referral mechanism to deal with this problem by allocating the majority of the reward to the winner (the agent who holds the answer) as well as her parent, i.e., the direct referral. However, the Sybil-proofness of the direct referral mechanism is only in expectation, which means that Sybil attack might be beneficial for an agent if the agent can acquire more knowledge about the network.

Again for Syblil-proofness, in the setting of dominant strategy implementation, Nath et al. [2012] studied the split contract mechanism design. They identified a set of desirable properties including Sybil-proofness and collusion-proofness and proved that no mechanism can satisfy them simultaneously under some conditions. They also examined the wellknown geometric mechanism and showed that it satisfies collusion-proofness and approximated Sybil-proofness.

Different from the above, in this paper, we investigate centralized Sybil-proof reward mechanism design in the query network under dominant strategy implementation. We characterize a class of mechanisms to achieve Sybil-proofness and other properties in the query network.

The remainder of the paper is organized as follows. Section 2 describes the model of the query network and introduces the desirable properties of the reward mechanism. Then we prove the impossibility results in Section 3. Following that, we propose our double geometric mechanism and characterize its uniqueness under different properties in Section 4. Finally, we conclude and discuss the future work in Section 5.

2 The Model

We consider a question answering setting where a requester r is seeking the answer of a question from a set of agents. The agents are connected via their social connections such as friendship and r connects to a subset of them. r will first ask her neighbours for the answer and if her neighbours do not have the answer, r wants her neighbours to further propagate the question to their neighbours and so on. We assume that there is at least one agent who holds the answer and the answer is unique/verifiable. The goal of r is to design a reward mechanism to find the answer from the network. Ideally, we want each agent to offer the answer if she has, otherwise, to propagate the question to her neighbours if there is any. Formally, the propagation process will build a query tree T = (V,E) rooted at r, where V is the set of all agents, including the requester r, who have been asked for the answer, and each edge e = (i, j) ∈ E means that agent i has propagated the query to agent j and j has either offered the answer or propagated the question to her neighbours. For each agent i in T, let p(i) be i's direct parent and s(i) be i's direct children set.

We assume that there is one agent in T who offered the answer, which is called the winner, denoted by w. It is clear that w ̸= r and if there are multiple agents offered the answer, we choose the one with the smallest depth with random tie-breaking. We call the path from r to w a winning path, denoted by pw = (i1, i2, . . . , in), where i1 ∈ s(r), in = w, (ij, ij+1) ∈ E for all 1 ≤ j < n and n is the length of the winning path.

Given the above setting, the requester needs to design a reward mechanismM : T → RV \{r} to incentivize the agents to find the answer, where T is the space of all possible resulting query trees and the output is the reward allocation for each player in the tree. Denote the reward allocated to agent i by xi. In this paper, we focus on path mechanisms, which are mostly studied in the literature [Kleinberg and Raghavan, 2005; Chen et al., 2013].

Definition 1. A reward mechanism is called a path mechanism if

1. it only assigns non-zero rewards to the agents on the winning path, i.e., xi = 0 for all i /∈ pw,
2. the reward distributed to an agent on the winning path only depends on her depth and the length of the path.

That is, a path mechanism M can be represented by a reward function x : N × N → R for the agents on the winning path, where the first parameter is the agent's depth and the second parameter is the length of the winning path.

A path mechanism only rewards the agents on the winning path in the resulting query network. This will not weaken our results since the agents on the winning path made the actual contribution for seeking the answer. We assume that the cost for the query propagation is negligible as the propagation is often easy or automated [Yu and Singh, 2003]. Therefore, the literature has also focused on path mechanisms.

In the following, we define the desirable properties for path mechanisms. Firstly, it should incentivize agents to offer the answer or further propagate the query to all their neighbours; otherwise, the query will stop at the requester's neighbours. We call this property incentive compatibility.

Definition 2. A path mechanism is incentive compatible (IC) if for all agent i, xi ≥ x′i , where

• xi is the reward i receives if i truthfully reports her answer, if i has the answer, or propagates the query to all her neighbours if i does not have the answer,
• x′i is the reward i receives if i behaves differently.

An incentive compatible mechanism guarantees that it will always find the answer if there is one in the network. Secondly, we also require that every agent is not forced to participate in the mechanism, i.e., their reward should not be negative, which is called individual rationality.

Definition 3. A path mechanism is individually rational (IR) if for all agent i ∈ pw, xi ≥ 0, i.e., x(j, n) ≥ 0 for all j, n ∈ Z+, j ≤ n. It is strongly individually rational (SIR) if for all agent i ∈ pw, xi > 0, i.e., x(j, n) > 0 for all j, n ∈ Z+, j ≤ n.

Notice that IR property can be easily satisfied even if the mechanism does not give any reward to any agent. Therefore, we also look for strongly IR path mechanisms, which at least reward something for every agent in the winning path. At the same time, the requester may also want to control the total reward distributed.

Definition 4. A path mechanism is budget constrained (BC) if there exists a constant B < ∞ such that

for all resulting query network T , for all winning path pw of length n in T .

Next, we consider the most important property of Sybilproofness, which requires that the mechanism should be resistant to Sybil-attacks. Since the resulting query network is a tree and we focus on path mechanisms, fake identities which are not on the winning path benefit nothing. So there is only one kind of meaningful Sybil-attacks for agent i, i.e., pretending to be multiple agents from agent p(i) to agents in s(i) (extending the paths from p(i) to s(i)).

Definition 5. A path mechanism is Sybil-proof (SP) if for any winning path pw = (i1, i2, . . . , in), if an agent ij ∈ pw extends pw by making m copies of herself to get the new winning path p′w = (i1, . . . , ij-1, i0j , i1j , . . . , imj , ij+1, . . . , in), we have:

Intuitively, if an agent pretends to be multiple agents along the winning path, the property of Sybil-proofness ensures that the total rewards she can get from the multiple agents is not more than what she will get originally. In our setting, Sybilproofness can be easily verified as stated in Proposition 1.

Proposition 1. A path mechanism is Sybil-proof if and only if

for all j, n ∈ Z+, j ≤ n.

Proof. ("⇒") If a path mechanism is Sybil-proof, then in Inequality (1), let m = 1, it can be easily derived that x(j, n) ≥ x(j, n + 1) + x(j + 1, n + 1) for all j, n ∈ Z+, j ≤ n.

("⇐") If a path mechanism satisfies x(j, n) ≥ x(j, n + 1) + x(j + 1, n + 1) for all j, n ∈ Z+, j ≤ n, then

for all j, n,m ∈ Z+, j ≤ n. Hence, the mechanism is Sybilproof.

Sybil-proofness says that an agent cannot gain by making multiple copies of herself, while another property says multiple agents could also not collude together to receive a better reward, which is called collusion-proofness [Chen et al., 2018]. We will show that these two properties cannot be satisfied together in general.

Definition 6. A path mechanism is λ-collusion proof (λ-CP) (λ ∈ Z+ and λ > 1) if

for all 1 ≤ λ′ ≤ λ, all j, n ∈ Z+ such that j ≤ n-λ′ +1. If λ-collusion proof holds for all λ > 1, i.e.,

for all j, n,m ∈ Z+ such that j ≤ n, then, we call this mechanism collusion-proof (CP).

Intuitively, λ-collusion proofness indicates that any group of agents with size less than λ cannot get more reward if they pretend to be a single agent. Collusion proofness requires this to be held for all group sizes. In real-world applications, agents' ability to form a collusion is always limited as, for example, it is not easy to collude for agents far from each other in the network. Thus, λ-collusion proofness is an applicable approximation of collusion proofness in practice.

Lastly, to guarantee the reward distributed to agents on the winning path is sufficient, we require that each agent on the winning path can get at least a certain fraction of the winner's reward. This property is inspired by the efficiency of split contracts [Cebrian et al., 2012].

Definition 7. A path mechanism is ρ-split secure (ρ-SS), 0 < ρ < 1, if for all agent ij ∈ pw \ {w}, xij ≥ ρxij+1 , i.e., x(j, n) ≥ ρx(j + 1, n) for all j, n ∈ Z+, j < n.

Intuitively, the property of ρ-split security ensures that each agent on the winning path other than the winner has at least ρ fraction of the reward distributed to her children on the winning path. This guarantee will encourage agents to propagate the query in reality.

3 Impossibility Results

Before characterizing the reward mechanisms that satisfy the desirable properties, we prove several impossibility results in this section.

The first impossibility is that if strongly IR is required (i.e., each agent on the winning path is rewarded more than zero), Sybil-proofness and collusion-proofness cannot be held together.

Lemma 1. An SIR path mechanism cannot be both Sybilproof and λ-collusion-proof for all λ ≥ 3.

Proof. If such a mechanism exists, then according to the inequality in Proposition 1, let m = λ - 1 and we have

for any j, n ∈ Z+, j ≤ n-λ+1. Together with Inequality (2), we know that

Hence, the middle part of Inequality (3) is equal to both the left hand side and the right hand side.

Then, since λ ≥ 3 and (λ-1 0 ) = (λ-1 λ-1) = 1,

from which we can derive that x(j + k, n + λ - 1) = 0 for all 1 ≤ k ≤ λ - 2 since (λ-1 k ) > 1 for all 1 ≤ k ≤ λ - 2. This is a contradiction with SIR.

Following Lemma 1, we can conclude that under the requirement of SIR, being both Sybil-proof and collusion-proof is impossible for a path mechanism.

Proposition 2. An SIR path mechanism cannot be both Sybilproof and collusion-proof.

However, we will show that the property of 2-collusionproof, which says that two agents cannot collude to make a gain, can be satisfied with Sybil-proofness in Section 4.

The impossibility assumes strongly IR. However, even if we weaken the condition to be IR, Theorem 1 shows that the only mechanisms to satisfy both SP and CP are limited to very special mechanisms called two-headed mechanism.

Mechanism 1. A path mechanism is a two-headed mechanism if its reward function satisfies

where a, b ≥ 0 are constants.

Intuitively, a two-headed mechanism only allocates positive rewards to the first agent and the winner on the winning path and all the other agents receive a zero reward.

Theorem 1. A path mechanism is IR, SP and CP if and only if it is a two-headed mechanism.

Proof. ("⇐") First, it is easy to show that a two-headed mechanism is IR, SP and CP since x(j, n) ≥ 0 and

for all j, n ∈ Z+ and j ≤ n.

("⇒") Then we show that these three properties determine a two-headed mechanism. From the definition of CP, we know that the mechanism is λ-CP for all λ > 1. Then from Lemma 1 we know that a mechanism with SP and λ-CP satisfies x(j, n) = 0 for all 1 < j < n and n > 1. Hence, from SP and 2-CP we can derive that

for all n > 1.

Hence, there exist two constants a ≥ 0 and b ≥ 0 such that x(1, n) = a, x(n, n) = b for all n > 1 and x(1, 1) = x(1, 2) + x(2, 2) = a + b.

4 Double Geometric Mechanism

In this section, we characterize a class of reward mechanisms with the desirable properties. The mechanism we will characterize is called Double Geometric Mechanism (DGM), which is a path mechanism defined by two parameters.

Mechanism 2. A path mechanism is an (α, δ) double geometric mechanism ((α, δ)-DGM), for 0 < α < 1 and δ > 0, if its reward function satisfies

for all j, n ∈ Z+ such that j ≤ n.

Intuitively, (α, δ)-DGM has two fractions αn-j and (1 - α)j-1 , which are controlled by the distance to the winner and the requester respectively. Note that if α < 1/2, the reward is strictly monotone decreasing with the depth on the winning path, while if α > 1/2, the reward is strictly monotone increasing with the depth on the winning path. Theorem 2 shows that (α, δ)-DGM can satisfy all the desirable properties defined in our model.

Theorem 2. If a path mechanism is an (α, δ)-DGM with ρ 1+ρ ≤ α < 12 (0 < ρ < 1), then it is IC, SIR, BC, SP, 2-CP and ρ-SS.

Proof. Suppose the winning path is (i1, i2, . . . , in) of length n when the agents behave truthfully. For an agent ij with 1 ≤ j < n, xij = x(j, n), if she did not query all her neighbours, then she will be either on the winning path of length ≥ n or not on the winning path. By doing so, her reward is either x(j, n + k) = (1 - α)j-1αn-j+k δ ≤ (1 - α)j-1αn-j δ = x(j, n) for some k ≥ 0, or zero, which is not better than behaving truthfully. For the winner in = w, if she did not provide the answer and further queried her children, then she would be either on the winning path of length > n or not on the winning path, which gives her a reward either x(n, n +

k) = (1 - α)n-1αk δ < (1 - α)n-1 δ = x(n, n) for some k ≥ 1 or zero. Hence, (α, δ)-DGM is IC.

For all j, n ∈ Z+, j ≤ n, we have x(j, n) = (1 - α)j-1αn-j δ > 0. Hence, (α, δ)-DGM is SIR. For all j, n ∈ Z+, j ≤ n and 0 < α < 12 , we have

Hence, (α, δ)-DGM is BC.

For all j, n ∈ Z+, j < n, we have

Hence, (α, δ)-DGM is 2-CP. According to Proposition 1, it is also SP.

Finally, for all j, n ∈ Z+, j < n, we have

Hence, (α, δ)-DGM is ρ-SS.

(α, δ)-DGM satisfies all the desirable properties. Then we wonder are they the only mechanisms to satisfy these properties. Under some mild conditions, we will prove that (α, δ)- DGM is indeed the only mechanism to satisfy all the properties.

Note that if there are only two agents on the winning path, it is a very special case that has almost no constraints (the reward can be assigned arbitrarily), which suggests that it acts like an initial condition to the reward function. To satisfy the property of ρ-SS, we should have x(1, 2) ≥ ρx(2, 2) and we let x(1, 2) = ρx(2, 2), which is the simplest way to construct the initial condition. We say a mechanism uses ρ-base condition if its reward function x satisfies x(1, 2) = ρx(2, 2). Theorem 3 proves that under the base condition, (α, δ)-DGM is the only kind of mechanism to satisfy all the properties.

Theorem3. If a path mechanism is IC, SIR, BC, SP, 2-CP, ρSS and uses ρ-base condition, then it is an (α, δ)-DGM with α = ρ 1+ρ .

Proof. First consider the value x(j, n), x(j + 1, n), x(j, n + 1), x(j+1, n+1) and x(j+2, n+1) for some j, n ∈ Z+ and j < n. Suppose that x(j, n) = γx(j + 1, n), x(j, n + 1) = γ2x(j + 1, n + 1) and x(j + 1, n + 1) = γ1x(j + 2, n + 1).

Then according to the property of SP and 2-CP, we know that x(j, n) = x(j, n+1)+x(j +1, n+1) and x(j +1, n) = x(j + 1, n + 1) + x(j + 2, n + 1), from which we have

Hence, by x(j, n) = γx(j + 1, n), we have

where according to the property of ρ-SS, we have γ ≥ ρ,

γ1 ≥ ρ and γ2 ≥ ρ.

which suggests that γ1 ≤ ρ. Hence γ1 = ρ and then γ2 = ρ. Note that we have x(1, 2) = ρx(2, 2) as the base condition, so from above we have x(1, 3) = ρx(2, 3) and x(2, 3) = ρx(3, 3). Then, by induction, x(j, n) = ρx(j+1, n) holds for any j, n ∈ Z+ and j < n. Therefore, the following recursive relation holds for any j, n ∈ Z+ and j ≤ n:

Denote δ = x(1, 1) > 0, then we can derive that

with α = ρ/(1+ρ) for any j, n ∈ Z+ and j ≤ n, which is an (α, δ)-DGM. Also according to Theorem 2, the property of IC, SIR and BC will not be hurt. Therefore, these properties will uniquely determine the (α, δ)-DGM.

So far, we have shown that (α, δ)-DGM is the only kind of mechanism to satisfy the properties under the ρ-base condition. Note that, without the ρ-base condition, we may get a different mechanism to satisfy all the properties, but it is still a DGM-like mechanism with a bounded difference. It suggests that the space of mechanisms removed by this base condition is also limited. Therefore, the base condition does not significantly hurt the generality of our result.

As Proposition 2 shows that SP and CP cannot be held together under SIR, the above mechanism can only satisfy 2CP. In the following, we show how much extra gain a group of agents could get if they collude together and a weaker concept of CP. Furthermore, we will investigate the cost of the requester and show how to minimize it.

4.1 Approximation of Collusion-proofness

Definition 8. A path mechanism is called β-approximate collusion-proof (β-ACP) if its reward function x satisfies

for all j, n, m ∈ Z+, j ≤ n.

Intuitively, the property of β-approximate collusion-proof ensures that if some agents pretend to be a single agent, they can achieve at most β times of their original reward. However, we show that a constant approximation cannot be achieved along with the other properties.

Proposition 3. An IC, SIR, BC, SP, 2-CP and ρ-SS path mechanism with ρ-base condition cannot be (1 + ϵ)-ACP for any ϵ > 0.

Proof. Note that an IC, SIR, BC, SP, 2-CP and ρ-SS path mechanism with ρ-base condition must be an (α, δ)-DGM with α = ρ/(1 + ρ). Then (1 + ϵ)-ACP implies that

from which we can derive that

However, for any given ϵ > 0 and 0 < α < 1/2, there exists N > 0 such that for any m > N, (1-α)m+1-αm+1 < (1-2α)/(1+ϵ) since the left hand side approaches to 0 when m approaches to ∞. Hence, it cannot be (1 + ϵ)-ACP.

On the other hand, an exponential approximation is easy to be achieved by an (α, δ)-DGM.

Theorem4. If a path mechanism is an (α, δ)-DGMwith 0 < α < 12 , then it is 2m-ACP, where m is the number of agents who collude together.

Proof. If an (α, δ)-DGM is 2m-ACP, it suggests that

from which we can derive the equivalent inequality that

or being rearranged as

Notice that for function f(y) = y (ym - 1 2m ), f(y) < 0 for any 0 < y < 1/2 and f(y) > 0 for any 1/2 < y < 1. Since 0 < α < 1/2, the above inequality always holds.

4.2 Cost Minimization

Next, we consider the case where the requester is willing to minimize her cost to query the answer.

Definition 9. A path mechanism is of minimum cost over a class of path mechanisms X if its reward function x satisfies

for all n ∈ Z+.

Intuitively, a path mechanism is of minimum cost if it can minimize the total reward distributed to the agents on the winning path. Notice that when we minimize the cost, we consider time-critical mechanisms, which are essential to the real-world application [Pickard et al., 2011]. A path mechanism is time-critical if the winner always takes the maximum reward, i.e., x(n, n) = maxj x(j, n) for any n ≥ 1. Now we show that the (α, δ)-DGM also characterizes the space of time-critical mechanisms of minimum cost.

Theorem 5. A path mechanism is of minimum cost over a class of time-critical path mechanisms that satisfy IC, SIR, BC, SP, 2-CP, ρ-SS and have x(1, 1) = δ if and only if it is an (α, δ)-DGM with α = 1/2.

Proof. First we show a lower bound of the total cost before we prove the statement. According to the property of SP and 2-CP, denote ∑nj=1 x(j, n) = Rn, then we have

with R1 = R2 = δ. Hence, to minimize the total cost is to minimize the term x(1, n + 1) + x(n + 1, n + 1). Suppose that x(1, 2) = γx(2, 2), x(1, 3) = γ2x(2, 3) and x(2, 3) = γ1x(3, 3) where ρ ≤ γ, γ1, γ2 ≤ 1 with γ = ρ + ϵ. Then similar to the process in Theorem 3, we can derive that γ2 = γ(1 + 1/γ1) - 1 and γ1 ≤ (ρ + ϵ)/(1 - ϵ). Hence,

As we want to minimize the cost, the minimum value will be reached if γ = γ1 = γ2 = 1, which means x(1, 2) = x(2, 2) and x(1, 3) = x(2, 3) = x(3, 3). By induction, if for some n, x(j, n) = x(j + 1, n) for any j < n, suppose x(j, n + 1) = γjx(j + 1, n + 1) for any j ≤ n, then we have 1 + γn = γn(1 + γn-1) = · · · = γn · · · γ2(1 + γ1) with ρ ≤ γj ≤ 1. So that the solution could only be γ1 = · · · = γn = 1. Therefore, x(j, n) = x(j + 1, n) for any j, n ∈ Z+ and j < n.

("⇐") First, an (α, δ)-DGM is IC, SIR, BC, SP, 2-CP, ρSS and have x(1, 1) = δ by Theorem 2. Then, for an (α, δ)- DGM with α = 1/2, the total reward distributed is

for any n ≥ 1. Besides, from the above we know 2Rn ≥ Rn-1 + δ/2n-2 for n ≥ 3 and R2 = δ. Then Rn ≥ (nδ)/2n-1 . Since (α, δ)-DGM with α = 1/2 meets this lower bound, then it is the mechanism of minimum cost.

("⇒") By the equation of x(j, n) = x(j + 1, n) and x(1, 1) = δ, we can derive that x(j, n) = δ/2n-1 , which is the same as for the (1/2, δ)-DGM. Therefore, the mechanism of minimum cost over these properties uniquely determines the (1/2, δ)-DGM.

5 Conclusion

We have investigated Sybil-proof answer querying mechanisms on networks in a dominant strategy implementation. We proposed a class of double geometric mechanisms (DGM) to against Sybil attacks and characterized its uniqueness under other important properties such as IC, IR and 2-CP. We also characterized the mechanisms for minimizing the requester's reward expenses and illustrated the performance of the mechanisms in terms of the approximation of collusionproofness. There are several other interesting aspects worth further investigation. There is a gap between constant approximation and exponential approximation of collusionproofness. The characterization of Sybil-proof mechanisms in a general directed graph is also missing.