Multilateral Transport Games

We consider networks, such as the Internet, where end-to-end traffic flow is determined by multiple domains with independent, and possibly competing interests. Such {em multilateral networks} offer smaller domains the possibility to influence traffic flows if they agree to work together. We explore cooperative game theoretic models which account for such coalitional behaviour. One objective is to model the tradeoffs between transitting third-party traffic versus satisfying one's own traffic demands. In contrast to previous work our focus is not on short-term routing decisions and we do not allow transferrable utility. This leads us to the notion of {em harmonious routing}. This is a routing where the amount of third-party traffic transited by a node is bounded by the amount of traffic it offers. We examine the complexity of computing such routings under several traffic demand models. Also considered is the question of designing {em deployable} subnetworks, i.e., a network that admits a harmonious routing. We describe connections to recent algorithmic work, as well as to two older results, one due to Scarf in game theory and one due to Mader in combinatorial optimization. A number of open problems are also raised.