How good is bargained routing?

Game theoretic models have been widely employed in many networking contexts. Research to date has mainly focused on non-cooperative networking games, where the selfish agents cannot reach a binding agreement on the way they would share the network infrastructure and the operating points are the Nash equilibria. These are typically inefficient, as manifested by large values of the Price of Anarchy (PoA). Many approaches have been proposed for mitigating this problem, however under the standing assumption of a non-cooperative game. In a growing number of networking scenarios it is possible for the selfish agents to communicate and reach an agreement, i.e., play a cooperative game. Therefore, the degradation of performance should be considered at an operating point that is a cooperative game solution. Accordingly, our goal is to lay foundations for the application of cooperative game theory to fundamental problems in networking. We explain our choice of the Nash Bargaining Scheme (NBS) as the solution concept, and we introduce the Price of Selfishness (PoS), which considers the degradation of performance at an NBS. We focus on the fundamental load balancing game of routing over parallel links. First, we study the classical scenario of agents that consider the same performance objectives. While the PoA here can be very large, we establish that, under plausible assumptions, the PoS attains its minimum value, i.e., through bargaining, the selfish agents reach social optimality. We then extend our study to consider the “heterogeneous” case, where agents may consider vastly different performance objectives. We demonstrate that the PoS and PoA can be unbounded, yet we explain why both measures may now be unsuitable. Accordingly, we introduce the Price of Heterogeneity (PoH), as a proper extension of the PoA. We establish an upper-bound on the PoH for a general class of heterogeneous performance objectives, and indicate that it provides incentives for bargain- ng also in this general case. We discuss network design guidelines that follow from our findings.