Repeated Inter-Session Network Coding Games: Efficiency and Min-Max Bargaining Solution

Abstract — Recent results have shown that selfish users do not have an incentive to participate in inter-session network coding in a static non-cooperative game setting. Because of this, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 20%. In this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be improved to 36%. We design a grim-trigger strategy that encourages users to cooperate and participate in the inter-session network coding. A key challenge is to determine a common cooperative coding rate that the users should mutually agree on. We resolve the conflict of interest among the users through a bargaining process, and obtain tight upper bounds for the price-of-anarchy which are valid for any possible bargaining scheme. Moreover, we propose a simple and efficient min-max bargaining solution that can achieve these upper bounds, as confirmed through simulation studies. The co-existence of multiple selfish network coding sessions as well as the co-existence of selfish network coding and routing sessions are also investigated. Our results represent a first step towards designing practical inter-session network coding schemes which achieve reasonable performance for selfish users. I