Min-Cost Selfish Multicast with Network Coding

We consider the single-source min-cost multicast problem, which can be framed as a convex optimization problem with the use of network codes and convex increasing edge costs. A decentralized approach to this problem is presented by Lun, Ratnakar, et al. [1] for the case where all users cooperate to reach the global minimum. We analyze the cost for the scenario where each of the multicast receivers greedily routes its flows and show that a Nash equilibrium exists for such a scenario. We present an allocation rule by which edge cost at each edge is allocated to flows through that edge. We show that for any power-law cost function on each edge, we have a pricing rule such that the flow cost at user equilibrium is the same as the min-cost. This leads to the construction of a selfish flow-steering algorithm for each receiver, which is also globally optimal. We further extend the algorithm for completely distributed flow adaptation at nodes in the network, which also achieves globally minimal cost in steady state. We also generalize the framework to the case of multiple multicast sessions and show that our results hold for user equilibrium in this case too.