Advanced
A Game theoretic analysis of public goods allocation in p2p networks
A Game theoretic analysis of public goods allocation in p2p networks
KSII Transactions on Internet and Information Systems (TIIS). 2015. Aug, 9(8): 2854-2874
Copyright © 2015, Korean Society For Internet Information
  • Received : February 24, 2015
  • Accepted : June 21, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Qingfeng Zhang
Sheng Wang
Dan Liao

Abstract
This paper presents a game theoretic approach to analyze the public goods (PGs) allocation in peer-to-peer (p2p) networks. In order to reduce the free-riders and promote the cooperation among peers, we propose an incentive mechanism with cooperation-based game theory. In this paper, we regarded the contributed resources by cooperators as public goods (PGs). We also build the PGs allocation in P2P networks to be the optimization problem, and the optimal solution of PGs allocation satisfies the Bowen-Lindahl-Samuelson equilibrium. Firstly, based on the subscriber mechanism, we analyze the feasibility and prove the validity, which can achieve Nash equilibrium. However, this strategy cannot meet to Bowen-Lindahl-Samuelson equilibrium as the free-riders do not pay with their private goods for consuming the PGs. Secondly, based on the Walker mechanism, we analyze the feasibility and prove the validity for the same allocation problem, which meets to Bowen-Lindahl-Samuelson equilibrium and achieves Pareto efficiency within cooperative game. Simulations show that the proposed walker mechanism can significantly improve the network performance of throughout, and effectively alleviate free-riding problem in P2P networks.
Keywords
1. Introduction
I n recent years, a large number of users use p2p networks, which have many advantages such as scalability, resilience, and effectiveness in coping with dynamics and heterogeneity. However most of the p2p systems face the problem of free-riding. The free-riders are selfish peers who only use the other peers’ resources without contributing anything, which has greatly influence on the efficiency and fairness of p2p networks. Investigation shows that: a measurement study of the Gnutella file sharing network [1] found that approximately 70% of peers provided no files and that approximately 37% of the total files are provided by the top 1% of the peers. Similar observations have been found in studies of Napster and Gnutella networks. A different study presented in [2] found that free-riders have increased to 85% of all Gnutella users. The free-riders without contributing anything because of it must be consuming much of their bandwidth, storage, computing and other hard resources; which have greatly influence on their security issues and quality of service ( QoS ).
The transfer of content incurs costs to both uploading and downloading peers but benefiting only downloading peers in p2p networks. So, Peers tend to download excessively as a common problem in p2p networks, if uploading peers incurs costs to other peers but without directly benefit, peers tend to upload too little or they will become free-riders. This will make the p2p networks collapse in a short time. The incentive mechanism states that peers can get benefit for their contributions. Therefore, healthy p2p networks should have some mechanisms that provide appropriate incentives to encourage peers contribute their resources.
We regard the cooperators contributions (file resources, storage resources, bandwidth resources, computing resources etc.) as the public goods (PGs). This paper presents an incentive mechanism of the PGs allocation in p2p networks using game theory which can overcome the free-riding problem. there are three advantages such as: 1)The number of PGs reflect the degree of cooperation peers’ selflessness and also reflect the number of selfless peers contributing resources to the p2p networks; 2) The PGs have Non-exclusiveness, which means all competing peers can fairly consume the PGs. This can improve the throughput of the p2p networks. It is noted that in our proposed mechanism, new peers who join the p2p networks for a short time also has a relative fairness chance PGs resource consuming; 3) There are competitions in the PGs consumption, so, the competing peers need to pay with their private goods for consuming the PGs according to their requirements and Marginal Rate of Transformation ( MRT ), for the providers (cooperators) they have the same resources contribution capacities. If they want to increase one of their public goods contributions, they must be inducing other public goods contributions.
This paper analyzes and proves the PGs allocation’s feasibility and validity within two basic model games: non-cooperative game based subscribe mechanism and cooperative game based walker mechanism respectively. The results show that both of them are feasibility for the PGs allocation. However, the validity of the PGs allocation depends on the model of game: non-cooperative game based subscribe mechanism is in-validity and cooperative game based walker mechanism is validity. The mechanisms proposed in this paper can achieve the validity of PGs resource allocation in P2P networks but with very simple models designed.
The rest of this paper is organized as follows. In Section 2 we discuss related work about various incentive schemes. Section 3, we build the basic model that describes a scenario of the PGs allocation, and use Lagrange multipliers achieved the solution of the optimal PGs’ allocation. This solution satisfies the Bowen-Lindahl-Samuelson equilibrium. Section 4, we analyze the feasibility and demonstrate the validity of non-cooperative game based subscribe mechanism. Section 5, we analyze the feasibility and discuss the validity of cooperative game based walker mechanism. Section 6, numerical results illustrate some properties of the PGs allocation. Finally Section7 is the conclusion of the paper.
2. Related Work
To overcome the free-ridings is critical to the performance, fairness and robustness of p2p networks. Various incentive schemes have been proposed in recent years to alleviate or overcome the free-riding problem (e.g., [2 , 3] ). According to the different resource allocation schemes, we categorize these researches into five types:
1).Cooperative group scheme (e.g., [4 , 5 , 6] ). In this scheme, peers can improve their downloading performance by sharing their spare capacities in the same collaborative group. There are many peers join and leave the p2p networks in a short time, so, the main challenge of these schemes is forming and sustaining the collaborative groups in unstructured networks.
2).Pricing scheme (e.g., [7 , 8] ).This scheme uses virtual currency or credit to reward the uploading peers and charge the downloading peers. Since they need an accounting infrastructure to record all peers’ transactions which contains a significant number of items, the pricing schemes are often regarded impractical.
3).Monetary payment scheme (e.g., [9 , 10] ).This scheme requires the service consumers to pay the service providers with real money. Almost research remains under the assumption that monetary exchanges are possible. Monetary schemes have many and flexible economic foundations but suffer the drawback of impractical as they still need an infrastructure for accounting and analyzing the micropayments between peers like pricing schemes.
4).Differential service scheme (e.g., [11 , 12 , 18] ).This scheme treats peers differentially according to their ranking. Since a good ranking peer can provide a better server quality to other peers, this good ranking peer will receive more resources from the source peer when receiving services. These schemes encourage peers to contribute their resources in order to obtain and maintain a good ranking. But, these schemes need large communication overheads to determine and broadcast the ranking of peers. The ranking of a peer is determined by its histories behavior which is observed by other peers, and the ranking in terms of trust or reputation is updated and broadcasted by other peers or the networks. So, there are many literature have studied the peers’ reputation or trust.
5).Reciprocity-Based Scheme (e.g., [13 , 14] ). This Scheme is based on Direct-reciprocity or Indirect- reciprocity. In Direct-reciprocity scheme, user i decides how to serve user j according to the service that j has provided to i in the present or past. In contrast, in indirect-reciprocity scheme, the decision of user i also considers the services that j has provided to other peers in the systems. Direct-reciprocity scheme often employ a tit-for-tat incentive mechanism to encourage cooperative behavior among a set of nodes that exchanges large files. Indirect-reciprocity scheme is more scalable than Direct-reciprocity scheme, because peers can obtain resources easily, and more peers are willing to join the networks. In Indirect-reciprocity scheme, there are some dishonest and malicious peers in p2p networks, thus the Indirect-reciprocity scheme must confront trust issues, which does not arise in Direct-reciprocity scheme.
introducing cooperation from the strategic peers. So, Game theory is the most pervasive tool in study of incentive mechanisms, which offers a useful framework to model multiuser interaction and has been applied to analyze the behavior of peers in p2p networks (e.g., [11 , 12] ). Incentive schemes have been investigated using both non-cooperative game theory and cooperative game theory. The authors of [11] use Game Theory to study differential service-based incentive schemes to improve the system performance. The authors of [12] propose a protocol to obtain Nash equilibrium efficiently, dynamically and guarantee the Pareto-optimal resource allocation. The authors of [15] build a model and obtain two results in two different scenarios: the non-cooperative result without any incentive scheme and the cooperative result with some incentive schemes. The authors of [16] propose an incentive mechanism for cooperation based game theory to overcome free-riding problem. The authors of [17 , 18] apply the mechanism-design approach to build optimal incentive-compatible differential service schemes to encourage peers to cooperate. The authors of [19] use static game models to establish pricing schemes which can be easily incorporated. The authors of [17 , 20] use an evolutionary game model to examine the performance of a differential service scheme based on peer reciprocation. The authors of [16] use both repeated game and mechanism design approaches to propose cheat-proof and attack-resistant differential service schemes. Especially, the problems are related to resource allocation use game theory [16 , 17 , 18] . The authors of [16 , 18] define a utility function which captures the best wish of the source peer to serve the competing peers according to peers’ ranking. The utility function is convex, and belongs to Harsanyi-type social welfare functions. It is devised to obtain a unique optimal resource allocation that achieves max-min fairness, and it also can achieved admission control. The authors of [12] propose a protocol in which the competing nodes can interact with the information providing node to achieve Nash equilibrium. The authors of [17 , 20 , 21 , 22 , 23] investigate the robustness, efficiency and fairness of their proposed resource allocation schemes. The authors of [24] present an evolutionary framework to simulate and analyze the outcomes of the PGs provisioning under asymmetric information. Only a few recent works addressed the PGs allocation in p2p networks. The authors of [25] present dynamic optimization of multi attributes resource allocation. The authors of [26] use network coding optimality delays and incentives approaches to propose distributed resource allocation for P2P multicast networks. The authors of [27] use resource pricing approaches investigate a resource allocation mechanism in peer-to-peer networks. The authors of [28] based on the P2P-assisted to investigate efficient and incentive-compatible resource allocation mechanism in content delivery systems. The authors of [29] based efficient content delivery propose indirect reciprocity reputation in BT-like systems. The authors of [30] based on social relation investigate a resource allocation algorithm for Video Streaming Services over P2P network. The authors of [31] based on P2P traffic planning to research on dynamic allocation of network resources. The authors of [32] survey on grid resource allocation mechanisms. The authors of [33] use a Stackelberg Game approach to present incentive Mechanism design for heterogeneous Peer-to-Peer networks. The authors of [34] use a game theoretic stochastic learning to solve the distributed channel selection for interference mitigation in dynamic environment. The authors of [35] also use a game theoretic approach investigate an optimal power allocation and user scheduling in multicell networks which based on station cooperation. In this paper, we propose two resource allocation models of PGs and also analyze the feasibility, proof the validity. The difference between the proposed scheme and the other existing schemes: We regard the altruistic peers’ resource sharing as PGs and allocate to the competing peers, which give a fairness chance for all competing peers to obtain their sharing resources. And these resources reflect the degree of cooperation peers’ selflessness. These resource allocation models can increase the total PGs to improve the quality of service for the competing peers, increase the size of the p2p network, maintain the stability of the p2p network and overcome the free-riders. If all competing peers can obtain PGs by pay with their private goods, which can attract more peers join the networks.
3. System Model
In this paper, we present an incentive scheme of the PGs allocation in p2p networks using game theory. P2P networks are consisting of a set of cooperators and a set of free-riders, and the network resources which contain the PGs and the peers’ private goods. Fig. 1 shows the resources of the p2p networks. The cooperators contribute some of their resources as the PGs that incur sharing costs, while all of the peers who consume the PGs must pay with their private goods according to their consumption to maintain the networks’ durative and robustness.
PPT Slide
Lager Image
the resources of the p2p networks
In this paper, we assume that there are n peers in p2p networks; each peer has the same Marginal Rate of Transformation ( MRT = μ ) and Marginal Rate of Substitution ( MRS ), which means for the consumers, if they want to obtain the public goods, they must be pay with their private goods. Assume peer i has resources consisting of the public goods ( θi ) and the private goods (Ω i ); the resource can contribute si , 0≤ si θi ; and the PGs requirement is ri , ri ≥0 ; the peer should pay with private goods for consuming the PGs is pi , 0≤ pi ≤Ω i . Unit of resources sharing cost of all peers is α = ( α 1 , α 2 , ... αn in this paper, we assume that αi =1 for all peers. If the sum of all peers’ requirements
PPT Slide
Lager Image
is less than the total PGs, which means all peer requirements can be accommodated with the PGs, and each peer just pay with their private goods according to their requirements, there is no competition for all peers under this condition. Otherwise, the p2p networks must allocate the PGs to the competing peers. This paper mainly discussing how to allocate the PGs for the competing peers to achieve Nash equilibrium and Pareto efficiency.
In this paper, we propose a simple and efficient model to allocate the PGs; we also theoretical solve this model with a mature technology. With this theoretical solution, we can achieve the optimally resource allocation in P2P networks.
In competing game, we assume that the total of all peers’ payments must be no less than the PGs sharing costs. In this paper, all peers should pay with their private goods if they are consuming the PGs. let S denote the PGs resource capacity for peers’ consumption, which also determines the costs of the PGs as C , where in non-corporative game based subscribe mechanism, as
PPT Slide
Lager Image
let SS denote that the PGs resource capacity SS is the summation of all peers’ sharing resource or the competing peers’ requirements. So,
PPT Slide
Lager Image
while in corporative game based walker mechanism, let Sw denote the PGs resource sharing capacity is the average of all peers’ requirements, so,
PPT Slide
Lager Image
and peers’ payment is
PPT Slide
Lager Image
Thus, in order to satisfy that all payments from peers should be no less than the total costs, the equation of
PPT Slide
Lager Image
is integrated into the model we proposed as a constraint.
We suppose the utility function of all peers is defined by a strictly concave and differentiable function Ui ( S , pi ), which is increasing in S and decreasing in pi .
Let us consider the following form of utility function which satisfies the above assumption:
PPT Slide
Lager Image
where 0< pi ≤Ω i , that means the competing peers is cooperative peer, who is willing to pays with his private goods for consuming the PGs; where pi =0, that means the competing peer is the free-rider, who regard the PGs as his private goods.
The peers’ payment is the price or his other private goods (file resources, storage resources, bandwidth resources, computing resources etc.). If the payment is the price [36] ; the all payments from the competing peers should be no less than the total sharing costs of the providers. If the payment is private goods, the all payments should be subject to the following equation
PPT Slide
Lager Image
The utility function simply shows that the system prefers to allocate the PGs to the competing peers to maximize the system total utility (which is the system total satisfaction in our case). We build a model of the PGs allocation in P2P networks as the optimization problem.
  • SYSTEM
PPT Slide
Lager Image
  • Subject to:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
The given parameter λi denotes of the degree of the peer’s satisfaction in the utility function, this parameter takes into account peer’s requirement and payment. The constraints (3) ensure that the PGs resource capacity for peers’ consumptions is within the peers’ total consumption. The constraints (4) ensure that the peer’s consumption is no larger than its payoff capacity. The PGs resource capacity for peers’ consumption is positive, which is guaranteed by equation (5).
Since the utility function is a strictly concave and differentiable function, and if we select appropriate parameter λi , a given valid PGs allocation must be the optimal solution of the problem. It is also one of Nash equilibriums of the problem that can achieve Pareto Optimality.
Proposition 1: Any PGs allocation is the solution of the problem, and it is a valid allocation. This allocation is also the Pareto Optimality if the constraint (3) holds.
Proof: Suppose that one of the PGs allocation ( S * ,
PPT Slide
Lager Image
) which is the solution of the problem, thus S * ≥0; 0≤
PPT Slide
Lager Image
≤Ω i ; (i=1,2,3…n)
Let L ( S , pi , β ) denotes the Lagrangian function where β >0 and 0≤ pi ≤Ω i , S ≥0; β is the Lagrange multiplier associated with constraint (3) .Then
PPT Slide
Lager Image
The first-order conditions are
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
According (7) and (8), we can obtain another equation (10) without β
PPT Slide
Lager Image
We note that this allocation is an efficient PGs allocation and it is also satisfy the Bowen-Lindahl-Samuelson condition in equation (11).
PPT Slide
Lager Image
That is to say, the sum of all competing peers’ MRS equals to the MRT = μ .
Bowen-Lindahl-Samuelson-equilibrium [37] means that if every peer in accordance with the marginal benefit of public goods or services to pay with his private goods (price) of the public goods or service cost in P2P networks. And the public goods or service provide can reach the optimal level of effectiveness.
In short, the equilibrium refers to peers bargaining between the consuming of the public goods and the providers sharing costs allocation among the competing peers. And it can reach the balance of the bargaining.
The equilibrium solution is the constraint condition of zero in the normal profit, so that the public goods pricing is depend on the demand elasticity of the competing peers. The different price depends on different evaluation of each competing peer for the public goods respectively.
According to the previous assumption, there are different PGs resource capacities for peers’ consumptions, which incur different sharing costs. In this paper, we discuss two scenarios of SS and Sw , which represent the non-cooperative game based subscribe mechanism and the cooperative game based walker mechanism respectively.
4. Subscribe Mechanism
In this section, we propose a non-cooperative game based Subscribe mechanism for PGs allocation; the competing peers should pay with their private goods for consuming the PGs according to the amount of consumptions and MRT . Thus
PPT Slide
Lager Image
- 4.1 Feasibility analyze
In non-cooperative game, each peer pays with private goods pi = εi for consuming the PGs without taking into account the other peers’ strategies. Therefore, these peers pay with their private goods only according to their requirements or consumptions. These peers are regarded as rational peers. This pay-as-you-need strategy is feasible for the p2p networks; however, there are some peers do not pay with their private goods when they consume PGs, these peers are regarded as free-riders and this free-riding behavior is in-feasibility for the p2p networks.
- 4.2 Validity prove
According to the previous assumption that MRT = μ , and all competing peers should pay with their private goods pi = εi for consuming the PGs within non-cooperative game. Thus
PPT Slide
Lager Image
And
PPT Slide
Lager Image
We define this game as a strategy game, peer i ’s strategies space as σi = [0,Ω i ], the payoff function as follow
PPT Slide
Lager Image
The set of n decision strategies ( ε 1 , ε 2 , ... εn )∈ σ that indicates the interaction results between peer responses to the external environment and Ui (.) that determines the reward to the resource sharing peer.
Proposition 2: In the non-cooperative game based subscribe mechanism; a given PGs allocation satisfying the Nash equilibrium, it is an in-efficient allocation and it is also cannot achieve the Pareto Optimality.
Proof: Suppose that one of strategies
PPT Slide
Lager Image
is a Nash equilibrium, which means this is the optimal solution to the problem of the PGs allocation. Thus
PPT Slide
Lager Image
And
PPT Slide
Lager Image
With (12) and (13), we can get the following equation (14):
PPT Slide
Lager Image
And it follows
PPT Slide
Lager Image
Compared (15) with (11), we can obtain the conclusion that the first-order condition of the Nash equilibrium is contradictory with the condition of Bowen-Lindahl-Samuelson when n ≥2. That is to say, this allocation is Pareto in-efficiency.
Suppose there is an allocation
PPT Slide
Lager Image
from the Nash equilibrium
PPT Slide
Lager Image
Each peer has the same marginal increase, which means there is a small parameter θ , and
PPT Slide
Lager Image
PPT Slide
Lager Image
= θ , obviously
PPT Slide
Lager Image
>
PPT Slide
Lager Image
, the utility of each peer is approximated as follow
PPT Slide
Lager Image
Since the utility function Ui (.) is increasing in Ss , thus the equation (16) is larger than zero. Therefore, every peer can receive benefit from the p2p networks, so, the free-riders may not pay with their private goods. It also demonstrates that the initiate PGs allocation is the Nash equilibrium but it cannot achieve the Pareto optimality, it’s an in-optimality allocation of the PGs. obviously, in this PGs allocation mechanism, every peer especially the free-riders haven’t taken into account influence of their payments to the total utilities of all peers. Because the free-riders regard the PGs as their private goods, their payments become less and less if they can obtain benefit from the p2p networks.
5. Walker Mechanism
In this section, we propose cooperative game based walker mechanism for an efficient the PGs allocation. We assume that the PGs resource sharing capacity is the average of all peers’ requirements, thus
PPT Slide
Lager Image
The cooperation process as following: first, everyone who wants to share the PGs or obtain the PGs in the P2P networks should broadcast its sharing and requirement to others; and then, the competing peers are arranged in the walker ring by their requirements; last, the competing peers pay with their private goods or payments is related to the average of all peers’ requirements, the Marginal Rate of Transformation ( MRT = μ ) and the next two adjacent peers’ requirements.
Fig. 2 show that the locations of all competing peers in the walker ring which are determined by their requirements. Specifically, each peer is arranged by the descending order of their requisitions ( ri > ri +1 ). The peer i ’s payment is related to the two adjacent peers’ requirements ri +1 and ri +2 (the index of all peers use model N to standardization).
PPT Slide
Lager Image
peers in the walker ring
Thus, peer i ’s payment is as follow
PPT Slide
Lager Image
- 5.1 Feasibility analyze
In this section, we analyze the feasibility of cooperative game based walker mechanism for the PGs allocation, which including two aspects: the individual rational and the aggregate rational.
Firstly, we analyze the feasibility of individual rational. We suppose peer i ’s private goods Ω i are more than his payment for consuming the PGs or the private goods are enough. That is to say, peer i can pays with his private goods for consuming the PGs. So, we denote that peer i ’s action is feasible. Meanwhile, if peer i hasn’t pay with his private goods for consuming the PGs is regarded as in-feasible. In this section, we discuss cooperation game based walker mechanism for an valid PGs allocation, so each peer is willing to pay with his private goods for consuming the PGs, these peers are regarded as individual rational.
Secondly, we analyze the feasibility of the aggregate rational. In cooperative game, every peer pays with the private goods for consuming the PGs according to the location in the walker ring, the parameter μ and the two adjacent peers’ requirements ri +1 and ri +2 . So, the total of peers’ payments as follows
PPT Slide
Lager Image
From the equation (19), we have the conclusion: all competing peers’ payment
PPT Slide
Lager Image
is decided by the MRT of each peer which is equal to μ , and the average requirements ϕr which equals to Sw . Therefore, this allocation mechanism guarantees the feasibility of the aggregate rational.
- 5.2 Validity prove
In this section, we assume that peer i ’s strategy space is σi = [0,Ω i ], with (17) and (18), we can get the payoff function as follow
PPT Slide
Lager Image
Proposition 3: in the cooperative game based walker mechanism for the PGs allocation, a given PGs allocation is Nash equilibrium, it is an efficient allocation and it is also can achieve Pareto Optimal.
Proof: Suppose that all the peers’ requirements
PPT Slide
Lager Image
are the Nash equilibrium, we define that
PPT Slide
Lager Image
And
PPT Slide
Lager Image
Meanwhile this PGs allocation
PPT Slide
Lager Image
( i = 1,2,3,... n ) is the Nash equilibrium and it also satisfies the Bowen-Lindahl-Samuelson equilibrium, which means it is the optimal solution of the PGs allocation problem. Thus, this allocation must satisfy the following three conditions:
  • is the solution to another problem as follow
PPT Slide
Lager Image
  • Subject to:
PPT Slide
Lager Image
Proof:
PPT Slide
Lager Image
Since the index of all peers use model N to standardization, we can get
PPT Slide
Lager Image
thus
PPT Slide
Lager Image
(b) Obviously, the sum of all peers’ payments equation (b) is easy to be established.
PPT Slide
Lager Image
(c) We use two methods to proof this condition.
1). we suppose that the PGs allocation
PPT Slide
Lager Image
( i = 1,2,3,... n ) is not satisfy the Bowen-Lindahl-Samuelson equilibrium, therefore, there is another PGs resource capacity
PPT Slide
Lager Image
for peers’ consumptions, we assume that
PPT Slide
Lager Image
thus
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
And also
PPT Slide
Lager Image
The equation (22) is in contradicted to the
PPT Slide
Lager Image
, which is the Nash equilibrium. Therefore, the PGs allocation
PPT Slide
Lager Image
( i = 1,2,3,... n ) is Bowen-Lindahl-Samuelson equilibrium.
2). we suppose that the PGs allocation
PPT Slide
Lager Image
( i = 1,2,3,... n ) is a Bowen-Lindahl-Samuelson equilibrium, which is derived from
PPT Slide
Lager Image
.
Since
PPT Slide
Lager Image
( i = 1,2,3,... n ) is the solution to the problem of (21).Thus, it must be subject to the first-order condition for all peers as follows
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Compare (23) with (11), we get the conclusion that the PGs allocation based on walker mechanism is an efficiency allocation. This allocation can achieve Pareto optimal and overcome the free-riding problem as competing peers are willing to pay with their private goods for consuming the PGs and these payments are related to their requirements (location in walker ring) and the MRT .
6. Simulation Results
In this section, to illustrate the validity of the model we proposed above, we give exact values to the solution and plot these results. From these results, we obtain some principles that hidden from the theoretical solutions of the model above. Simulations for the PGs allocation are carried out by the Numerical experiments.
In Fig. 3 , we plot the PGs resource from different proportions of cooperators ( pn ) and proportions of resource sharing ( p ), which represent the degree of selfless for cooperators. The value of PGs resource is equals to ( p pn ). Due to the resource sharing peer is the selfless peer who is willing to sharing his resources (PGs) to the competing peers who will pay with their private goods (price) for consuming the PGs. The value of PGs is proportional relationship between the proportions of cooperators and proportions of resource sharing. For example, we give three ranges of proportions of resource contribution( p ) as (0≤ p ≤0.5,0≤ p ≤0.8, and 0≤ p ≤1). Accordingly, the three largest PGs resources are calculated when ( pn =1) that is to say, all peers are willing to sharing all of their resources to the competing peers, and p equals to 0.5, 0.8 and 1, then three largest PGs. Resources are 1, 0.8 and 0.5 respectively. We note that the zones under each line is valid PGs resources with different ( pn ) and ( p ).
PPT Slide
Lager Image
the total PGs with (pn) and (p)
In Fig. 4 , we plot the changes of total PGs resource after peer consuming with three different MRT = μ as 1, 1.5 and 2. We assume that the initial PGs is one unite, and all competing peers pays with their private goods when they consumed the PGs. The previous theoretical analysis that the competing peers’ payments is
PPT Slide
Lager Image
and the initial PGs is one unite. The competing peers pay with their private goods according to the above equation, so, the PGs increasing in μ after the competing peers pay with their private goods for consuming PGs. Fig. 4 , the difference becomes larger when MRT increases. The MRT = μ as 1 in some other existing schemes (Reciprocity-Based Scheme [13 , 14] and tit-for-tat Scheme which means the competing peers sharing the same number of their resources according to their obtain the PGs); so, the total PGs of the P2P networks is the same as the initial cooperators’ sharing resources; in this scheme, if setting the parameter MRT = μ larger than 1, the total PGs of the P2P networks will be over than the total PGs when μ = 1. So, in this scheme, there are more PGs than other schemes, it can guarantee the quality of service (QoS) for the competing peers consuming the PGs. By this way, it can attract more peers join into the P2P networks, which can increase the size of the P2P networks, maintain the stability of the P2P networks and so on.
PPT Slide
Lager Image
the total PGs with MRT = μ
Fig. 5 shows that the total PGs increases when the number of cooperators ( n ) and the proportion of cooperators’ resource contribution ( p ) increases. In this situation, we assume there are 10 cooperators in p2p networks, and the proportion of cooperators’ resource contribution as (0≤ p ≤0.2,0≤ p ≤0.5, and 0≤ p ≤1). The number of cooperators from 1 to 10, and their resource sharing proportion 0≤ p ≤0.2, 0≤ p ≤0.5 and 0≤ p ≤1 respectively. The total PGs is calculated by the multiple of the number of cooperators and proportion of cooperators’ resource sharing p. if p =0, that means there is no resource sharing, the min value of the total PGs is 0; the competing peers cannot obtain resource. However, when n = 10 and p = 1, the total PGs reached the maximum value is 10. The three bars represent the cooperator(s) resources sharing proportion 0≤ p ≤0.2, 0≤ p ≤0.5 and 0≤ p ≤1 respectively. This is simple linear function as shown in the Fig. 5 .
PPT Slide
Lager Image
the total PGs with n and p
Fig. 6 shows that the total PGs increases with the parameter μ and the number of competing peers ( n ) consumed the PGs. We assume that three different MRT = μ as 1, 1.5 and 2. The number of competing peers from 1 to 10, and the MRT = μ , μ = 1, μ = 1.5, μ = 2 respectively. The competing peers are rational peers, who are willing to pay with their private goods for consuming PGs. The total PGs is calculated by the multiple of the number of cooperators and MRT = μ . When n = 10 and μ = 2, the total PGs reached the maximum value is 20. The total PGs increasing with the number of competing peers consuming the PGs and large parameter μ would obtain large PGs value. Similarly the MRT = μ as 1 in some other existing schemes; in this scheme, if setting the parameter MRT = μ larger than 1, the total PGs of the P2P networks will be over than the total PGs when μ = 1. So, in this scheme, there are more PGs than other schemes, it can guarantee the quality of service (QoS) for the competing peers consuming the PGs. By this way, it can attract more peers join into the P2P networks, which can increase the size of the P2P networks, maintain the stability of the P2P networks and so on.
PPT Slide
Lager Image
the total PGs with n and MRT = μ
7. Conclusion
This paper presented an incentive scheme to overcome the free-riding problem in P2P networks. We defined that the cooperators contribution resource as the PGs and then build a system model to allocate the PGs for the competing peers to achieve Nash equilibrium and Pareto optimal. We used game theory resolve this model encourage peers to sharing their resources and pay with their private resources for consuming the PGs according to their requirements and the parameter MRT = μ . We also analyzed the feasibility and demonstrated the efficiency for resource allocation in two scenarios: non-cooperative game based Subscribe mechanism and cooperative game based Walk mechanism respectively. In Non-cooperative game, each peer pays with his private goods for consuming the PGs without taking into account the other peers’ strategies. Therefore, these peers pay with their private goods only according to their requirements or consumptions. However, there are some free-riders do not pay with their private goods when they consume the PGs. In cooperative game, which based on the walker mechanism each peer pays with private goods for consuming the PGs within taking into account the other peers’ strategies. the total of the competing peers payments is equals to the providers sharing costs, which can incentive the providers sharing more resources, overcome the free-riders and increase the total PGs. Simple numerical results show that the relationships between the PGs resource and other parameters, i.e. MRT , proportion of cooperator, the proportion of resource sharing, and the number of cooperators. Specifically, the increasing of PGs resource is related to MRT , the proportion of cooperator, the proportion of resource sharing, the number of cooperators and all these relation is linear. We obtained the following two conclusions: first, based on subscribe mechanism within non-cooperative game, the PGs allocation is feasibility but it is in-efficiency and it is also cannot overcome the free-riding problem; second, based on walker mechanism within cooperative game, the PGs allocation is feasibility, and is an efficient allocation, which can achieve the Pareto efficiency and satisfy the Bowen-Lindahl-Samuelson equilibrium and overcome the free-riding problem.
BIO
Qingfeng Zhang, is currently a Ph.D. candidate in University of Electronic Science and Technology of China, Chengdu, China. His research interests include cooperative communications, resource allocation and incentive mechanism for P2P networks or p2p social networks. Email: qingfengzhang2010@126.com
Sheng Wang, received his Ph.D. degree in information and communication engineering from University of Electronic Science and Technology of China, Chengdu, China. He is a professor of school of Communication and Information Engineering in University of Electronic Science and Technology of China. His main research interests include traffic engineering, the key technologies for the NGN and WDM. Email: wsh_keylab@uestc.edu.cn
Dan Liao, received his Ph.D. degree in information and communication engineering from University of Electronic Science and Technology of China, Chengdu, China. He is a professor of school of Communication and Information Engineering in University of Electronic Science and Technology of China. His main research interests include cooperative communications, resource allocation and incentive mechanism for P2P networks or p2p social networks. Email: liaodan@uestc.edu.cn
References
Adar E. , Huberman B. A. 2000 “Free riding on Gnutella,” First Monday 5 (10) 42 - 68    DOI : 10.5210/fm.v5i10.792
Feldman M. , Chuang J. 2005 “Overcoming Free-Riding Behavior in Peer-to-PeerSystems,” ACM SIGecom Exchanges 5 (4)    DOI : 10.1145/1120717.1120723
Li Y. , Liu Y. , Xu K. , Chen W. “Analysis and Balanced Mechanism on Free-rider In P2P Network,” in Proc. of 2010 Second International Conference on Computer Modeling and Simulation
Garbacki P. , Iosup A. , Epema D. , van Steen M. “2Fast: Collaborative downloads in P2P networks,” in Proc. of 6th IEEE Int. Conf. Peer-to-Peer Comput 2006 23 - 30
Wang J. , Yeo C. , Prabhakaran V. , Ramchandran K. “On the role of helpers in peer-to-peer file download systems: Design, analysis and simulation,” presented at the 6th Int. Workshop Peer-to-Peer Syst. (IPTPS ’07) 2007
Sirivianos M. , Park J. H. , Yang X. , Jarecski S. “Dandelion: Cooperative content distribution with robust incentives,” in Proc. of 2007 Usenix Annu. Tech. Conf 157 - 170
Eger Kolja , Killat Ulrich 2007 “Resource Pricing in peer-to-peer Networks,” IEEE Communications Letters 11 (1)    DOI : 10.1109/LCOMM.2007.061094
Park Jaeok , Schaar Mihaela vander “Pricing and Incentives in peer-to-peer Networks,” IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings
Wang Chi , Wang Hangba , Lin Yu , Chen Shanzhi “A Currency-based P2P Incentive Mechanism Friendly with ISP,” in Proc. of 2010 International Conference On Computer Design and Appliations (ICCDA 2010)
Rius J. , Cores F. , Solsona Francesc “A New Credit-Based Incentive Mechanism for P2P Scheduling with User Modeling,” 2009 First International Conference on Advances in P2P Systems
Buragohain C. , Agrawal D. , Suri S. “A game theoretic framework for incentives in P2P systems,” in Proc. of 3rd Int. Conf. Peer-to-PeerComput 2003 48 - 56
Ma T. B. , Lee S. C. M. , Lui J. C. S. , Yau D. K. Y. 2006 “Incentive and service differentiation in P2P networks: A game theoretic approach,” IEEE/ACM Trans. Netw 14 (5) 978 - 991    DOI : 10.1109/TNET.2006.882904
Lin C. S. , Cheng Y. C. “A Barter-Based Incentive Mechanism for peer-to-peer Media Streaming,” The 13th IEEE International Symposium on Consumer Electronics (ISCE2009)
Menasché D. S. , Massoulié L. , Towsley D. Thomson Research “Reciprocity and Barter in peer-to-peer Systems,” IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings
Park Jaeok , Schaar Mihaela vander 2010 “A Game Theoretic Analysis of Incentives in Content Production and Sharing Over peer-to-peer Networks,” IEEE Journal of Selected Topics in Signal Processing 4 (4)
Xie Fu , Liu Feng-Ming , Yang Rong-Rong , Lu Ran “Game-Based Incentive Mechanisms for Cooperation in P2P Networks,” Fourth International Conference on Natural Computation 2008
Zhao Bridge Q. , Lui John C.S. , Chiu Dah-Ming “Analysis of Adaptive Incentive Protocols for P2P Networks,” IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings
Yan Yonghe , El-Atawy Adel , Al-Shaer Ehab “Ranking-based Optimal Resource Allocation in peer-to-peer Networks,” IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2007 proceedings
Golle P. , Leyton-Brown K. , Mironov I. , Lillibridge M. “Incentives for sharing in peer-to-peer networks,” in Proc. of 2nd Int.Workshop Electron.Commerce (WELCOM) 2001 75 - 87
Feldman M. , Lai K. , Stoica I. , Chuang J. “ Robust incentive techniquesfor peer-to-peer networks,” in Proc. of ACM Conf. Electron. Commerce(EC ’04) 2004
Zhang Z. , Chen S. , Yoon M. “MARCH: A Distributed Incentive Scheme for peer-to-peer Networks,” IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2007 proceedings
Qingjie W. , Jian Y. U. , Mei Y. U. , Jie Z. , Zheng Z. “Incentive Compatible Mechanism in P2P Systems,” 2009 IEEE
Rahman R. , Meulpolder M. , Hales D. , Pouwelse J. , Epema D. , Sips H. “Improving Efficiency and Fairness in P2P Systems with Effort-Based Incentives,” IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
Quek Han-Yang , Tan Kay Chen , Tay Arthur 2009 “Public Goods Provision: An Evolutionary GameTheoretic Study Under Asymmetric Information,” IEEE Transanctions on Computational Inteliligence and in Games 1 (2)
Di Sheng , Wang Cho-Li 2013 “Dynamic Optimization of Multi attribute Resource Allocation in Self-Organizing Clouds,” IEEE Transanctions on parallel and distributed systems 24 (3)
Li Shu qin , Zhang Shao quan “Distributed Resource Allocation for P2P Multicast Networks with Network Coding Optimality Delays and Incentives,” 2011 International Symposium on Networking Coding July 2011 1 - 4
Kumar Che tan , Altinkemer Kemal , De Prabuddha (2011) “A mechanism for pricing and resource allocation in peer-to-peer networks,” Electronic Commerce Research and Applications 10 26 - 37    DOI : 10.1016/j.elerap.2010.07.004
Hua Yusuo , Dong Dafan , Li Jiang , Wu Feng (2013) “Efficient and incentive-compatible resource allocation mechanism for P2P-assisted content delivery systems,” Future Generation Computer Systems 29 1611 - 1620    DOI : 10.1016/j.future.2012.08.008
linWei Xi. , Chen M. , Tan C. , Bai H. , Zhang G. , Wang Z. (2013) “iRep:indirect reciprocity reputation based efficient content delivery in BT-like systems,” Telecommun Syst 54 47 - 60    DOI : 10.1007/s11235-013-9715-0
Ho Donghyeok , Song Hwangjun “Resource Allocation Algorithm based on Social Relation for Video Streaming Services over P2P Network,” in Proc. of 2012 18th IEEE International Conference on Networks Dec. 2012 185 - 190
Ma D. , Wang X. , Chen W. , Yang S. , Ma L. (2014) “A research on dynamic allocation of network resources based on P2P traffic planning,” Peer-to-Peer Netw. Appl. 7 511 - 524    DOI : 10.1007/s12083-012-0163-5
Qureshi M. B. , Dehnavi M. M. , Min-Allah N. , Shuaib Qureshi M. , Hussain H. , Rentifis I. , Tziritas N. , Loukopoulos T. , Khan S. U. , Xu C. Z. , Zomaya A. Y. (2014) “Survey on Grid Resource Allocation Mechanisms,” J Grid Computing 12 399 - 441    DOI : 10.1007/s10723-014-9292-9
Kang X. , Wu Y. dong 2015 “Incentive Mechanism Design for Heterogeneous Peer-to-Peer Networks: A Stackelberg Game Approach,” IEEE Transanctions on mobile computing 14 (5)
Zheng J. , Cai Y. 2014 “Distributed channel selection for interference mitigation in dynamic environment: a game-theoretic stochastic learning solution,” IEEE Trans. Veh. Tech. 63 (9) 4757 - 4762    DOI : 10.1109/TVT.2014.2311496
Zheng J. , Cai Y. 2014 “Optimal power allocation and user scheduling in multicell networks: base station cooperation using a game-theoretic approach,” IEEE Trans. Wireless Commun. 13 (12) 6928 - 6942    DOI : 10.1109/TWC.2014.2334673
Kreps David M 1990 “A Course in Microeconomic Theory,” Princeton UniversityPress,Princeton New Jersey
Vega-Redondo Fernando “ Economics and the Theory of Games,” University of Cambridge press