Incentives - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 88

P > S, which is the same as the original Prisoner's Dilemma. Thus, the Nash
equilibrium for such users occurs at the profile: (No Supply, No Supply). As
the P2P network progresses to the mature stage (i.e., the size of the network
becomes stabilized), we can expect that a majority of users are neither fully
altruistic nor fully non-cooperative. For these users, the payoffs ranking is:
R > T > P > S. As a result, the payoff matrix is depicted in Figure 5.4. As
can be seen, there are two equally probable Nash equilibria: (Supply, Supply)
and (No Supply, No Supply). Consequently, whether or not the P2P network
is viable or e cient depends on the relative proportions of users in these two
equilibria. Results obtained in empirical studies [Becker and Clement, 2004]
using real P2P networks conform quite well to the simple analysis described
above.

Player 2

Action: Supply Action: No Supply

1
2

2
2

g g

Player 1

R T Action: Supply

1

R S g

S P Action: No Supply

g

2

T P

FIGURE 5.4: Payoff table in the settlement stage [Becker and Clement,
2004].

Ma et al. [Ma et al., 2004a, Ma et al., 2004b] suggested an analytically
sound incentive mechanism based on a fair bandwidth allocation algorithm.
Indeed, the key idea is to model the P2P sharing as a bandwidth allocation
problem. Specifically, the model is shown in Figure 5.5. Here, multiple file
requesting peers compete for uploading bandwidth of a source peer. Each
requesting peer i sends a bidding message b i to the source peer N S . The
source peer then divides its total uploading bandwidth W S into portions of x i
for the peers. However, due to network problems such as congestion, each peer
i may receive an actual uploading bandwidth of x ′ i which is smaller than x i .
Each bidding message b i is the requested amount of bandwidth. Thus, we
have x i ≤b i . To achieve a fair allocation, the source peer uses the contribu-
tion level C i of each competing peer i to determine an appropriate value of x i .
Ma et al. [Ma et al., 2004a, Ma et al., 2004b] described several allocation algo-
rithms with different complexities and considerations: simplistic equal sharing,
max-min fair allocation, incentive-based max-min fair allocation, utility-based
max-min fair allocation, and incentive with utility-based max-min fair alloca-
tion. The last algorithm is the most comprehensive and effective. It works by
solving the following optimization problem:

N

C i log( x i
b i

max + 1) (5.8)

i=1