  A common assumption in the existing network coding literature is that the
users are cooperative and non-selfish. However, this assumption can be violated
in practice. In this paper, we analyze inter-session network coding in a wired
network using game theory. We assume selfish users acting strategically to
maximize their own utility, leading to a resource allocation game among users.
In particular, we study the well-known butterfly network topology where a
bottleneck link is shared by several network coding and routing flows. We prove
the existence of a Nash equilibrium for a wide range of utility functions. We
show that the number of Nash equilibria can be large (even infinite) for
certain choices of system parameters. This is in sharp contrast to a similar
game setting with traditional packet forwarding where the Nash equilibrium is
always unique. We then characterize the worst-case efficiency bounds, i.e., the
Price-of-Anarchy (PoA), compared to an optimal and cooperative network design.
We show that by using a novel discriminatory pricing scheme which charges
encoded and forwarded packets differently, we can improve the PoA. However,
regardless of the discriminatory pricing scheme being 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
ordinary routing, it is significantly more sensitive to users' strategic
behaviour. For example, in a butterfly network where the side links have zero
cost, the efficiency can be as low as 25%. If the side links have non-zero
cost, then the efficiency can further reduce to only 20%. These results
generalize the well-known result of guaranteed 67% worst-case efficiency for
traditional packet forwarding networks.
