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

2004], the children peers are responsible for reporting such suspicious selfish
peers to the root (or the server) in the tree. Jun et al.'s scheme is also more
flexible in that even upon receiving such “negative reports,” the root may not
discard such suspected selfish peers immediately. Instead, the root keeps track
of a trust metric for each peer in the tree. A negative report only decreases
the trust value. Only when the trust value falls below some threshold, the
suspected selfish peer is discarded from the tree and the peers under its sub-
tree are relocated.

5.2.2.3 Coalition-Based Media Streaming

In P2P media streaming, each peer can choose its upstream peers (parents)
and downstream peers (children). In a recent study by Yeung and Kwok [Ye-
ung and Kwok, 2009], they consider peers as rational entities and model the
peer selection process as a strategic game.
They first focus on the case where there is only one parent, p, and a
set of children, c 1 , c 2 ,, c n . The objective is to study how p should select
its children such that the resultant parent-child relationships are stable and
resilient to peer dynamics. Specifically, Yeung and Kwok [Yeung and Kwok,
2009] formulate a cooperative game where the players are the parent and
its children. The objective is to form a stable coalition which creates the
highest aggregate value. Here, stability is defined as the probability that a
participant departs from the coalition and acts alone. The aggregate value is
to be distributed among the members. In other words, two inter-related issues
need to be tackled: (1) formation of a stable coalition; and (2) distribution of
the aggregate value. The elements of cooperative game and what constitutes
a stable coalition are defined as follows.
A cooperative game consists of a finite set of players, N , and a scalar-
valued function, V (), which associates every subset G of N a real number,
V (G). For each coalition, G, the number V (G) represents the total payoff to
be divided among the members of G, i.e.,

V (G) = v(x) (5.10)

∀x∈G

where v(x) represents the value allocated to player x.
Here, V (G) is called the value of the coalition, G. Players can form other
coalitions to obtain different values. We say that a stable coalition is formed
when players have no incentive to deviate from joining the coalition. Specifi-
cally, a coalition, G, is stable if we cannot find a better coalition, G ′ , G ′ ⊆G,
with respect to V (). This implies:

v(x)≥V (G ′ ) ∀G ′ ⊆G (5.11)

x∈G

In other words, if a coalition is unstable, it is possible for a subset of players
to deviate such that each deviating player can obtain a larger value than they