Fair and resilient Incentive Tree mechanisms

Abstract

We study Incentive Trees for motivating the participation of people in crowdsourcing or human tasking systems. In an Incentive Tree, each participant is rewarded for contributing to the system, as well as for soliciting new participants into the system, who then themselves contribute to it and/or themselves solicit new participants. An Incentive Tree mechanism is an algorithm that determines how much reward each individual participant receives based on all the participants’ contributions, as well as the structure of the solicitation tree. The sum of rewards paid by the mechanism to all participants is linear in the sum of their total contribution. In this paper, we investigate the possibilities and limitations of Incentive Trees via an axiomatic approach by defining a set of desirable properties that an Incentive Tree mechanism should satisfy. We give a mutual incompatibility result showing that there is no Incentive Tree mechanism that simultaneously achieves all the properties. We then present two novel families of Incentive Tree mechanisms. The first family of mechanisms achieves all desirable properties, except that it fails to protect against a certain strong form of multi-identity attack; the second set of mechanisms achieves all properties, including the strong multi-identity protection, but fails to give participants the opportunity to achieve unbounded reward. Given the above impossibility result, these two mechanisms are effectively the best we can hope for. Finally, our model and results generalize recent studies on multi-level marketing mechanisms.

Appendix: Proof of Theorem 4

Proof

It will be convenient to use the following definition. Let $S_A, S_B$ be two subsets of $T'$. We define

$$\begin{aligned} B(S_A,S_B)=\sum _{u\in S_A}\sum _{v\in S_B}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}. \end{aligned}$$

Intuitively, $B(S_A,S_B)$ is the sum of the rewards accumulated by nodes in $S_A$ through nodes in $S_B$. Using this definition, we can reformulate the reward function R(u) for $u\in T$ as

$$\begin{aligned} R(u)= & {} \sum _{v\in CH_u}\frac{\lambda }{\mu }C(v)\sum _{x\in T'_{v}}{a^{dep_{v}(x)} b\cdot C(x)+\phi C(u)} \\= & {} B\left( CH_u,T'_{m_1^u}\right) +\phi C(u). \end{aligned}$$

There are two properties for function $B(S_A,S_B)$. Suppose $S,S',S^*$ are subsets of $T'$, and $S,S'$ are disjoint. We have

$$\begin{aligned} B(S\cup S',S^*)&=\sum _{u\in S\cup S'}\sum _{v\in S^*}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\&=\sum _{u\in S}\sum _{v\in S^*}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\&\quad +\sum _{u\in S'}\sum _{v\in S^*}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\&=B(S,S^*)+B(S',S^*) \end{aligned}$$

and

$$\begin{aligned} B(S^*,S\cup S')= & {} \sum _{u\in S^*}\sum _{v\in S\cup S'}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\= & {} \sum _{u\in S^*}\sum _{v\in S}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\&+\sum _{u\in S^*}\sum _{v\in S'}\frac{\lambda }{\mu }b\cdot C(u)C(v)a^{dep_u(v)}\\= & {} B(S^*,S)+B(S^*,S'). \end{aligned}$$

Budget Constraint: We start by proving that the mechanism meets the budget constraint. First, observe that the total rewards in the referral tree is equivalent to the total rewards in the reward computation tree. Then, in the reward computation tree $T'$, it holds that

$$\begin{aligned} \sum _{u\in T'}{R(u)}= & {} \sum _{u\in T'}\left[ C(u)\cdot \frac{\lambda }{\mu } \sum _{v\in T'}a^{dep_u(v)}\cdot b C(v)+\phi C(u)\right] \\&\le \sum _{u\in T'}\left[ \lambda \sum _{v\in T'}a^{dep_u(v)}\cdot b C(v)\right] +\sum _{u\in T'}\phi C(u)\\&<\sum _{v\in T'}\left[ \lambda \cdot C(v)\sum _{i=0}^{\infty }a^ib\right] +\sum _{u\in T'}\phi C(u)\\&<(\lambda +\phi )\sum _{u\in T'}C(u). \end{aligned}$$

By the constraint imposed on $\lambda$, this last expression is at most $\varPhi \sum _{u\in T'}C(u)$, which is the budget.

We now prove the desirable properties one by one.

CCI: Consider a participant u, who increases his contribution from C(u) to $C^*(u)=C(u)+\epsilon$. We denote by $R^*(u)$ and $CH^*_u=\{m^{*u}_1,\ldots ,m^{*u}_{N^*_u}\}$ the new reward and the new corresponding chain, respectively. There are two cases depending on whether u’s contribution increase leads to a change of its corresponding chain $CH^*_u$ in the RCT, or not. We consider the two cases independently.

First, if $N^*_u=N_u$, then only the head-node $m^u_1$’s contribution increases in $T'$: $C(m^{*u}_1)=C(m^u_1)+\epsilon$. Then, the new reward of participant u is $R^*(u)> R(u)$.

Second, if $N^*_u>N_u$, then we only need to consider the sub-chain in $CH^*_u$ with $N_u$ nodes from the leaf node up. As each node of the sub-chain has contribution $\mu$, we get that $R^*(u)>R(u)$.

$\phi$-RPC: By the definition of the R(u), it holds that $R(u)=B(CH_u,T_{m^u_1})+\phi C(u)>\phi C(u)$.

CSI: The property holds because by the definition of R(u), the reward of a participant u is strictly increasing when a new node v attaches to u.

SL: The property holds because by the definition of R(u), the reward of a participant u is independent of any node outside of $T_u$.

URO: Consider a participant u, whose contribution is $C(u)=s\mu +\epsilon$, for some integer s and $0<\epsilon \le \mu$, and suppose u has k children in the referral tree, namely there are k trees attached to u. Here s can be any non-negative integer and k can be any positive integer. We denote one of u’s children as v and the corresponding subtree as $T_v$. Suppose v has $\ell$ children with contribution $\mu$. It holds that R(u) is at least $R'(m^u_{N_u})$ in the reward computation tree. Calculating the value of $R'(m^u_{N_u})$ using the definition, it can be shown that $R'(m^u_{N_u})\ge \ell \cdot a^2 b \lambda \epsilon$. As $\ell$ can become arbitrarily large, R(u) can increase to infinity.

USA: At the heart of our proof is that TDRM satisfies USA. To do so, we define an $\epsilon \hbox {-}chain$ as a chain in the reward computation tree of which only the head node can have contribution less than $\mu$.

USA states that no participant can increase his reward by pretending to have multiple identities. Consider a participant u that joins the referral tree as j Sybil nodes ($j\ge 1$), $v_1,v_2,\ldots ,v_j$, with total contribution C(u). Further assume that u has s children, $q_1,\ldots ,q_s$. Suppose $v_1,v_2,\ldots ,v_j$ are transformed into k nodes $u_1,\ldots ,u_k$ in the reward computation tree. By definition, it holds that $C(u)=\sum ^k_{i=1}C(u_i)$ and $C(u_i)\le \mu , i=1,\ldots ,k$. For $q_1,\ldots ,q_s$, we denote the subtrees rooted at $q_1,\ldots ,q_s$ in the reward computation tree as $T_1,\ldots ,T_s$. We define a partition as any configuration of nodes $u_1,\ldots ,u_k$, subtrees $T_1,\ldots ,T_s$, and contributions $C(u_i)$, $(i=1,\ldots ,k)$ in the reward computation tree that can feasibly result from node u joining the referral tree as a set of multiple Sybil nodes.

Our proof idea is as follows: Consider the set of optimal partitions for u in the reward computation tree (partitions maximizing R(u)). We show that at least one optimal partition has the structure of a single $\epsilon \hbox {-}chain$ in the RCT. In other words, we show that u’s best possible Sybil attack is to join in such a way that the resulting structure in the RCT is an $\epsilon \hbox {-}chain$. However, since the TDRM mechanism transforms u into an $\epsilon \hbox {-}chain$ in the RCT even if u joins as a single node, it follows that u has no benefit of joining the referral tree as multiple Sybil identities. The mechanism itself will give u the best possible split, thus giving u no incentive to split itself (Fig. 4).

We formally prove this intuition by a sequel of structural lemmas. The lemmas describe the properties of a reward-maximizing partition $u_1,\ldots ,u_k,T_1,\ldots ,T_s$ in the RCT, ultimately showing that the optimal such partition is an $\epsilon \hbox {-}chain$. As a first step, notice that because we have proven SL in TDRM, we consider only $u_1,\ldots ,u_k,T_1,\ldots ,T_s$ in the RCT. All other nodes are irrelevant for u’s reward. The first lemma shows that $u_1,\ldots ,u_k,T_1,\ldots ,T_s$ forms a tree. Here notice that according to the soliciting sequence, $u_i$ can not be a child of $T_j$ ($i=1,2,\ldots ,k$, $j=1,2,\ldots ,s$).

Lemma 1

If R(u) is maximized, $u_1,\ldots ,u_k,T_1,\ldots ,T_s$ forms a tree.

Proof

We prove the lemma by contradiction. Suppose R(u) is maximized and $u_1,\ldots ,u_k,T_1,\ldots ,T_s$ forms a forest F with more than one tree. We pick any two trees $T_\alpha$, $T_\beta$ in F with roots $\alpha$ and $\beta$. As u is the parent of $q_1,\ldots ,q_s$, it holds that $T_1,\ldots ,T_s$ will be attached as subtrees to $u_1,\ldots ,u_k$. Thus, $\alpha ,\beta \in \{u_1,\ldots ,u_k\}$. Now, assume that we attach $T_\beta$ to $\alpha$, thereby making it one tree. The attachment does not change the reward accumulated by nodes in $T_\beta$, but it strictly increases the rewards accumulated by $\alpha$ (due to the CSI property). This contradicts the assumption that R(u) is maximized. $\square$

Fig. 4

Illustration of the final topology in the proof

Thus if R(u) is maximized, $u_1,\ldots ,u_k$, $T_1,\ldots ,T_s$ forms a tree. We denote this tree as $T_u$, and define $\overline{T_u}$ as the tree induced by $u_1,\ldots ,u_k$, and $\underline{T_u}$ as the forest induced by $T_1,\ldots ,T_s$. With these definitions, we can write R(u) as

$$\begin{aligned} R(u)= & {} B(\overline{T_u},T_u) + \phi C(u) \\= & {} B(\overline{T_u},\overline{T_u})+B(\overline{T_u},\underline{T_u})+\phi C(u). \end{aligned}$$

Before continuing the proof, we distinguish different parts of R(u): The inner reward $R^i(u)= B(\overline{T_u},\overline{T_u})$ which is the part of reward purely coming from u’s own contribution, and the external reward $R^e(u)= B(\overline{T_u},\underline{T_u})$ which is the part of reward coming from u’s descendants. Then we can rewrite R(u) as $R(u)= R^i(u)+R^e(u)+\phi C(u).$ According to our assumption that u has a fixed contribution, the third term $\phi C(u)$ is a constant and does not influence u’s decision.

As mentioned before, we need to prove that the best partition of u, maximizing the reward, is an $\epsilon \hbox {-}chain$. Concretely, as $R(u)= R^i(u)+R^e(u)+\phi C(u)$, we show that u can maximize $R^i(u)$ and $R^e(u)$, respectively, if $\overline{T_u}$ is an $\epsilon \hbox {-}chain$. Our next step is to prove u’s partition as an $\epsilon \hbox {-}chain$ will maximize $R^i(u)$. We transform the topology of $\overline{T_u}$ step by step. The lemma below shows that if u wants to maximize his inner reward $R^i(u)$ at most one node in $\overline{T_u}$ can have contribution less than $\mu$.

Lemma 2

If $R^i(u)$ is maximized, there can be at most one node $v\in \overline{T_u}$ with contribution $C(v)<\mu$.

Proof

We prove the lemma by contradiction. Suppose there is more than one node with contribution less than $\mu$. We denote two such nodes as x, y, i.e., $x,y\in \overline{T_u}$ satisfying $C(x)<\mu$ and $C(y)<\mu$. Let $S_u=\overline{T_u}{\setminus }\{x,y\}$, and let $P_x,P_y$ be the set of ancestors of x, y in the reward computation tree. The inner reward of u is

$$\begin{aligned} R^i(u)= & {} B(\overline{T_u},\overline{T_u})\\= & {} B(\{x,y\},S_u)+B(S_u,S_u)\\&+\,B(\{x,y\},\{x,y\})+B(S_u,\{x,y\}). \end{aligned}$$

To simplify the calculation, we define a function $\gamma _p(S)=\sum _{v\in S}\frac{b\lambda }{\mu }C(v)\max \{a^{dep_p(v)},a^{dep_v(p)}\}$ for any node p in $\overline{T_u}$.According to the definition and properties we proposed for function B(), it holds that

$$\begin{aligned} B(\{x,y\},S_u)= & {} B(x,S_u)+B(y,S_u)\\= & {} C(x)\sum _{v\in S_u}\frac{\lambda }{\mu }b\cdot C(v)a^{dep_x(v)}\\&+\,C(y)\sum _{v\in S_u}\frac{\lambda }{\mu }b\cdot C(v)a^{dep_y(v)}\\= & {} C(x)\sum _{v\in T_x{\setminus }\{x,y\}}\frac{\lambda }{\mu }b\cdot C(v)a^{dep_x(v)}\\&+\,C(y)\sum _{v\in T_y{\setminus }\{x,y\}}\frac{\lambda }{\mu }b\cdot C(v)a^{dep_y(v)}\\= & {} C(x)\gamma _x(T_x{\setminus }\{x,y\})+C(y)\gamma _y(T_y{\setminus }\{x,y\}). \end{aligned}$$

$$\begin{aligned} B(S_u,\{x,y\})= & {} B(S_u,x)+B(S_u,y)\\= & {} C(x)\sum _{u\in S_u}\frac{\lambda }{\mu }b\cdot C(u)a^{dep_u(x)}\\&+\,C(y)\sum _{u\in S_u}\frac{\lambda }{\mu }b\cdot C(u)a^{dep_u(y)}\\= & {} C(x)\sum _{u\in P_x{\setminus }\{x,y\}}\frac{\lambda }{\mu }b\cdot C(u)a^{dep_u(x)}\\&+\,C(y)\sum _{u\in P_y{\setminus }\{x,y\}}\frac{\lambda }{\mu }b\cdot C(u)a^{dep_u(y)}\\= & {} C(x)\gamma _x(P_x{\setminus }\{x,y\})+C(y)\gamma _y(P_y{\setminus }\{x,y\}).\\ B(\{x,y\},\{x,y\})= & {} \frac{b\lambda }{\mu }\left[ \left( a^{dep_x(y)}+a^{dep_y(x)}\right) C(x)C(y)\right. \\&\left. +\,C(x)^2+C(y)^2\right] . \end{aligned}$$

Expanding $R^i(u)$ and combining the above bounds, we get

$$\begin{aligned} R^i(u)= & {} C(x)\gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})\nonumber \\&+\,C(y)\gamma _{y}((P_{y}\cup T_{y}){\setminus }\{x,y)\})\nonumber \\&+\,\frac{b\lambda }{\mu }\left[ \left( a^{dep_x(y)}+a^{dep_y(x)}\right) C(x)C(y)\right. \nonumber \\&\left. +\,C(x)^2+C(y)^2\right. ]+B(S_u,S_u). \end{aligned}$$

(1)

Without loss of generality, suppose $\gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})\ge \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})$. Then, consider two cases:

• (a) If $C(x)+C(y)>\mu$, we can change C(x) to $\mu$ and C(y) to $C(x)+C(y)-\mu$.

• (b) If $C(x)+C(y)\le \mu$, we can change C(x) to $C(x)+C(y)$ and C(y) to 0.

In both cases, the change does not have an impact on the total contribution, but it increases $R^i(u)$. Specifically, the sum of the first two expressions in (1) will increase due to the change. Then, using the fact that if for two reals A and B with $A>B,0<t<\frac{A-B}{2},k<2$ and $S_1=A^2+B^2+kAB$ and $S_2=(A-t)^2+(B+t)^2+k(A-t)(B+t)$, it holds that $S_1>S_2$, it follows that the third expression in (1) also increases. Meanwhile, the forth expression is unchanged. This leads to a contradiction because it means that this hypothetic partition does not maximize the inner reward. Therefore, if $R^i(u)$ is maximized, there can be at most one node $v\in \overline{T_u}$ with contribution $C(v)<\mu$. $\square$

Next, we characterize the location of the at most one node in $\overline{T_u}$ that has contribution less than $\mu$. In the following lemma, we give the result.

Lemma 3

If $R^i(u)$ is maximized, $\overline{T_u}$ is an $\epsilon \hbox {-}chain$ or a chain in which only the leaf node has contribution less than $\mu$.

Proof

According to Lemma 2, if $R^i(u)$ is maximized, there is at most one node with contribution less than $\mu$ in $\overline{T_u}$. We call it $\epsilon \hbox {-}node$ and suppose its contribution is $\epsilon (<\mu )$. (Here we need to pay attention that the $\epsilon \hbox {-}node$ has contribution strictly less than $\mu$.) We can prove the lemma by case analysis and contradiction.

(a):

Suppose $\overline{T_u}$ is not a chain. We distinguish three subcases.

(a1):

Suppose in $\overline{T_u}$, there is an $\epsilon \hbox {-}node$ and the $\epsilon \hbox {-}node$ is not a leaf node.

We denote the $\epsilon \hbox {-}node$ as x with contribution $C(x)=\epsilon$, and denote one of the leaf nodes which is a descendent of x as y with $C(y)=\mu$. Let $S_u=\overline{T_u}{\setminus }\{x,y\}$, and let $P_x,P_y$ be the set of ancestors of x, y in the reward computation tree. Just copy the expansion of $R^i(u)$ calculated in Lemma 2, we get that

$$\begin{aligned} R^i(u)= & {} \frac{b\lambda }{\mu }\left[ \left( a^{dep_x(y)}+a^{dep_y(x)}\right) C(x)C(y)+C(x)^2\right. \\&\left. +\,C(y)^2\right] +C(x)\cdot \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})\\&+\,C(y)\cdot \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})+B(S_u,S_u) . \end{aligned}$$

Since x is the ancestor of y, we know that nodes in $P_x$ are ancestors of both x and y and it holds that

$$\begin{aligned} \gamma _{x}(P_{x})= & {} \sum _{v\in P_x}\frac{b\lambda }{\mu }C(v)a^{dep_v(x)}\\&>\sum _{v\in P_x}\frac{b\lambda }{\mu }C(v)a^{dep_v(y)}=\gamma _{y}(P_{x}). \end{aligned}$$

Suppose there are n nodes in the path from y to x (not including x and y), denoted as $S_{xy}$. Remember we have stated there is at most one $\epsilon \hbox {-}node$. So each of these n nodes has contribution $\mu$. Then we can infer that

$$\begin{aligned} \gamma _{x}(S_{xy})= & {} \sum _{v\in S_{xy}}\frac{b\lambda }{\mu }\mu a^{dep_x(v)}=\sum ^n_{i=1}b\lambda a^i\\= & {} \sum _{v\in S_{xy}}\frac{b\lambda }{\mu }\mu a^{dep_v(y)}=\gamma _{y}(S_{xy}). \end{aligned}$$

Then we expand $\gamma _{x}$ and $\gamma _{y}$ using the union property

$$\begin{aligned} \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})= & {} \gamma _{x}(P_{x})+\gamma _{x}(S_{xy})\\&+\,\gamma _{x}(T_{x}{\setminus } \{x,y,S_{xy}\})\\ \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})= & {} \gamma _{y}(P_{y}{\setminus } \{x\})=\gamma _{y}(P_{x})+\gamma _{y}(S_{xy}) \end{aligned}$$

Then we can infer that

$$\begin{aligned} \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})>\gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\}). \end{aligned}$$

Then in the expression of $R^i(u)$, if u changes C(x) to $\mu$ and C(y) to $\epsilon$, u will increase the sum of the second and third term in $R^i(u)$, namely increase $C(x)\cdot \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})+C(y)\cdot \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})$, and the other terms don’t change according to symmetry. So this change will increase $R^i(u)$ which contradicts the assumption.

• (a2) Suppose in $\overline{T}$, there is an $\epsilon \hbox {-}node$ and the $\epsilon \hbox {-}node$ is a leaf node.

In this case, $\overline{T}$ has at least two leaf nodes. At least one leaf node denoted by x has contribution $\mu$. We then want to prove that if we delete x and add a new node y with contribution $C(y)=\mu$ and make the remain tree $\overline{T}{\setminus }\{x\}$ attached as a subtree to y, the new inner reward of u will increase meanwhile the total contribution of u remains unchanged.

We define the new tree with y replacing x as $\overline{T}_{new}$. Suppose there are n nodes in the path from x to y, denoted as $S_{xy}$. Then we compare the new inner reward $R^i(\overline{T}_{new})$ to the original inner reward $R^i(\overline{T})$. We expand $R^i(\overline{T}_{new})$ by using the properties of B(., .) as

$$\begin{aligned} R^i\left( \overline{T}_{new}\right)= & {} B\left( \overline{T}_{new},\overline{T}_{new}\right) \\= & {} B\left( \overline{T}\cup \{y\}{\setminus }\{x\},\overline{T}\cup \{y\}{\setminus }\{x\}\right) \\= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) \\&+\,B\left( y,\overline{T}{\setminus }\{x\}\right) +B\left( \overline{T}{\setminus }\{x\},y\right) +B(y,y). \end{aligned}$$

As y is the root node of $\overline{T}_{new}$, it holds that $B(\overline{T}{\setminus }\{x\},y)=0$. Therefore,

$$\begin{aligned} R^i\left( \overline{T}_{new}\right)= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +B\left( y,\overline{T}{\setminus }\{x\}\right) +B(y,y)\\= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +B\left( y,\overline{T}{\setminus }(\{x\}\cup S_{xy})\right) \\&+\,B(y,S_{xy}\cup \{y\})\\= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +B\left( y,\overline{T}{\setminus }(\{x\}\cup S_{xy})\right) \\&+\sum _{i=0}^n b\lambda a^i. \end{aligned}$$

For the original inner reward $R^i(\overline{T})$, we have

$$\begin{aligned} R^i\left( \overline{T}\right)= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) \\&+\,B\left( x,\overline{T}{\setminus }\{x\}\right) +B\left( \overline{T}{\setminus }\{x\},x\right) +B(x,x). \end{aligned}$$

As x is the leaf node of $\overline{T}$, it holds that $B(x,\overline{T}{\setminus }\{x\})=0$ and $B(\overline{T}{\setminus }\{x\},x)=B(S_{xy},x)$. Therefore,

$$\begin{aligned} R^i\left( \overline{T}\right)= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +B(S_{xy},x)+B(x,x)\\= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +\sum _{v\in S_{xy}\cup \{x\}} \frac{b\lambda }{\mu }a^{dep_v{x}}\\= & {} B\left( \overline{T}{\setminus }\{x\},\overline{T}{\setminus }\{x\}\right) +\sum _{i=0}^n b\lambda a^i. \end{aligned}$$

We find that $R^i(\overline{T}_{new})>R^i(\overline{T})$ since $B(y,\overline{T}{\setminus }(\{x\}\cup S_{xy}))>0$, which contradicts the assumption.

• (a3) Suppose in $\overline{T}$, there is no $\epsilon \hbox {-}node$. The proof is totally the same as in a2). We can find that the proof in a2) use the assumption only to make sure that the non-leaf nodes have contribution $\mu$.

• (b) Suppose $\overline{T}$ is a chain and there is an $\epsilon \hbox {-}node$ which is neither the root nor the leaf of the chain.

We denote the $\epsilon \hbox {-}node$ as x and the leaf of the chain as y. Then we prove that u can increase the inner reward by changing C(x) to $\mu$ and changing C(y) to $\epsilon$. The proof is similar to a1) as a chain is a special case of tree. Suppose there are n nodes in the path from y to x, denoted as $S_{xy}$. Let $S_u=\overline{T_u}{\setminus }\{x,y\}$, and let $P_x,P_y$ be the set of ancestors of x, y in the reward computation tree. Here we just simplify the proof by using results in a1):

$$\begin{aligned} R^i(u)= & {} C(x)\cdot \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})\\&+\,C(y)\cdot \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})+B(S_u,S_u)\\&+\,\frac{b\lambda }{\mu }\left[ \left( a^{dep_x(y)}+a^{dep_y(x)}\right) C(x)C(y)\right. \\&\left. +\,C(x)^2+C(y)^2\right] . \end{aligned}$$

$$\begin{aligned} \gamma _{x}((P_{x}\cup T_{x}){\setminus }\{x,y\})= & {} \gamma _{x}(P_{x})+\gamma _{x}(S_{xy})\\&+\,\gamma _{x}(T_{x}{\setminus } \{x,y,S_{xy}\})\\ \gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\})= & {} \gamma _{y}(P_{y}{\setminus } \{x\})\\= & {} \gamma _{y}(P_{x})+\gamma _{y}(S_{xy}), \end{aligned}$$

Here the only difference is that $\overline{T}$ is a chain. So $\gamma _{x}(T_{x}{\setminus } \{x,y,S_{xy}\})=0$. But we still have

$$\begin{aligned} \gamma _{x}((P_{x}\cup T_{x}){\setminus } \{x,y\})>\gamma _{y}((P_{y}\cup T_{y}){\setminus } \{x,y\}). \end{aligned}$$

according to $\gamma _x(P_x)>\gamma _y(P_x)$ and $\gamma _{x}(S_{xy})=\gamma _{y}(S_{xy})$.

This change will increase $R^i(u)$ which contradicts the assumption.

Above all, we know if $R^i(x)$ is maximized, $\overline{T}$ is an $\epsilon \hbox {-}chain$ or a chain with an $\epsilon \hbox {-}$node which is the leaf. We know these two topology is just reverse up-side-down. So the inner rewards are the same according to symmetry. $\square$

Until now, we know u can partition as an $\epsilon \hbox {-}chain$ to maximize $R^i(u)$. Then we begin the second main part. We want to prove u’s partition as an $\epsilon \hbox {-}chain$ will maximize his external reward, $R^e(u)$. In next lemma, it would be better to root each tree in $\underline{T}$ to one leaf node in $\overline{T}$.

Lemma 4

For any given topology $\overline{T_u}$, suppose $u_1,u_2,\ldots$, $u_k$ are the nodes in $\overline{T_u}$. There exists a partition that maximizes $R^e(u)$ in which each tree in $\underline{T_u}$ is attached to a single node $u_i$, for some $i=1,2,\ldots ,k$.

Proof

We denote the trees in $\underline{T}$ as $T_1,\ldots ,T_s$. Suppose $T_1,\ldots ,T_s$ are attached to $v_1,\ldots ,v_s$ in $\overline{T}$. ($v_1,\ldots ,v_s$ needn’t be different.) Then we use the definition of the external reward and get

$$\begin{aligned} R^e(u)=B\left( \overline{T},\underline{T}\right)= & {} \sum ^s_{i=1}B\left( \overline{T},T_i\right) \\= & {} \sum ^s_{i=1}B(P_{v_i}\cup \{v_i\},T_i)\\= & {} \sum ^s_{i=1}\sum _{u\in P_{v_i}\cup \{v_i\}}\sum _{v\in T_i}\frac{\lambda }{\mu }b\\&\cdot \, C(u)C(v)a^{dep_u(v)}.\\= & {} \sum ^s_{i=1}\sum _{u\in P_{v_i}\cup \{v_i\}}\sum _{v\in T_i}\frac{\lambda }{\mu }b\\&\cdot \, C(u)C(v)a^{dep_{u}(v_i)+dep_{v_i}(v)}\\= & {} \frac{b\lambda }{\mu }\sum ^k_{i=1}\left( \sum _{v\in T_i}C(v)a^{dep_{v_i}(v)}\right) \\&\left( \sum _{u\in P_{v_i}\cup \{v_i\}}C(u)a^{dep_{v_i}(u)}\right) . \end{aligned}$$

Suppose $u^*$ is the node in $\overline{T}$ which can maximize $\sum _{u\in P_{v_i}\cup \{v_i\}}C(u)a^{dep_{v_i}(u)}$. For each $T_i$ ($i=1,\ldots ,s$), $\sum _{v\in T_i}C(v)a^{dep_{v_i}{v}}$ depends only on the topology of $T_i$. Therefore, taking the attached nodes $v_i=u^*$ can maximize $R^e(u)$. It indicates that there is a partition that each tree in $\underline{T}$ is attached to one node in $\overline{T}$. $\square$

We now know that $R^e(u)$ can be maximized when each tree in $\underline{T_u}$ is attached to a single node in $\overline{T_u}$. For any given $\overline{T_u}$, in order to maximize $R^e(u)$, we thus only need to consider partition in which each tree in $\underline{T_u}$ is attached to some node $u^*$ in $\overline{T_u}$. Then using this property, we show that an $\epsilon \hbox {-}chain$ is the best partition for maximizing u’s external reward.

Lemma 5

If $R^e(u)$ is maximized, $\overline{T_u}$ must be an $\epsilon \hbox {-}chain$ and $u^*$ is the leaf node of $\overline{T_u}$.

Proof

Firstly, let us show $R^e(u)$ is maximized, $\overline{T_u}$ must be a chain and $u^*$ is a leaf node in $\overline{T_u}$. We prove it by contradiction. Suppose $\overline{T_u}$ is not a chain or $u^*$ is not a leaf node in $\overline{T_u}$. We find that there exists a leaf node $u_L$ in $\overline{T}$ which is not in set $P_{u^*}\cup \{u^*\}$. We delete $u_L$ in $\overline{T}$ and let it be the new root $u'_L$ of $\overline{T}{\setminus }{u_L}$, namely relocate $u_L$ to be the root of $\overline{T}{\setminus }{u_L}$. We define the new tree as $\overline{T}_{new}$. We then compare the original external reward $R^e(u)$ and the new external reward calculated by $\overline{T}_{new}$, $R^e(u)'$.

$$\begin{aligned}&R^e(u)=B(\overline{T},\underline{T})=B(P_{u^*}\cup \{u^*\},\underline{T})\\&R^e(u)'=B(\overline{T}_{new},\underline{T})=B(P_{u^*}\cup \{u^*,u'_L\},\underline{T})>R^e(u). \end{aligned}$$

From the above equality, we get a contradiction that u can increase his external reward by improvements. So if $R^e(u)$ is maximized, $\overline{T_u}$ must be a chain and $u^*$ is a leaf node in $\overline{T_u}$.

Our next step is to show $\overline{T}$ is an $\epsilon \hbox {-}chain$. We also prove it by contradiction. Suppose $\overline{T}$ is a chain but not an $\epsilon \hbox {-}chain$ and u can get the maximum external reward. Then there exists a node x which is not the root node of $\overline{T}$ and has contribution $C(x)<\mu$. As x is not the root, we denote x’s parent as y. Then we show that if we change C(x) to $C(x)+\alpha$ and C(y) to $C(y)-\alpha$, (The constraints are $\alpha <\mu -C(x)$ and $\alpha <C(y)$. We can take very small $\alpha$.) u can get higher external reward. If we change the contribution like above, the new external reward becomes $R^e(u)'$. Then we compare it to the original external reward $R^e(u)$:

$$\begin{aligned} R^e(u)= & {} B(\overline{T},\underline{T})=B(\overline{T}{\setminus }\{x,y\},\underline{T})+B(x,\underline{T})+B(y,\underline{T})\\= & {} B(\overline{T}{\setminus }\{x,y\},\underline{T})+C(x)\sum _{v\in \underline{T}}\frac{\lambda b}{\mu }C(v)a^{dep_x(v)}\\&+C(y)\sum _{v\in \underline{T}}\frac{\lambda b}{\mu }C(v)a^{dep_y(v)}.\\= & {} (C(x)+a C(y))\sum _{v\in \underline{T}}\frac{\lambda b}{\mu }C(v)a^{dep_x(v)}\\&+B(\overline{T}{\setminus }\{x,y\},\underline{T}). \end{aligned}$$

In the same way, we can write

$$\begin{aligned} R^e(u)'= & {} B(\overline{T}{\setminus }\{x,y\},\underline{T})+(C(x)+\alpha +a C(y)-a\alpha )\\&\cdot \sum _{v\in \underline{T}}\frac{\lambda b}{\mu }C(v)a^{dep_x(v)}. \end{aligned}$$

According to the condition of TDRM that $a<1$, we get $R^e(u)<R^e(u)'$. So we get the contradiction and get our solution that if u wants to maximize $R^e(u)$, he must take $\overline{T_u}$ as an $\epsilon \hbox {-}chain$ and $u^*$ is the leaf node of $\overline{T_u}$. $\square$

By Lemmas 3 and 5, we know that the partition which makes $\overline{T_u}$ an $\epsilon \hbox {-}chain$, and in which all trees in $\underline{T_u}$ are attached to the tail node of $\overline{T_u}$, can maximize both $R^i(u)$ and $R^e(u)$. According to the definition that $R(u)=R^i(u)+R^e(u)+\phi C(u)$, we can infer that such a partition thus maximizes R(u). However, if the participant u simply joins the referral tree as a single, non-Sybil node with its entire contribution, TDRM will automatically also transform u into the same $\epsilon \hbox {-}chain$ in the reward computation tree. Thus, u has no benefit from joining as multiple identities, which proves USA.