On primal-dual cost allocation schema in multicast communication: Combinatorial game theory model

We analyze the cost allocation strategy associated with the problem of sending information from some source to a number of communication network users. A multicast routing chooses a minimum cost network that spans the source and all the receivers. The cost of such a network is distributed among its receivers who may be individuals or organizations with possibly conflicting interests. These receivers are likely to cooperate if they are charged the `fair share´ of the cost. Providing network developers, users and owners with computable `fair´ cost allocation solution procedures is of great importance for network management. We overview some previously published, as well as some new results, in the development of algorithmic cooperative game theory based mechanisms to efficiently compute `attractive´ cost allocation solutions for multicast networks. We also present some open cost allocation problems and the potential contribution that combinatorial game theory models might make in the future.