Setting a Maximum Capacity Network and Sharing its Cost.
Andrés Caro  1@  , Miguel Hinojosa  1@  , Diego Borrero  1@  
1 : Pablo de Olavide University, of Seville  (UPO)  -  Website

Sometimes the solution of set a network connecting different places (agents) are provided by seeking higher capacity in their connections instead of lower cost or times. In those cases, the routes will be settled looking for certain capacity. In a maximum capacity network problem, it is assumed that the network to be built has minimum capacity requirements between the agents that will be connected. The capacity demands between each pair of agents are known and the minimum cost of establishing the capacity network is sought. The solution to this problem lays in the construction of a maximum cost spanning tree that connects all the agents with their required capacity. The objective of this work is not only to describe the trees which solve the problem but also to share the network cost between the agents. Thus, we present a set of algorithms that generate maximum cost spanning trees and produce different allocations of the costs. When these allocations are analysed from the point of view of Game Theory, it will be concluded that they are optimal both from the cooperative and the non-cooperative approach. As a consequence, using the introduced algorithms, a large set of solutions are achieved. And, in the Game Theory framework, these solutions are in the Core of a certain Cooperative Game and are Nash-Equilibrium of a related Non Cooperative Game.

Online user: 1 RSS Feed