Limiting User’s Sybil Attack in Resource Sharing

Abstract

In this work, we discuss the sybil attack to a sharing economic system where each participant contributes its own resource for all to share. We are interested in the robustness of the market equilibrium mechanism in withstanding such an attack, in terms of the incentive ratio to measure how much one could gain by splitting its identity and reconstructing its communication connections with others. On one hand, weshow that no player can increase more than $\sqrt{2}$ times of their original share from the market equilibrium solution, by characterizing the worst case under which strategic agent can obtain the maximum utility gain after manipulation. On the other hand, such a bound of $\sqrt{2}$ is proved to be tight by constructing a proper instance, for which this bound is reached.

1 Introduction

Resource sharing has now attracted much commercial efforts in many good and service application, such as done in AirBnB, mobike, UBER, etc., to make participants benefit from exchanging each own idle resource with others and to improve the social benefit as well as revenue. A key question in sharing is whether one would be motivated to make their best effort, or in the current setting to share their resources to the maximum availability to the sharing community for others to use. In addition, whether our protocol would prevent the abuse of the system by some to deviate from the expected social behavior by participation agents.

In this paper, we focus on the resource sharing over networks with autonomous participants (or agents), which goes beyond the peer-to-peer (P2P) bandwidth sharing idea [27]. Peers in such networks act as both suppliers and customers of resources and make their resources directly available to their network peers. Their utilities are determined by the total of resources received from all others. Such a resource sharing system over P2P network can be modeled as a pure exchange economy, a kind of Arrow-Debreu Market. Therefore, we are interested in the market equilibrium as the allocation mechanism to distribute those resources over P2P network.

As a distributed scheme, one of critical issues for the resource sharing problem is how to allocate resource in a fair fashion to maintain agents participation, i.e., ensuring that agents will share their resources fairly, and hence will agree to exchange resource with others. To motivate sharing, [16] pioneered the use of incentive techniques to drive cooperation and to promote voluntary contributions by participating agents. By taking such an approach, Cohen created the BitTorrent protocol, which has been well recognized as an Internet success to change “the entertainment industry and the interchange of information in Web”[5]. From the view of fairness consideration, Wu and Zhang [27], motivated by Bit-Torrent, have pioneered a model of proportional response for the bandwidth sharing problem on peer-to-peer system. Under this model, the resource allocation satisfies the condition that each peer provides each neighbor a portion of its contribution proportional to the percentage it receives from this neighbor among all its neighbors. They showed its economic efficiency by its convergence to a market equilibrium of a pure exchange economy. To obtain the market equilibrium, Wu and Zhang modeled the peer-to-peer system as an undirected graph $G=(V,E)$, where each vertex v represents an agent, with $w_v$ units of divisible underused resources (or weight) to be distributed among its neighbors. And they proposed an elegant network decomposition on such a graph, which is called the bottleneck decomposition [27]. Based on this decomposition, they applied the idea of maximum flow to derive a proportional response allocation protocol among all agents whose output just is the allocation of the market equilibrium. This protocol is named as Bottleneck Decomposition Mechanism, or BD Mechanism for short [10, 11].

However, agents are rational and strategic. The resource allocation from BD Mechanism depends on agents’ reported information rather than their true information. So we are interested in the incentives of agents against BD Mechanism: when a system designer proposes BD Mechanism, is it possible for an agent to deviate from it by strategic behavior and improve its utility? Further, if the answer is “yes”, does we can characterize the extent to which an agent’s utility can be increased by such a strategic play? In recent works, [10, 11] proved the incentive compatibility of this protocol against strategic behaviors of mis-reporting connectivity and the amount of resources agent owns. In this paper, we further explore its resistance to manipulative behavior by considering a kind of strategy that an agent disguises itself by creating several copied false nodes with its resources assigning among them. The motivation for us to discuss this strategic behavior, since it just is the behavior which is called sybil attack. In peer-to-peer system, sybil attack is a grave threat and subverts the security of network “by creating a large number of pseudonymous identities, using them to gain a disproportionately large influence” [24]. Compared with collusion, sybil attack strategy is easier to execute on the Internet since getting another identification, such as duplicating IP addresses, is cheap. Further, such a strategy is very difficult to detect since identifying each participant on Internet is virtually impossible. As of 2012, evidence showed that large-scale Sybil attacks could be carried out cheaply and efficiently in extant realistic systems such as BitTorrent Mainline DHT [25, 26].

Recently, Chen et al. [6, 7] have done a series of work on the sybil attack strategy against BD Mechanism in resource sharing. They first showed BD Mechanism is not robust to such a strategy any more. To characterize how much one can improve its utility at most and formalize such an improvement, they employed the concept of incentive ratio. Incentive ratio, which is first introduced by Chen et al. [9], is defined as the factor of the largest possible utility gain that a participant can achieve by behaving strategically, given that all other participants have their strategies unchanged. In the distributed environment, all agents only have limited knowledge due to the decentralization of the system. They need an incredible effort to know the full information of the game and do complicated computation as well. A small incentive ratio provides a safety margin where BD Mechanism will not be breached if no agents will pursue a small improvement in its utility in sacrificing some of its peers. Therefore a smaller incentive ratio implies an agent has less incentive to influence the allocation result from BD Mechanism through strategic considerations. In [6, 7], Chen et al. discussed the settings of tree networks and cycle networks and proved that the incentive ratio of BD Mechanism for sybil attack strategy is exactly 2 on trees and is bounded by 2 and 4 on cycles, respectively.

In this paper, we are more concerned about the resource sharing in the context of sharing economy, in which the ideal state is that all of participants are fully connected. Thus our study mainly focuses on the network structure of complete graph and study the agents’ incentive against BD Mechanism by sybil attack strategy.

Related Work

The classical economists and algorithmic game theorists have made an extensive study of competitive equilibrium [2], in terms of computation for prices and allocation [20], complexity and approximation [13,14,15, 18, 22, 28]. Those works have started to have an influence in resource allocation among multiple agents, especially in the important implementations for the Internet enabled economic, management and social activities. How to fairly redistribute and share those resources have become an important issue with more and more online platforms and APPs which facilitate the exchange of commodities and services, such as Uber, Mobike, AirBnB, Opengarden, Swap...

The automated process through information and communication technology for Internet applications has made their successes relied on the voluntary cooperations of participating agents. [16] pioneered the study of such incentive techniques in mechanism design and in performance analysis for such peer-to-peer resource sharing systems. Agent strategic behaviors against market equilibrium mechanism has been analyzed in the Fisher market for linear markets [1] and for constant elasticity of substitution markets [4]. As a special case of Arrow-Debreu market, the proportional response protocol was shown to be equivalent to a market equilibrium solution [27] in the resource sharing system under P2P setting. [10, 11] proved that the market equilibrium from the proportional response protocol is incentive compatible to two types of strategic behaviors for each agent: cheating on its connectivity with the rest of network and misreporting its own resource amount. But for the strategy of sybil attack, the proportional response protocol is not truthful any more. In addition, Chen et al. computed the percentage of improvement by this strategy with the aid of incentive ratio. They proved that incentive ratio is exactly 2 if the underlying network is a tree [6] and is bounded by 2 and 4 on cycles [7], respectively. The concept of incentive ratio is first introduced by Chen et al. [9], motivated by the concept of price of anarchy [19, 23]. Comparing such two kinds of ratios, the former measures the most individual gains one may acquire in deviation from truthful behavior, while the latter models the loss of social efficiency in selfish Nash equilibrium in comparison to social optimality.

The strategy of sybil attack was first discussed by Douceur [12] for the consideration of the security of P2P network. Meanwhile, similar strategic strategies are also discussed in other situations, such as the false-name bidding in Internet auctions. The false-name bidding [30] is a serious fraud, in which false-name bids are submitted by a single agent under multiple fictitious identities. It has been known that the famous VCG mechanism is not incentive compatible against the false-name bidding, as a result of the study on the false-name-proof auction mechanisms design [17, 29], and on the efficiency guarantee of the VCG mechanism [3].

Technical Contributions and Main Results

We analyze incentive ratio to quantitatively measure the maximal magnitude of utility gain by sybil attack followed a proportional response mechanism. Our main result in this paper is that the incentive ratios are exactly $\sqrt{2}$ on complete graphs. To obtain the ideal result, we propose a proper example for the lower bound. On the other hand, we characterize all possible bottleneck decompositions before and after manipulation with the help of the structure of complete graphs. And for each different case, we compute the maximal ratio by considering the maximum possible utility improvement, respectively, to reach the upper bound.

There has been several important research results for various utility functions where the most relevant one is the incentive ratio of two matching bound for linear utilities in the Fisher market [8, 9], which is not directly applicable to our resource exchange model here but a special case of Arrow-Debreu market. As the incentive ratio for the Arrow-Debreu model is known to be unbounded [21] even in linear exchange economy, it is interesting to show a non-trivial matching bound under the setting discussed here. The practical network sharing economy with a market equilibrium solution still remains to be interesting with a limited rationality in terms of truthful behavior.

2 Preliminary

Our resource sharing system is based on a connected and undirected network $G=(V,E)$. Each vertex $v\in V$ represents an agent with an upload resource amount (weight) $w_v>0$ for exchanging with its neighbors, where $\Gamma (v)=\{u: (v,u)\in E\}$ is the neighborhood of v. Let $x_{vu}$ be the amount of resource v allocates to neighbor u ($0\le x_{vu}\le w_v$) and $X=\{x_{uv}\}$ be an allocation. The utility of agent v from allocation X is defined as $U_v(X)=\sum _{u\in \Gamma (v)}x_{uv}$, i.e. all received resource from its neighbors. In the resource sharing environment, one of critical issues is how to design an allocation mechanism to maintain the agents participation, i.e., ensuring that agents will share their resources in a fair fashion. Wu and Zhang [27] pioneered the concept of “proportional response” inspired by the idea of “tit-for-tat” for the consideration of fairness.

Proportional Response. A mechanism is called proportional response if an allocation X from this mechanism satisfies $x_{vu}=\frac{x_{uv}}{\sum _{k\in \Gamma (v)}x_{kv}}w_v$, that is the allocation of each agent’s resource is proportional to what it receives from its neighbors.

To achieve a proportional response mechanism, a combinatorial structure, called bottleneck decomposition is derived in [27]. For set $S\subseteq V$, define $w(S)=\sum _{v\in S}w_v$ and $\Gamma (S)=\cup _{v\in S}\Gamma (v)$. It is possible that $S\cap \Gamma (S)\ne \emptyset$. Denote $\alpha (S)=\frac{w(\Gamma (S))}{w(S)}$ to be the inclusive expansion ratio of S, or the $\alpha$-ratio of S for short. A set $B\subseteq V$ is called a bottleneck of G if $\alpha (B)=\min _{S\subseteq V}\alpha (S)$. A bottleneck with the maximal size is called the maximal bottleneck.

Bottleneck Decomposition. Given $G=(V,E;w)$. Start with $V_1=V$, $G_1=G$ and $i=1$. Find the maximal bottleneck $B_i$ of $G_i$ and let $G_{i+1}$ be the induced subgraph on the vertex set $V_{i+1}=V_i- \left( B_i\cup C_i\right)$, where $C_i=\Gamma (B_i)\cap V_i$, the neighbor set of $B_i$ in $G_i$. Repeat if $G_{i+1}\ne \emptyset$ and set $k=i$ if $G_{i+1}=\emptyset$. Then we call $\mathcal {B}=\{(B_1,C_1),\cdots ,(B_k,C_k)\}$ the bottleneck decomposition of G, $(B_i,C_i)$ the i-th bottleneck pair and $\alpha _i=w(C_i)/w(B_i)$ the $\alpha$-ratio of $(B_i,C_i)$.

B -class and C -class. Given $\mathcal {B}=\{(B_1,C_1),\cdots ,(B_{k},C_{k})\}$. For pair $(B_i,C_i)$ with $\alpha _i<1$, each vertex in $B_i$ (or $C_i$) is called a B-class (or C-class) vertex. For the special case $B_k=C_k=V_k$, i.e., $\alpha _k=1$, all vertices in $B_k$ are categorized as both B-class and C-class.

Bottleneck decomposition has a lot of beautiful combinatorial properties which are critical for us to obtain the tight incentive ratio of $\sqrt{2}$.

Proposition 2.1

[27]. Given a graph G, the bottleneck decomposition of G is unique and

• 1. $0< \alpha _1<\alpha _2<\cdots <\alpha _k\le 1$;

• 2. if $\alpha _i=1$, then $i=k$ and $B_i=C_i$; otherwise $B_i$ is an independent set and $B_i\cap C_i=\emptyset$;

BD Mechanism. Given the bottleneck decomposition $\mathcal {B}$, an allocation Wu and Zhang [27] can be determined by distinguishing three cases. Cheng et al. [10, 11] named it as BD Mechanism for short.

• For $(B_i,C_i)$ with $\alpha _i<1$, consider the bipartite graph $\widehat{G}=(B_i,C_i;E_i)$ with $E_i=B_i\times C_i$. Construct a network $N=(V_N,E_N)$ with $V_N=\{s,t\}\cup B_i\cup C_i$ and directed edges (s, u) with capacity $w_u$ for $u\in B_i$, (v, t) with capacity $w_v/\alpha _i$ for $v\in C_i$ and (u, v) with capacity $+\infty$ for $(u,v)\in E_i$. The max-flow min-cut theorem ensures a maximal flow $\{f_{uv}\}$, $u\in B_i$ and $v\in C_i$, such that $\sum _{v\in \Gamma (u)\cap C_i}f_{uv}=w_u$ and $\sum _{u\in \Gamma (v)\cap B_i}f_{uv}=w_v/\alpha _i$. Let the allocation be $x_{uv}=f_{uv}$ and $x_{vu}=\alpha _if_{uv}$ implying $\sum _{u\in \Gamma (v)\cap B_i}x_{vu}=\sum _{u\in \Gamma (v)\cap B_i}\alpha _i\cdot f_{vu}=w_v$. Figure 1 illustrates it.

• For $\alpha _k=1$ (i.e., $B_k=C_k$), construct a bipartite graph $\widehat{G}=(B_k,B'_k;E'_k)$ where $B'_k$ is a copy of $B_k$, there is an edge $(u,v')\in E'_k$ if and only if $(u,v)\in E[B_k]$. Construct a network by the above method, for any edge $(u,v')\in E'_k$, there exists flow $f_{uv'}$ such that $\sum _{v'\in \Gamma (u)\cap B'_k}f_{uv'}=w_u$. Let the allocation be $x_{uv}=f_{uv'}$.

• For any other edge $(u,v)\not \in B_i\times C_i$, $i=1,2,\cdots ,k$, define $x_{uv}=0$.

Fig. 1.

The illustration of BD Mechanism.

Proposition 2.2

[27]. BD Mechanism is a proportional response mechanism.

On the other hand the resource sharing system can be modeled as a pure exchange economy, for which an efficient allocation is the market equilibrium.

Market Equilibrium. In the exchange economy, price vector $p=(p_v)_{v\in V}$ together with an allocation X is called a market equilibrium if for any agent $v\in V$ the following holds, 1. $\sum _{u\in \Gamma (v)}x_{vu}=w_v$ (market clearance); 2. $\sum _{u\in \Gamma (v)}p_u\frac{x_{uv}}{w_u}\le p_v$ (budget constraint); 3. $X=(x_{vu})$ maximizes the utility $U_v=\sum _{u\in \Gamma (v)}x_{uv}$ subject to the budget constraint (individual optimality).

BD Mechanism is not only fair as stated above but also efficient, since the proportional response allocation from it also is a market equilibrium. Given a bottleneck decomposition, if a price vector p is well defined as: $p_u=\alpha _iw_u$, if $u\in B_i$; and $p_u=w_u$ otherwise, then

Proposition 2.3

[27]. (p, X) is a market equilibrium. Furthermore, each agent u’s utility is $U_u=w_u\cdot \alpha _i$ if $u\in B_i$; $U_u=\frac{w_u}{\alpha _i}$ if $u\in C_i$.

Note that $U_u\ge w_u$ if u is in C-class and $U_u\le w_u$ if u is in B-class, as $\alpha _i\le 1$ by the first claim in Proposition 2.1. From a system design point of view, although BD Mechanism shall allocate resource among interconnected participants fairly and efficiently, a problem occurs that, an agent may or may not follow BD Mechanism at the execution level. Can agents make strategic moves for gains in their utilities? We call such a problem with incentive compatibility consideration the resource exchange game.

In an instance of resource sharing game, the collection $\mathrm {\mathbf {w}}=(w_1,\cdots ,w_n)\in R^{n}$ is referred as the weight profile. For agent v, let $\mathrm {\mathbf {w}}_{-v}$ be the weight profile without v. Since the utility of agent v depends on the underlying network G and $\mathrm {\mathbf {w}}$, it is written as $U_v(G;\mathrm {\mathbf {w}})$. Now we study a strategic move, called sybil attack strategy, that is one agent may create more than one fake identity by splitting itself into several copied nodes, and assign a weight to each node. Thus for a strategic agent v, it shall make multiple decisions as follows:

$\bullet$ how many copied nodes does it split into?

$\bullet$ how to build the connections between the copied nodes and its neighbors?

$\bullet$ how to assign its own weight to each copied node?

In this paper, we model the sybil attack strategy as: the strategic agent v shall split itself into m nodes ${v^1,\cdots ,v^m}$, $1\le m\le d_v$ ($d_v$ is the degree of v), assign an amount $w_{v^i}$ of resource to each node $v^i$, satisfying $0\le w_{v^i}\le w_v$ and $\sum _{i=1}^mw_{v^i}=w_v$, and each neighbor of v in original G is connected to one of copied nodes, not vice versa. Let $G'$ be the resulting network after agent v making above three decisions and agent v’s new utility is denoted by $U'_v(G';w_{v^1},\cdots ,w_{v^{m}},\mathrm {\mathbf {w}}_{-v})$.

Definition 2.1

(Incentive Ratio). In a resource exchange game, the incentive ratio of agent v under BD Mechanism for the sybil attack strategy is

$$\begin{aligned} \zeta _v=\max _{1\le m\le d_v}\max _{w_{v^i}\in [0,w_v],\sum _{i=1}^{m}w_{v^i}=w_v;\mathbf {w}_{-v};G'} \frac{U_v'(G';w_{v^1},\cdots ,w_{v^m},\mathrm {\mathbf {w}}_{-v})}{U_v(G;\mathrm {\mathbf {w}}_{v})}. \end{aligned}$$

The incentive ratio of BD mechanism in resource exchange game is defined to be $\zeta =\max _{v\in V}\zeta _v$.

There is a special case that a strategic agent v splits itself into $d_v$ nodes and each node is connected to one of neighbors. Thus there is one to one correspondence between copied nodes and neighbors. Chen et al. showed the equivalence of the special strategy and the general sybil attack, which simplifies the decision making for strategic agent.

Proposition 2.4

[6, 7]. In a resource sharing game, the incentive ratio of BD mechanism with respect to sybil attack strategy can be achieved by splitting into $d_v$ nodes and making each node be connected to one neighbor, where $d_v$ is the degree of strategic agent v.

3 Incentive Ratio of BD Mechanism on Complete Graph $K_n$

In this section, we focus on the resource sharing game in which the underlying network is a complete graph $K_n$. Before proceeding the details of discussion, let us introduce some necessary notations and propositions.

Lemma 3.1

For any complete graph $K_n$, the bottleneck decomposition $\mathcal {B}$ only contains one bottleneck pair $\mathcal {B}=\{(B_1,C_1)\}$ and it shall be

• 1. $\alpha _1=1$ and $B_1=C_1=V$, or

• 2. $\alpha _1<1$, $B_1$ only has one vertex and $C_1$ has other $n-1$ vertices.

Proof

Let us focus on the first pair $(B_1,C_1)$ in $\mathcal {B}$. Of course, there exist two cases: $\alpha _1=1$ and $\alpha _1<1$. If $\alpha _1=1$, then $B_1=C_1=V$ and the first claim holds. If $\alpha _1<1$, then $B_1$ must be independent by the first claim in Proposition 2.1. So the structure of complete graph makes $B_1$ only contain one vertex. Further the neighborhood $\Gamma (B_1)=V-B_1$. Hence $C_1$ contains other $n-1$ vertices and $V_2=V-(B_1\cup C_1)=\emptyset$ which means there is only one pair $(B_1,C_1)$ in $\mathcal {B}$.    $\square$

Since the complete graph $K_n$ has n vertices, without loss of generality, let the vertex who plays strategically be v, and the others be $u^1,\cdots ,u^{n-1}$. In addition, such a strategic vertex v shall split itself into $n-1$ duplicated nodes by Proposition 2.4. For the sake of convenience, we denote the duplicated node set by $\Lambda (v)=\{v^1,\cdots ,v^{n-1}\}$ and the neighborhood of v by $\Gamma (v)=\{u^1,\cdots ,u^{n-1}\}$, where each $v^j$ is adjacent to $u^j$, $j=1,\cdots ,n-1$, in $G'$. Because of the structure of complete graphs, the induced graph $G'[\Gamma (v)]$ also is a complete graph $K_{n-1}$ and the vertex set of new graph $G'$ after manipulation is $V'=\Gamma (v)\cup \Lambda (v)$.

Similar to the notations of bottleneck decomposition in original $K_n$, the bottleneck decomposition of $G'$ is denoted by $\mathcal {B}'=\{(B_1',C_1'),\cdots ,(B_{k'}',C_{k'}')\}$ and let the $\alpha$-ratio of each pair $(B_i',C_i')$ be $\alpha _i'$, $i=1,\cdots ,k'$. Likewise, $V'_1=V'$, $V_{i+1}'=V_{i}' - (B_i'\cup C_i')$ for $i=1,2,\cdots , k'-1$ and $G_i'=G'[V_i']$, $i=1,2,\cdots , k'$. The vertex in $B_i'$ or $C_i'$, $i=1,\cdots ,k'$, is called the $B'$-class or $C'$-class vertex and $\Gamma '(v)$ is the neighborhood of v in $G'$, $\Gamma '(S)=\cup _{v\in S}\Gamma '(v)$ for any vertex set $S\subseteq V'$. Based on the structure of $K_n$ and $G'$, we characterize the bottleneck decomposition $\mathcal {B}'$ carefully in the following proposition.

Lemma 3.2

Let $\mathcal {B}'$ be the bottleneck decomposition of $G'$, then it shall be

• 1. $\mathcal {B}'=\{(B_1',C_1')\}$, where $B_1'=C_1'=V'$ with $\alpha _1'=1$, or

• 2. $\mathcal {B}'=\{(B_1',C_1')\}$, where $B_1'=\{u^j,\Lambda (v)-v^j\}$, $C_1'=\{v^j,\Gamma (v)-u^j\}$, $j\in \{1,\cdots ,n-1\}$ (an example in Fig. 3), or

• 3. $\mathcal {B}'=\{(B_1',C_1'),\cdots ,(B_{k'}',C_{k'}')\}$, where for each $i=1,\cdots , k'-1$, $B_i'=\{v^{h_1},\cdots ,v^{h_t}\}$, $C_i'=\{u^{h_1},\cdots ,u^{h_t}\}$, $h_1,\cdots ,h_t\in \{1,\cdots ,n-1\}$; and the last pair $(B_{k'}',C_{k'}')$ shall be

  • (a) $B_{k'}'=C_{k'}'=\emptyset$ ($\mathcal {B}'$ actually contains $k'-1$ pairs), or

  • (b) $B_{k'}'=C_{k'}'$ with $\alpha _{k'}'=1$, or

  • (c) $B_{k'}'=\{u^j,\Lambda (v)-\cup _{i=1}^{k'-1}B_i'-v^j\}$, $C_{k'}'=\{v^j,\Gamma (v)-\cup _{i=1}^{k'-1}C_i'-u^j\}$ with $\alpha _{k'}'<1$.

Proof

To show the correctness of this proposition, we shall discuss two situations depending on $\alpha _1'=1$ or $\alpha _1'<1$. Of course, if $\alpha _1'=1$, then $B_1'=C_1'=V$ which induces the first case. Otherwise if $\alpha _1'<1$, then $B_1'$ must be independent by the first claim of Proposition 2.1 and it may contain one vertex $u^j$ from $\Gamma (v)$ or not. For the former that one vertex $u^j\in B_1'$, then $v^j\in C_1'$ and all others in $\Gamma (v)$ except for $u^j$ must belong to $C_1'$, because the induced subgraph of $\Gamma (v)=\{u^1,\cdots ,u^{n-1}\}$ still is a complete graph $K_{n-1}$ in $G'$ as mentioned before. In addition, each $v^h\in \Lambda (v)-v^j$ has a unique neighbor $u^h\in C_1'$, $h\ne j$, and is not adjacent to $u^j$. So adding all $v^h$, $h\ne j$, into $B_1'$ not only keeps the independence property of $B_1'$, but also makes its $\alpha$-ratio decrease. Thus we get the second case, that is $B_1'=\{u^j,\Lambda (v)-v^j\}$ and $C_1'=\{v^j,\Gamma (v)-u^j\}$.

If $B_1'$ dose not contain any vertex from $\Gamma (v)$, it must have the form as $B_1'=\{v^{h_1},\cdots ,v^{h_t}\}$ and $C_1'=\{u^{h_1},\cdots ,u^{h_t}\}$ with the property of $\frac{w_{u^h}}{w_{v^h}}=\frac{w(C_1')}{w(B_1')}=\alpha _1'$. Recalling the process of bottleneck decomposition, $V_2'=V'-(B_1'\cup C_1')=(\Lambda (v)-B_1')\cup (\Gamma (v)-C_1')$ and the rest graph $G_2'$ has the same structure as $G'$. Now we turn to discuss $(B_2',C_2')$ which is the maximal bottleneck in $G_2'$. If $V_2'=\emptyset$, then $B_2'=C_2'=\emptyset$. It implies case 3-(a). If $V_2'\ne \emptyset$ and $B_2'=C_2'=V_2'$ with $\alpha _2'=1$, then case 3-(b) holds. If $B_2'$ has one vertex $u^j\in \Gamma (v)-C_1'$, then $B_2'$ and $C_2'$ has the same structure as case 2. So case 3-(c) is derived. If there is no any $u^j$ in $B_2'$, then we continue the same analysis until one of above three cases happens.    $\square$

Our main result on the incentive ratio of BD Mechanism for the sybil attack strategy on complete graphs is the following.

Theorem 3.1

If the network of resource exchange system is a complete graph $K_n$, then the incentive ratio of BD Mechanism for the sybil attack strategy is exactly $\sqrt{2}$.

To obtain Theorem 3.1, we try our best to prove the lower bound and upper bound of the incentive ratio on $K_n$ are both equal to $\sqrt{2}$ in the subsequent two subsections.

3.1 Lower Bound of Incentive Ratio on $K_n$

In this subsection, we will prove the lower bound of $\sqrt{2}$ by proposing an example.

Theorem 3.2

If the network of resource sharing system is a complete graph, then the incentive ratio of BD Mechanism for the sybil attack strategy is at least $\sqrt{2}$, i.e. $\zeta \ge \sqrt{2}$.

Proof

Assume network G is a triangle $K_3$, shown in Fig. 2(a). The weights of all vertices are $w_{v}=2\sqrt{2}-2$, $w_{u^1}=1$ and $w_{u^2}=3-2\sqrt{2}$. The bottleneck decomposition $\mathcal {B}$ is $\{(B_1,C_1)\}$ with $B_1=C_1=\{v,u^1,u^2\}$ and $\alpha _1=1$. And the utility of v is $w_{v}\cdot \alpha _1=2\sqrt{2}-2$.

Fig. 2.

An example showing the lower bound of incentive ration on complete graphs.

If vertex v strategically splits itself into $v^{1}$ and $v^2$ and assigns $\sqrt{2}-1$ units resource to each node, respectively, as shown in Fig. 2-(b). Then the bottleneck decomposition of new graph shall change to be $\{(B'_1,C'_1)\}$, where $B'_1=\{u^1,v^2\}$, $C'_1=\{u^2,v^1\}$ with $\alpha _1'=\sqrt{2}-1$. At this time it is easy to compute $U_{v^1}'=(\sqrt{2}-1)/(\sqrt{2}-1)=1$ and $U_{v^2}'=(\sqrt{2}-1)\cdot (\sqrt{2}-1)=3-2\sqrt{2}$ which imply the total utility of v is $U'_{v}=4-2\sqrt{2}$ and the incentive ratio of v is at least $\sqrt{2}$. Thus the incentive ratio of BD Mechanism on complete graphs is $\zeta \ge \sqrt{2}$.    $\square$

It’s worth noting that the above example for lower bound can be generalized to any complete graph $K_n$ with vertex weights $w_{v}=2\sqrt{2}-2$, $w_{u^1}=1$ and $w_{u^2}=\cdots =w_{u^{n-1}}=\frac{3-2\sqrt{2}}{n-2}$. The bottleneck decomposition of $K_n$ is $\{(B_1,C_1)\}$ with $B_1=C_1=\{v,u^1,\cdots , u^{n-1}\}$ and $\alpha _1=1$. So $U_{v}=2\sqrt{2}-2$. Now v plays the vertex splitting strategy to replace itself by $n-1$ duplicated nodes $v^{j}$, $j=1,\cdots ,n-1$, such that each $v^{j}$ is adjacent to neighbor $u^j$. Furthermore, v assigns its weight to each node as $w_{v^1}=\sqrt{2}-1$ and $w_{v^2}=\cdots =w_{v^{n-1}}=\frac{\sqrt{2}-1}{n-2}$. Then the bottleneck decomposition changes to be $\{(B_1',C_1')\}$, where $B_1'=\{u^1,v^2,\cdots ,v^{n-1}\}$, $C_1'=\{v^1,u^2,\cdots ,u^{n-1}\}$ and $\alpha _1'=\sqrt{2}-1$. So $U'_{v^1}=(\sqrt{2}-1)/(\sqrt{2}-1)=1$ and $U_{v^j}'=\frac{\sqrt{2}-1}{n-2}\cdot (\sqrt{2}-1)=\frac{3-2\sqrt{2}}{n-2}$, $j=2,\cdots ,n-1$. The total utility of v is $U'_{v}=U'_{v^1}+\sum _{j=2}^{n-1}U'_{v^j}=4-2\sqrt{2}=\sqrt{2}U_{v}$.

3.2 Upper Bound of Incentive Ratio on $K_n$

The main task of this subsection is to show the upper bound of $\sqrt{2}$. To compute the upper bound of incentive ratio on complete graph $K_n$, it is necessary to analyze the optimal strategy for the strategic vertex v, by which v can obtain the maximal utility gain.

Theorem 3.3

If the network of resource sharing system is a complete graph, then the incentive ratio of BD Mechanism for the sybil attack strategy is at most $\sqrt{2}$, i.e. $\zeta \le \sqrt{2}$.

Proof

As we know, the strategic vertex v may be a B-class vertex or C-class vertex in G. But if $v\in B_1$ with $\alpha _1=1$, it can be viewed as a C-class vertex since $B_1=C_1=V$. Thus there are two disjoint cases that $v\in B_1$ with $\alpha _1<1$ and $v\in C_1$. From the characterization of bottleneck decomposition $\mathcal {B}$ in Lemma 3.1, we note that if $v\in B_1$ with $\alpha _1<1$, then other $n-1$ vertices are all in $C_1$ and upload all of their resource to v. In other words, vertex v obtains all possible resource in system, which achieves the maximum. Under this case, such a vertex v has no any incentive to play strategically and its optimal strategy is to keep intact. Hence, the incentive ratio is 1. For the second case that $v\in C_1$, it’s obvious that $U_v=w_v/\alpha _1\ge w_v$. If $\mathcal {B}'$ only contains one bottleneck pair $(B'_1,C'_1)$ with $\alpha _1'=1$, then $U_v'=\sum _{j=1}^{n-1}U'_{v^j}=\sum _{j=1}^{n-1}w_{v^j}=w_v\le U_v,$ which implies v’s incentive ratio is 1 too. Until now there is only one situation left that $v\in C_1$ and $\mathcal {B}'$ contains at least one bottleneck pair whose $\alpha$-ratio is less than 1, meaning $\alpha _1'<1$. Following lemma characterizes the structure of $\mathcal {B}'$ when the strategic agent v plays the optimal strategy.

Fig. 3.

The bottleneck decomposition $\mathcal {B}'$ when v adopts optimal strategy, where the blue or white vertices represent $B'$-class or $C'$-class vertices respectively. (Color figure online)

Lemma 3.3

Suppose that the network of resource sharing system is a complete graph and the strategic vertex v is in C-class. When v gains the maximal utility by adopting the optimal strategy, the bottleneck decomposition $\mathcal {B}'$ in $G'$ must has the form as $\mathcal {B}'=\{(B_1',C_1')\}$ with $B_1'=\{u^j,\Lambda (v)-v^j\}$ and $C_1'=\{v^j,\Gamma (v)-u^j\}$, $\exists j\in \{1,2,\cdots ,n-1\}$ as shown in Fig. 3.

Proof

Based on the previous analysis, it is enough to discuss the case that $v\in C_1$ and $\mathcal {B}'$ contains at least one pair whose $\alpha$-ratio is less than 1, which implies $\alpha _1'<1$. So the structure of $\mathcal {B}'$ must be case 2 or 3 in Lemma 3.2. If $\mathcal {B}'$ has the structure as case 2, then this lemma holds. Now we turn to discuss case 3 and try to show the impossibility of case 3 when v plays optimally.

If $\mathcal {B}'$ has the structure as case 3-(a) and 3-(b), then each duplicated node $v^l$, $l=1,\cdots ,n-1$, is in $B'$-class (for case 3-(b) some $v^l$ may be in $B_{k'}'=C_{k'}'$ with $\alpha _{k'}'=1$) and $U'_{v^l}\le w_{v^l}$. Therefore,

$$\begin{aligned} U'_v=\sum _{l=1}^{n-1}U'_{v^l}\le \sum _{l=1}^{n-1}w_{v^l}=w_v\le U_v. \end{aligned}$$

The last inequality is from the condition that $v\in C_1$. So v has no incentive to manipulate BD mechanism and its incentive ratio is 1.

If $\mathcal {B}'$ has the structure as case 3-(c), without loss of generality, we assume there are two pairs in $\mathcal {B}'$, which are $B_1'=\{v^h\}$, $C_1'=\{u^h\}$ and $B_2'=\{u^j,\Lambda (v)-\{v^j,v^h\}\}$, $C_2'=\{v^j,\Gamma (v)-\{u^j,u^h\}\}$. Thus, $U'_{v^h}=w_{v^h}\cdot \alpha _1'=w_{u^h}$, $U'_{v^j}=w_{v^j}/\alpha _2'$ and $U'_{v^l}=w_{v^l}\cdot \alpha _2'$, for each $l\ne j,h$. In addition the total utility of v in $G'$ is

$$\begin{aligned} U_v'=w_{u^h}+\frac{w_{v^j}}{\alpha _2'}+(w_v-w_{v^h}-w_{v^j})\cdot \alpha _2'. \end{aligned}$$

Let us consider a new weight assignment $(\widehat{w}_{v^1},\widehat{w}_{v^2},\cdots ,\widehat{w}_{v^{n-1}})$ of $w_v$ as

$$\begin{aligned} \widehat{w}_{v^l}=\left\{ \begin{array}{ll} w_{v^l}-\delta ,&{}~l=h;\\ w_{v^l}+\frac{\alpha _2'}{1+\alpha _2'}\delta ,&{}~l=j;\\ w_{v^l}+\frac{1}{(1+\alpha _2')(n-3)}\delta ,&{}~l\ne h,j; \end{array} \right. \end{aligned}$$

(1)

where $\delta$ is a arbitrarily small and positive number. Obviously, $\sum _{l=1}^{n-1}\widehat{w}_{v^l}=w_v$. Since $\alpha _1'<\alpha _2'$, there must be a small and positive number $\delta$ such that the bottleneck decomposition $\mathcal {B}'$ keeps unchanged for the new weight assignment (1). So the new utility of $v^h$ is still $\widehat{U}_{v^h}'=w_{u^h}=U'_{v^h}$ and the fact $\alpha _2'=\frac{w_{v^j}+\sum _{l\ne h,j}w_{u^h}}{w_{u^j}+\sum _{l\ne h,j}w_{v^h}}$ makes

$$\begin{aligned} \widehat{\alpha }_2'=\frac{w_{v^j}+\sum _{l\ne h,j}w_{u^h}+ \frac{\alpha _2'}{1+\alpha _2'}\delta }{w_{u^j}+\sum _{l\ne h,j}w_{v^h}+ \frac{1}{1+\alpha _2'}\delta }=\alpha _2' \end{aligned}$$

Therefore,

$$\begin{aligned}&\widehat{U}_{v^j}'=\frac{\widehat{w}_{v^j}}{\alpha _2'}=\frac{w_{v^j}+\frac{\alpha _2'}{1+\alpha _2'}\delta }{\alpha _2'} =U_{v^j}'+\frac{1}{1+\alpha _2'}\delta ;\\&\sum _{l\ne j,h}\widehat{U}_{v^l}'=(w_v-w_{v^h}-w_{v^j}+\frac{1}{1+\alpha _2'}\delta )\cdot \alpha _2'= \sum _{l\ne j,h}U_{v^l}'+\frac{\alpha _2'}{1+\alpha _2'}\delta , \end{aligned}$$

which implies $\widehat{U}_{v}'=U_v'+\delta >U_v'$. Vertex v continues to adjust its weight assignment as (1) by increasing $\delta$ until $\widehat{\alpha }_1'=\widehat{\alpha }_2'=\alpha _2'$. At this time, the two bottleneck pairs should be combined together to keep the maximal size and have the form as $B_1'=\{u^j,\Lambda (v)-v^j\}$ and $C_1'=\{v^j,\Gamma (v)-u^j\}$. Furthermore, by the proof of Lemma 3.2, we know once one of $u^j\in \Gamma (v)$ is in $B_1'$ and $\alpha _1'<1$, then the bottleneck decomposition $\mathcal {B}'$ must have the structure of case 2 in Lemma 3.2. This completes the proof.    $\square$

Now we are ready to provide the proof of Theorem 3.3. Here we only discuss the case that $v\in C_1$ in G and $\mathcal {B}'$ contains at least one bottleneck pair whose $\alpha$-ratio is less than 1. Given any weight profile $\mathrm {\mathbf {w}}=(w_v,w_{u^1},\cdots ,w_{u^{n-1}})$. From Lemma 3.3, if vertex v plays the optimal strategy, then the bottleneck decomposition $\mathcal {B}'=\{(B_1',C_1')\}$ has the structure of $B_1'=\{u^j,\Lambda (v)-v^j\}$ and $C_1'=\{v^j,\Gamma (v)-u^j\}$, $j\in \{1,2,\cdots ,n-1\}$. So

$$\begin{aligned} \alpha _1'=\frac{w_{v^j}+\sum _{l\ne j}w_{u^l}}{w_{u^j}+(w_v-w_{v^j})}~\text {and}\quad U_v'=(w_v-w_{v^j})\cdot \alpha _1'+w_{v^j}\frac{1}{\alpha _1'}. \end{aligned}$$

Since the weight profile $\mathrm {\mathbf {w}}=(w_v,w_{u^1},\cdots ,w_{u^{n-1}})$ is given in advance, $U_v'$ and $\alpha _1'$ can be viewed as the functions of $w_{v^j}$. To simplify the notations, we denote $w_v=a$, $w_{u^j}=b$, $\sum _{l\ne j}w_{u^l}=c$ and the decision variable $w_{v^j}=x$, as shown in Fig. 3. Using these notations, the bottleneck decomposition $\mathcal {B}=\{(B_1,C_1)\}$ of $K_n$ may be: (1) $B_1=\{u^j\}$ and $C_1=V-\{u^j\}$ with $\alpha _1=\frac{a+c}{b}$ when $b>a+c$; or (2) $B_1=C_1=V$ with $\alpha _1=1$ when $b\le a+c$. Thus

$$\begin{aligned} U_v=\left\{ \begin{array}{lll} a\cdot \frac{1}{\alpha _1}=\frac{a b}{a+c},&{}\,\,\,\,\,\,\,\,\text {if}&{} b>a+c;\\ a,&{}\,\,\,\,\,\, \text { if}&{} b\le a+c. \end{array} \right. \end{aligned}$$

(2)

For the strategic vertex v, it tries to maximize the following maximization problem,

$$\begin{aligned}&\max ~\quad U'_{v}(x)/U_{v}\nonumber \\&\begin{array}{llc} s.t~&{} \quad \frac{c}{a-x}\ge \frac{c+x}{b+a-x}&{}\qquad (\star )\\ &{} \quad b + a-x > c +x&{}\qquad (\star \star )\\ &{} \quad 0\le x\le a&{}\qquad (\star \star \star ) \end{array} \end{aligned}$$

(3)

Constraint $(\star )$ is from characterization that the bottleneck decomposition $\mathcal {B}'$ shall be $B_1'=\{u^j,\Lambda (v)-v^j\}$ and $C_1'=\{v^j,\Gamma (v)-u^j\}$ under the optimal strategy, and constraint $(\star \star )$ is right since $\alpha _1'(x)=\frac{c+x}{b+a-x}<1$. Combining constraints $(\star \star )$ and $(\star \star \star )$, the feasible solution $x\le \min \{a,\frac{a+b-c}{2}\}.$ In addition,

$$\begin{aligned} U_v'(x)=x\cdot \frac{b+a-x}{c+x}+(a-x)\cdot \frac{c+x}{a+b-x} =(a+b+c)\left[ \frac{x}{c+x}+\frac{a-x}{a+b-x}\right] -a, \end{aligned}$$

and the derivation of $U'_v(x)$ is

$$\begin{aligned} \frac{dU_v'(x)}{dx}=(a+b+c)\left[ \frac{c}{(c+x)^2}-\frac{b}{(a+b-x)^2}\right] . \end{aligned}$$

It is not hard to see function $U_v'(x)$ has a unique maximum point $x^*=\frac{\sqrt{c}(a+b)-\sqrt{b}c}{\sqrt{b}+\sqrt{c}}$ and $U_v'(x)$ increases when $x\le x^*$ and decreases when $x\ge x^*$.

Let us consider four intervals where the parameter b is in: [0, c], $[c,a+c]$,$[a+c,\frac{(a+c)^2}{c}]$ and $[\frac{(a+c)^2}{c},+\infty ]$. We can compute that $\frac{a+b-c}{2}\le x^*<a$ when $b\in [0,c]$; $x^*\le \frac{a+b-c}{2}\le a$ when $b\in [c,a+c]$; $x^*\le a\le \frac{a+b-c}{2}$ when $b\in [a+c,\frac{(a+c)^2}{c}]$ and $a\le x^*<\frac{a+b-c}{2}$ when $b\in [\frac{(a+c)^2}{c},+\infty ]$. In the following we shall prove that the ratio $U_v'(x)/U_v$ is no more than $\sqrt{2}$ in each interval.

$\bullet$ $b\in [0,c]$. So $U_v=a$ since $b\le c\le a+c$ by (2). On the other hand, we get $x^*\ge \frac{a+b-c}{2}$ and $a\ge \frac{a+b-c}{2}$. Such two inequalities means the feasible solution $x\le \min \{a,\frac{a+b-c}{2}\}=\frac{a+b-c}{2}\le x^*$. So the monotonically increasing property of $U'_v(x)$ when $x\le x^*$ promises

$$\begin{aligned} U_v'(x)\le U_v'(\frac{a+b-c}{2})=a=U_v. \end{aligned}$$

$\bullet$ $b\in [c,a+c]$. On one hand, condition $b\le a+c$ promises $U_v=a$ by (2) and $a\ge \frac{a+b-c}{2}$. On the other hand, $x^*\le \frac{a+b-c}{2}=\min \{a,\frac{a+b-c}{2}\}$. Therefore v can get its maximal utility when $x=x^*$, and

$$\begin{aligned} U_v'(x^*)=x^*\cdot \frac{b+a-x^*}{c+x^*}+(a-x^*)\cdot \frac{c+x^*}{a+b-x^*}=a+(\sqrt{b}-\sqrt{c})^2. \end{aligned}$$

Then the ratio

$$\begin{aligned} \frac{U_v'(x^*)}{U_v}=\frac{a+(\sqrt{b}-\sqrt{c})^2}{a}\le \frac{a+(\sqrt{a+c}-\sqrt{c})^2}{a}=\frac{2\sqrt{a+c}(\sqrt{a+c}-\sqrt{c})}{a}=\frac{2}{\sqrt{\frac{1}{1+\frac{a}{c}}}+1},\nonumber \\ \end{aligned}$$

(4)

where the inequality is from condition $b\le a+c$. Of course, if $U'_v(x)$ achieves its maximum at $x=x^*$, then $x^*=\frac{\sqrt{c}(a+b)-c\sqrt{b}}{\sqrt{b}+\sqrt{c}}$ must satisfy constraint ($\star$) additionally, i.e., $\frac{c}{a-x^*}\ge \frac{c+x^*}{b+a-x^*}$. So

$$\begin{aligned} bc\ge x^*(a-x^*)\Rightarrow & {} bc\ge \frac{[\sqrt{b}(c+a)-b\sqrt{c}][\sqrt{c}(b+a)-c\sqrt{b}]}{(\sqrt{b}+\sqrt{c})^2}\\\Longleftrightarrow & {} bc(b+c)+2bc\sqrt{bc} \ge [2bc+a(a+b+c)]\sqrt{bc}-2abc-bc(b+c)\\\Longleftrightarrow & {} 2bc(a+b+c) \ge a(a+b+c)\sqrt{bc}\Longleftrightarrow 2\sqrt{bc} \ge a \end{aligned}$$

Combining the condition $b\le a+c$, we have $a\le 2\sqrt{(a+c)c}$, which implies

$$\begin{aligned} a^2\le 4(a+c)c\Rightarrow \left( \frac{a}{c}\right) ^2-4\left( \frac{a}{c}\right) -4\le 0\Rightarrow 0<\frac{a}{c}\le 2+2\sqrt{2}. \end{aligned}$$

(5)

Continue the computation of the upper bound in (4),

$$\begin{aligned} \frac{U_v'(x^*)}{U_v}\le \frac{2}{\sqrt{\frac{1}{1+\frac{a}{c}}}+1}\le \frac{2}{\sqrt{\frac{1}{1+(2+\sqrt{2})}}+1}=\sqrt{2}. \end{aligned}$$

$\bullet$ $b\in [a+c,\frac{(a+c)^2}{c}]$. Under this case, we have $U_v=\frac{ab}{a+c}$ by (2), inequalities $a\le \frac{a+b-c}{2}$ and $x^*\le a=\min \{a,\frac{a+b-c}{2}\}$. So the utility $U_v'(x)$ must reach the maximum $U'_v(x^*)=a+(\sqrt{b}-\sqrt{c})^2$ at $x=x^*$ and the ratio

$$\begin{aligned} \frac{U_v'(x^*)}{U_v}=\frac{a+(\sqrt{b}-\sqrt{c})^2}{ab/(a+c)}\le \frac{a+(\sqrt{a+c}-\sqrt{c})^2}{a}=\frac{2}{\sqrt{\frac{1}{1+\frac{a}{c}}}+1}. \end{aligned}$$

Since the above ratio decreases with b, the inequality is from the condition that $b\ge a+c$. Applying the same analysis for case $b\in [c,a+c]$, we also can get the upper bound of $\sqrt{2}$.

$\bullet$ $b\in [\frac{(a+c)^2}{c},+\infty ]$. Clearly, $U_v=\frac{ab}{a+c}$ and $a\le \frac{a+b-c}{2}$, $x^*\ge a$. Hence all feasible solutions $x\le \min \{a,\frac{a+b-c}{2}\}=a\le x^*$. By the monotonically increasing property of $U_v'(x)$ when $x\le x^*$, we have

$$\begin{aligned} U_v'(x)\le U_v'(a)=\frac{ab}{a+c}=U_v, \end{aligned}$$

which implies the incentive ratio of v is no more than 1.

This completes Theorem 3.3.    $\square$

4 Observations and Conclusions

In this paper, we discuss the effect of sybil attack, a possible strategic manipulation of agents, on the resource sharing game over P2P network. Resource sharing can be viewed as a pure exchange economy model, for which pricing and allocation are decided by market equilibrium. As a common strategic behavior in peer-to-peer system, sybil attack is easier to execute and is difficult to detect. This motivates us to study the incentives of agents by taking the sybil attack strategy under the market equilibrium solution and quantitatively measuring the maximal magnitude of agent advantage gained from sybil attack in terms of the incentive ratio.

From the perspective of sharing economy, the ideal state of resource sharing game to consider is where all participants are fully connected. Therefore, it motivates us to focus on the complete graphs. We prove that the incentive ratio of the market equilibrium solution under the sybil attack strategy is exactly $\sqrt{2}$ on complete graphs.

Fig. 4.

The numerical experiment results on random graphs.

Through the study of incentive ratio on complete graphs, we may suspect that the density of edges in a graph may decrease the incentive ratio of the resource sharing problem from that of 2 for tree to $\sqrt{2}$ gradually. There then opens up the issue whether the incentive ratio of market equilibrium for resource sharing on random networks decreases as the probability an edge is selected into the network. Therefore, we look into a series of random graphs, in each of which any two vertices are connected by an edge with probability p independent from every other edge. In our numerical experiments, we construct 100 graphs of 10 vertices for each probability $p\in \{0.1,0.2,\cdots ,0.9\}$, and the weight of each vertex is no more than 100. Then we simulate the sybil attack strategy and compute the maximal incentive ratio among all 100 graphs for each probability p, as shown in Fig. 4. From the results in Fig. 4, we can see that the incentive ratio is no more than 2. Furthermore we have the intuition that, with the increase of p, implying that the underlying network contains more and more edges, the incentive ratio decreases. From the current results that the incentive ratio is 2 on trees and is $\sqrt{2}$ on complete graphs, such an intuition does make sense.

Despite of the randomized results, we are still interested in the incentive ratio in general settings. A key challenge is to find out a proper bound for the incentive ratio of general graphs, which we conjecture to be two.