Designing Networks with Low Structural Congestion via Game Theory and Linear Programming - Askarian, Ahmad; Farago, Andras (Discoveries in Agriculture and Food Sciences, 2015)
We propose a network topology design approach that targets the reduction of structural congestion in a directed acyclic network. What we mean by structural congestion is that a node has much higher in-degree than out-degree in a directed network. We approach the issue using a network design game model. In this model we consider multiple sources and one destination. Each node is willing to connect to other nodes but it should pay the price of whole paths it uses to send traffic to the destination. The model yields a weight for each link. We show that if these weights are used to compute shortest paths, then a network topology is obtained with a low level of structural congestion. The proposed method has two phases. In Phase I, we solve a linear optimization problem in order to find the optimum link weights. In Phase II, each node optimizes its own individual objective function, which is based on the weights computed in Phase I. We show that there exists a Nash Equilibrium which is also the global optimum. In order to measure the penalty incurred by the selfish behavior of nodes, we use the concept called price of anarchy. Our results show that the price of anarchy is zero.