Resumen de On Economies of Scale and Cooperation in Some Communication Networks

Darko SKorin Kapov, Jadranka Skorin Kapov

• The objective for designers of communication networks is often to minimize the cost, while satisfying various constraints on reliability, congestion, speed, capacity and coverage. Economies of scale play an important role in their considerations. Namely, the creation of high capacity links and concentration of flows reduces the number of needed links and the unit flow cost. Applications of this approach are seen, for example, in high capacity lines of backbone networks in telecommunications, and in high volume traffic between major airports in air transportation networks.

  Most of the related work in the literature was performed in the context of the so-called hub networks. In those networks a certain subset of focal nodes (i.e. hubs) is fully interconnected while other nodes are connected to those hubs and the economies of scale are achieved by discounting the cost of traffic among hubs. The hub networks were extensively studied over the last couple of decades and numerous computational studies show that hub networks are quite attractive and practical. Nevertheless, the restrictions imposed with the hub network model are sometimes to prohibitive. Recently, authors together with some collaborators introduced the network model in which each pair of nodes can communicate via any path, and the cost of sending flow through each link is discounted if and only if the amount of flow exceeds a certain threshold.

  This approach also gives incentive to concentrate flows. It seems however, that the above threshold based discounting model is even more �efficient� than hub networks in its use of a relatively small number of links and in the exploitation of economies of scale. We will refer to the threshold based discounting network model as to the hub-like network model.

  In this paper, we study the cost allocation problem in hub-like networks.

  Namely, the cost of services delivered through the hub-like network is distributed among its users who may be individuals or organizations with possibly conflicting interests. The cooperation of these users is essential for the exploitation of economies of scale. Consequently, there is a need to find a fair distribution of the cost of providing the service among network users. It is well known that in general, the game theoretic network cost allocation solution concepts are computationally prohibitive even for relatively small problems. Moreover there are no general practical algorithms for the computation of these solutions.

  Consequently, researchers have concentrated on individual classes of network games to demonstrate that computation of network cost allocation solution concepts is sometimes feasible in the context of a particular problem.

  In our study we take similar approach. Namely, we develop some cooperative game theory based mechanism to efficiently characterize cost allocation solutions for networks that allow threshold based discounting. Specifically, while paying special attention to users� contribution to economies of scale, we formulate the associated hub-like network cost allocation games in the characteristic function form. Since the optimization problem is NP-hard, we depend on our heuristic algorithms to obtain optimal or best-known optimization results.

  These results are used to determine the value of the associated characteristic function. We use our four and three-dimensional optimization formulations for small and large size problems respectively. In the four dimensional case we define players to be pairs of users, while in the three dimensional case we set players to be individual users. We demonstrate that hub-like games are decomposable into link games. We then show that the cores of those games are not empty and that they can be characterized with polynomial number of constraints. Finally, we show that the nucleolus of the above hub-like network games can be efficiently computed.

  Key words: network design, economies of scale, heuristic algorithms, combinatorial optimization, cost allocation, cooperative games