Distributed algorithms in service overlay networks: a game theoretic perspective

When designing distributed algorithms for application overlay networks, it is usually assumed that the overlay nodes are cooperative to collectively achieve optimal global performance properties. However, this assumption does not hold in reality, as nodes generally tend to be noncooperative and always attempt to maximize their gains by optimizing their strategies. With such an assumption, we present extensive theoretical analysis to gain insights from a game theoretic perspective, with respect to the behavior of nodes and the equilibrium of the system. The main idea in our analysis is to design appropriate payoff functions, so that the equilibrium of the system may achieve the optimal properties that we desire. Driven by the per-node goal of maximizing gains, such payoff functions naturally lead to distributed algorithms that lead to the desired favorable properties of overlay networks.