Algorithms for multiplayer multicommodity flow problems

We investigate the multiplayer multicommodity flow problem: several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value. We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence.