Designing Networks with Low Structural Congestion via Game Theory and Linear Programming
DOI:
https://doi.org/10.14738/tnc.31.795Keywords:
Communication network, Game theory, Linear programmingAbstract
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.
References
. Nahir, A., et al. Topology Design of Communication Networks: A Game-Theoretic Perspective. IEEE/ACM Trans. Netw. 22(2): (2014) 405-414.
. Page Jr, F. H., et al. Strategic basins of attraction, the path dominance core, and network formation games. Games and Economic Behavior 66.1 (2009): 462-487.
. Jackson, M., et al. On the formation of interaction networks in social coordination games. Games and Economic Behavior 41.2 (2002): 265-291.
. Aumann, R., ., et al. Endogenous formation of links between players and coalitions: an application of the Shapley value. The Shapley Value(1988): 175-191.
. Fotakis, D., et al. The structure and complexity of Nash equilibria for a selfish routing game. Theoretical Computer Science 410.36 (2009): 3305-3326.
. Fang, Z., ., et al. Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. Vol. 2. IEEE, 2004.
. Ji, Z., et al. Cognitive radios for dynamic spectrum access-dynamic spectrum sharing: A game theoretical overview. Communications Magazine, IEEE 45.5 (2007): 88-94.
. Wang, Y., et al. Internet traffic engineering without full mesh overlaying. INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 1. IEEE, 2001.
. Varol, Y., et al. An algorithm to generate all topological sorting arrangements. The Computer Journal 24.1 (1981): 83-84.
. Roughgarden, T. Selfish routing and the price of anarchy. Vol. 174. Cambridge: MIT press, 2005.
. Awerbuch, B., et al. Approximate distributed bellman-ford algorithms. Communications, IEEE Transactions on 42.8 (1994): 2515-2517.
. G. Debreu, A social equilibrium existence theorem, Proc. Nat. Acad. Sci., vol. 38, pp. 886–893, Oct. 1952.
. Koutsoupias, E., et al. Worst-case equilibria. STACS 99. Springer Berlin Heidelberg, 1999.
