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

do staying put. In game theory literature, the above definition of stability is
called the core of the cooperative game. In our context, it is undesirable for
peers to deviate after joining as that would disrupt the structure of the P2P
network and, in turn, adversely affect the streaming quality.
With the above definitions, a cooperative game, called the peer selection
game, can be devised to model the peer selection process. The players are a
parent p and a set of children, c 1 , c 2 ,, c n . The set of all players are denoted
as G a , i.e.,

G a ={p, c 1 , c 2 ,, c n } (5.12)
The players can freely form other coalitions, G, among themselves, where
G⊆G a . In general, different coalitions lead to different values. The function
V (G) should satisfy the following conditions:

V (G) = 0 if p /∈G (5.13)

V (G)≤V (G ′ ) if G⊆G ′

(5.14)

V (G 1 ∪c i )−V (G 1 ) = V (G 2 ∪c i )−V (G 2 ) (5.15)

Condition (5.13) dictates that the parent, p, is a necessary member in any
coalitions that generate non-zero values. In other words, p is the veto player
of the game. This is a reflection of the reality where downstream peers depend
on their parent for media packets. Without the participation of p, a coalition
does not bring any value to the members.
Condition (5.14) indicates that when comparing two coalitions, G and G ′ ,
the coalition with more members always generates a value no smaller than
the other does. This property precisely models a practical scenario where a
parent having a larger number of children is more important because if such
a parent departs, a large number of other peers will be disconnected. Thus,
the system should attach a higher value to such a coalition.
Condition (5.15) means that, in general, the same peer, c i , brings different
marginal utilities to different coalitions. The discrepancy is attributed to the
heterogeneous nature of P2P media streaming. For instance, the presence of c i
would be more significant if the coalition contains only a few children. On the
other hand, c i does not create much value if it joins another coalition already
having many children.
We require the value function V (G) to satisfy all the three conditions
discussed above. However, the precise definitions depend on the specific char-
acteristics of the application. A specific value function is defined below.
In the peer selection game, the formation of a coalition G, would create an
aggregate value, represented by V (G) =

∀x∈G v(x), where v(x) represents
the utility allocated to player x. It is assumed that each player would like
to maximize its share of utility, i.e., player x is interested in maximizing
v(x). This is reasonable because each peer x is more concerned with its own
performance in terms of v(x). On the other hand, V (G) is a measure of the
value of coalition G, in the P2P network.
The participating cost of peers should also be taken into consideration.