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

Specifically, player x incurs some cost to be a member of a coalition. The
amount of player x's coalitional effort is denoted as e(x). This can be inter-
preted as the amount of outgoing bandwidth and other resources consumed.
The utility of player x is then defined as the difference between the share of
value obtained from the coalition v(x), and the amount of effort contributed
to the coalition e(x). That is, utility is defined as:

u(x) = v(x)−e(x) (5.16)

Moreover, it is assumed that e(x) depends on the number of peers in the
coalition, i.e.,

(|G|−1)e x = p

e(x) = (5.17)

e x∈G\{p}

where e is a non-negative constant.
It is clear that if player x does not join any coalition, its utility is zero, i.e.,
u(x) = 0 if x /∈G. This implies that a rational player will only join a coalition
providing non-negative utility, u(x)≥0 if x∈G. This is called the incentive
compatibility constraint:

u(x)≥0 if x∈G (5.18)

Here, G a is defined as the set of players and can be used to analyze the
peer selection game as G a increases:
Case 1 G a ={p}
This is the baseline case where the parent is the sole player. There is only
one possible coalition, G 1 ={p}. The player obtains all the value created by
the coalition, which is given by:

V (G 1 ) = v(p) (5.19)

Since p has no downstream peer, its effort is zero, i.e., e(p) = 0. The utility
of p is u(p) = v(p).
Case 2 G a ={p, c 1 }
The set of players includes the parent and one potential child, i.e., P =
{p, c 1 }. If p accepts c i as its child, they form a coalition, G 2 ={p, c 1 }. The
value created by the coalition is to be distributed between the two players,
i.e.,

V (G 2 ) = v(p) + v(c 1 ) (5.20)

The value V (G 2 ) needs to be distributed judiciously in order to make G 2
a stable coalition such that neither p nor c 1 has an incentive to leave. This
requires the following conditions to be satisfied:

v(p)−e≥V (G 1 ) (5.21)

v(c 1 )−e≥0 (5.22)

Condition (5.21) suggests that p should receive a utility larger than the