Inter-session network coding with strategic users: A game-theoretic analysis of the butterfly network - Mohsenian-Rad, Hamed; Huang, Jianwei; Wong, Vincent W. S.; Jaggi, Sidharth; Schober, Robert (IEEE Transactions on Communications, 2013)
We analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game among users. In particular, we study a butterfly network, where a bottleneck link is shared by network coding and routing flows. We assume that network coding is performed using pairwise XOR operations. We prove the existence of Nash equilibrium for a wide range of utility functions. We also show that the number of Nash equilibria can be large (even infinite) for certain choices of parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding, where the Nash equilibrium is always unique. We characterize the worst-case efficiency bound, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA in comparison with the case where a single pricing scheme is used. However, even when a discriminatory pricing scheme is used, the PoA is still worse than for the case when network coding is not applied. This implies that, although inter-session network coding can improve performance compared to routing, it is much more sensitive to users' strategic behavior. © 1972-2012 IEEE.
CRIS-Team Scopus Importer:2020-02-03
Keywords: butterfly network; efficiency bound; game theory; Inter-session network coding; Nash equilibrium; price-of-anarchy