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

- Received : February 24, 2015
- Accepted : June 21, 2015
- Published : August 31, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

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.
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.
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
s_{i}
, 0≤
s_{i}
≤
θ_{i}
; and the PGs requirement is
r_{i}
,
r_{i}
≥0 ; the peer should pay with private goods for consuming the PGs is
p_{i}
, 0≤
p_{i}
≤Ω
_{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
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
let
S_{S}
denote that the PGs resource capacity
S_{S}
is the summation of all peers’ sharing resource or the competing peers’ requirements. So,
while in corporative game based walker mechanism, let
S_{w}
denote the PGs resource sharing capacity is the average of all peers’ requirements, so,
and peers’ payment is
Thus, in order to satisfy that all payments from peers should be no less than the total costs, the equation of
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
U_{i}
(
S
,
p_{i}
), which is increasing in
S
and decreasing in
p_{i}
.
Let us consider the following form of utility function which satisfies the above assumption:
where 0<
p_{i}
≤Ω
_{i}
, that means the competing peers is cooperative peer, who is willing to pays with his private goods for consuming the PGs; where
p_{i}
=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
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.
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
^{*}
,
) which is the solution of the problem, thus
S
^{*}
≥0; 0≤
≤Ω
_{i}
; (i=1,2,3…n)
Let
L
(
S
,
p_{i}
,
β
) denotes the Lagrangian function where
β
>0 and 0≤
p_{i}
≤Ω
_{i}
,
S
≥0;
β
is the Lagrange multiplier associated with constraint (3) .Then
The first-order conditions are
According (7) and (8), we can obtain another equation (10) without
β
We note that this allocation is an efficient PGs allocation and it is also satisfy the Bowen-Lindahl-Samuelson condition in equation (11).
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
S_{S}
and
S_{w}
, which represent the non-cooperative game based subscribe mechanism and the cooperative game based walker mechanism respectively.
MRT
. Thus
p_{i}
=
ε_{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.
MRT
=
μ
, and all competing peers should pay with their private goods
p_{i}
=
ε_{i}
for consuming the PGs within non-cooperative game. Thus
And
We define this game as a strategy game, peer
i
’s strategies space as
σ_{i}
= [0,Ω
_{i}
], the payoff function as follow
The set of n decision strategies (
ε
_{1}
,
ε
_{2}
, ...
ε_{n}
)∈
σ
that indicates the interaction results between peer responses to the external environment and
U_{i}
(.) 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
is a Nash equilibrium, which means this is the optimal solution to the problem of the PGs allocation. Thus
And
With (12) and (13), we can get the following equation (14):
And it follows
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
from the Nash equilibrium
Each peer has the same marginal increase, which means there is a small parameter
θ
, and
−
=
θ
, obviously
>
, the utility of each peer is approximated as follow
Since the utility function
U_{i}
(.) is increasing in
S_{s}
, 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.
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 (
r_{i}
>
r_{i}
_{+1}
). The peer
i
’s payment is related to the two adjacent peers’ requirements
r_{i}
_{+1}
and
r_{i}
_{+2}
(the index of all peers use model N to standardization).
peers in the walker ring
Thus, peer
i
’s payment is as follow
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
r_{i}
_{+1}
and
r_{i}
_{+2}
. So, the total of peers’ payments as follows
From the equation (19), we have the conclusion: all competing peers’ payment
is decided by the MRT of each peer which is equal to
μ
, and the average requirements
ϕ_{r}
which equals to
S_{w}
. Therefore, this allocation mechanism guarantees the feasibility of the aggregate rational.
i
’s strategy space is
σ_{i}
= [0,Ω
_{i}
], with (17) and (18), we can get the payoff function as follow
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
are the Nash equilibrium, we define that
And
Meanwhile this PGs allocation
(
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:
Proof:
Since the index of all peers use model N to standardization, we can get
thus
(b) Obviously, the sum of all peers’ payments equation (b) is easy to be established.
(c) We use two methods to proof this condition.
1). we suppose that the PGs allocation
(
i
= 1,2,3,...
n
) is not satisfy the Bowen-Lindahl-Samuelson equilibrium, therefore, there is another PGs resource capacity
for peers’ consumptions, we assume that
thus
Since
And also
The equation (22) is in contradicted to the
, which is the Nash equilibrium. Therefore, the PGs allocation
(
i
= 1,2,3,...
n
) is Bowen-Lindahl-Samuelson equilibrium.
2). we suppose that the PGs allocation
(
i
= 1,2,3,...
n
) is a Bowen-Lindahl-Samuelson equilibrium, which is derived from
.
Since
(
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
and
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
.
p_{n}
) and proportions of resource sharing (
p
), which represent the degree of selfless for cooperators. The value of PGs resource is equals to (
p
∗
p_{n}
). 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 (
p_{n}
=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 (
p_{n}
) and (
p
).
the total PGs with (p_{n} ) 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
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.
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
.
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.
the total PGs with n and MRT = μ
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.
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

1. Introduction

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

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- SYSTEM

PPT Slide

Lager Image

- Subject to:

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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
PPT Slide

Lager Image

- 4.1 Feasibility analyze

In non-cooperative game, each peer pays with private goods
- 4.2 Validity prove

According to the previous assumption that
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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

PPT Slide

Lager Image

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
PPT Slide

Lager Image

PPT Slide

Lager Image

- 5.2 Validity prove

In this section, we assume that peer
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- is the solution to another problem as follow

PPT Slide

Lager Image

- Subject to:

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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 (
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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
BIO

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

Citing 'A Game theoretic analysis of public goods allocation in p2p networks
'

@article{ E1KOBZ_2015_v9n8_2854}
,title={A Game theoretic analysis of public goods allocation in p2p networks}
,volume={8}
, url={http://dx.doi.org/10.3837/tiis.2015.08.006}, DOI={10.3837/tiis.2015.08.006}
, number= {8}
, journal={KSII Transactions on Internet and Information Systems (TIIS)}
, publisher={Korean Society for Internet Information}
, author={Zhang, Qingfeng
and
Wang, Sheng
and
Liao, Dan}
, year={2015}
, month={Aug}