Bio-inspired paradigms in network engineering games

Eitan Altman

doi:10.3934/jdg.2014.1.1

Article Contents

2014, Volume 1, Issue 1: 1-15. Doi: 10.3934/jdg.2014.1.1

This issue Previous Article Next Article Collective attention and ranking methods

Bio-inspired paradigms in network engineering games

Eitan Altman^1,

1.
INRIA Sophia-Antipolis, 2004 Route des Lucioles, 06906, Sophia-Antipolis

Received: March 31, 2012

Revised: May 31, 2012

Published: December 2013

Abstract Related Papers Cited by

Abstract

Network Engineering Games (NEGs) is an emerging branch of game theory developed in Electrical Engineering Departments. It concerns games that arise in all levels of telecommunication networks. There has been a growing interest among researchers in this community in bio-inspired methodologies in recent years due to two reasons. First, many problems in networking have much in common with problems in biology. Examples are (i) propagation of information in networks, that has similar dynamics as propagation of epidemics; (ii) energy management issues in wireless networks and competition over resources are often similar to issues by biologists; (iii) both equilibria concepts as well as replicator dynamics that arise in evolutionary games are quite relevant to NEGs. In this paper we present an overview of applications and tools used in network engineering games, we then describe in more depth bio-inspired tools used in or relevant to network engineering. We present finally an example of a stochastic epidemic game arising in wireless networks that involves competition over the relaying of information.

Keywords:

Networking engineering game,
bio-inspired.

Mathematics Subject Classification: Primary: 91A25, 91A80; Secondary: 91D30.

Citation:

Related Papers

Cited by

References

[1]	T. Alpcan and T. Başar, "Network Security. A Decision and Game-Theoretic Approach," Cambridge University Press, Cambridge, 2011.
[2]	E. Altman, "Constrained Markov Decision Processes. Stochastic Modeling," Chapman & Hall/CRC, Boca Raton, FL, 1999.
[3]	E. Altman, R. El Azouzi and V. Abramov, Non-cooperative routing in loss networks, Performance Evaluation, 49 (2002), 257-272.doi: 10.1016/S0166-5316(02)00112-8.
[4]	E. Altman, T. Boulogne, R. El-Azouzi, T. Jiménez and L. Wynter, A survey on networking games in telecommunications, Computers and Operations Research, 33 (2006), 286-311.doi: 10.1016/j.cor.2004.06.005.
[5]	E. Altman and R. El-Azouzi, La théorie des jeux non-coopératifs appliquée aux réseaux de télécommunication, (in French) Annales des Télécommunications, (2007).
[6]	E. Altman and L. Wynter, Equilibrium, games, and pricing in transportation and telecommunications networks, Networks and Spatial Economics, 4 (2004), 7-21.doi: 10.1023/B:NETS.0000015653.52983.61.
[7]	Eitan Altman, A stochastic game approach for competition over popularity in social networks, Dynamic Games and Applications, online publication, (2012). Available from: http://hal.inria.fr/hal-00681959.doi: 10.1007/s13235-012-0057-4.
[8]	Eitan Altman and Yezekael Hayel, Markov decision evolutionary games, IEEE Transactions on Automatic Control, 55 (2010), 1560-1569.doi: 10.1109/TAC.2010.2042230.
[9]	J. Aspnes, K. Chang and A. Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, J. Comput. Syst. Sci., 72 (2006), 1077-1093.doi: 10.1016/j.jcss.2006.02.003.
[10]	J. Aspnes, N. Rustagi and J. Saia, Worm versus alert: Who wins in a battle for control of a large-scale network?, Lecture Notes in Computer Science, 4878 (2007), 443-456.doi: 10.1007/978-3-540-77096-1_32.
[11]	C. T. Bauch, Imitation dynamics predict vaccinating behavior, Proc. of The Royal Society, (2005).doi: 10.1098/rspb.2005.3153.
[12]	C. T. Bauch and D. J. D. Earn, Vaccination and the theory of games, Proceedings of the National Academy of Science, 101 (2004), 13391-13394.doi: 10.1073/pnas.0403823101.
[13]	N. G. Beans, F. P. Kelly and P. G. Taylor, Braess's paradox in a loss network, J. Appl. Prob., 34 (1997), 155-159.doi: 10.2307/3215183.
[14]	M. Beckmann, C. B. McGuire and C. B. Winsten, "Studies in the Economics of Transportation," Yale Univ. Press, New Haven, 1956.
[15]	T. Berger, The source coding game, IEEE Trans. on Inform. Theory, IT-17 (1971), 71-76.
[16]	N. M. Blachman, Communication as a game, in "I.R.E. WESCON Convention Record Part 2" (August 1957), 61-66.
[17]	D. Braess, Über ein Paradoxien aus der Verkehrsplanung, (German) Unternehmensforschung, 12 (1968), 258-268.
[18]	Mung Chiang, Chee Wei Tan, Prashanth Hande and Tian Lan, Power control in wireless cellular networks, Foundations and Trends in Networking, 2 (2007), 381-533.doi: 10.1561/1300000009.
[19]	S. Coraluppi and S. I. Marcus, Risk-sensitive queueing, in "Proc. 35^th Annual Allerton Conf. on Communication, Control, and Computing," Urbana, IL, USA, September 28-October 1, 1997.
[20]	Merouane Debbah and Samson Lasaulce, "Game Theory for Wireless Networks: From Fundamentals to Practice," Elsevier Science & Technology, 2011.
[21]	C. Douligeris, "Optimal Flow Control and Fairness in Communication Networks: A Game Theoretic Perspective," Ph.D. Dissertation, Electrical Engineering, Columbia University, 1989.
[22]	T. Ericson, The noncooperative binary adder channel, IEEE Trans. on Inform. Theory, 32 (1986), 365-374.doi: 10.1109/TIT.1986.1057190.
[23]	D. Falomari, N. Mandayam and D. Goodman, A new framework for power control in wireless data networks: Games utility and pricing, in "Proc. Allerton Conference on Communication, Control and Computing," Champaign, Illinois, USA, (1998), 546-555.
[24]	C. Frenzel, H. Sanneck and S. Hamalainen, "LTE Self-Organising Networks (Son): Network Management Automation for Operational Efficiency," John Wiley & Sons, 2011.
[25]	A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equilibria, Networks, 15 (1985), 295-308.doi: 10.1002/net.3230150303.
[26]	M. T. Hsiao and A. A. Lazar, A game theoretic approach to decentralized flow control of Markovian queueing networks, in "Performance '87" (Brussels, 1987), North-Holland, Amsterdam, (1988), 55-73.
[27]	M. T. Hsiao and A. A. Lazar, Optimal decentralized flow control of Markovian queueing networks with multiple controllers, Performance Evaluation, 13 (1991), 181-204.doi: 10.1016/0166-5316(91)90054-7.
[28]	M. H. R. Khouzani, Saswati Sarkar and Eitan Altman, Saddle-point strategies in malware attack, IEEE Journal on Selected Areas in Communications, 30 (2012), 31-43.doi: 10.1109/JSAC.2012.120104.
[29]	Man-Tung Tony Hsiao, "Optimal Decentralized Flow Control in Computer Communication Networks," Ph.D. Thesis, EE, Columbia Univ, October, 1986.
[30]	Anna Jaśkiewicz, A note on negative dynamic programming for risk-sensitive control, Operations Research Letters, 36 (2008), 531-534.doi: 10.1016/j.orl.2008.03.003.
[31]	Hongbin Ji and Ching-Yao Huang, Non-cooperative uplink power control in cellular radio systems, Wireless Networks, 4 (1998), 233-240.
[32]	B. Jovanovic and R. W. Rosenthal, Anonymous sequential games, Journal of Mathematical Economics, 17 (1988), 77-87.doi: 10.1016/0304-4068(88)90029-8.
[33]	S. Lasaulce and H. Tembine, "Game Theory and Learning for Wireless Networks," Fundamentals and Applications, Academic Press, 2011.
[34]	S. A. Lippman, Applying a new device in the optimization of exponential queueing systems, Operations Research, 23 (1975), 687-710.doi: 10.1287/opre.23.4.687.
[35]	Allen Mackenzie and Luiz DaSilva, "Game Theory for Wireless Engineers," Synthesis Lectures on Communications, Morgan & Claypool Publishers, 2006.doi: 10.2200/S00014ED1V01Y200508COM001.
[36]	R. Mazumdar, L. G. Mason and C. Douligeris, Fairness in network optimal flow control: Optimality of product forms, IEEE Trans. on Comm., 39 (1991), 775-782.doi: 10.1109/26.87140.
[37]	I. Menache and A. Ozdaglar, "Network Games: Theory, Models, and Dynamics," Synthesis Lectures on Communication Networks, Morgan & Claypool Publishers, 2011.doi: 10.2200/S00330ED1V01Y201101CNT009.
[38]	I. Milchtaich, Congestion games with player-specific payoff functions, Games and Economic Behavior, 13 (1996), 111-124.doi: 10.1006/game.1996.0027.
[39]	W. Murrey, The application of epidemiology to computer viruses, Comp. Security, 7 (1988), 139-150.
[40]	Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani, eds., "Algorithmic Game Theory," Cambridge University Press, Cambridge, 2007.doi: 10.1017/CBO9780511800481.
[41]	A. Orda, R. Rom and N. Shimkin, Competitive routing in multi-user communication networks, in "INFOCOM '93. Proceedings. Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking: Foundation for the Future" (San Francisco, CA), IEEE, (1993), 964-971.doi: 10.1109/INFCOM.1993.253270.
[42]	M. Patriksson, "The Traffic Assignment Problem: Models and Methods," VSP BV, P.O. Box 346, 3700 AH Zeist, The Netherlands, 1994.
[43]	R. W. Rosenthal, A class of games possessing pure strategy Nash equilibria, Int. J. Game Theory, 2 (1973), 65-67.doi: 10.1007/BF01737559.
[44]	R. W. Rosenthal, The network equilibrium problem in integers, Networks, 3 (1973), 53-59.doi: 10.1002/net.3230030104.
[45]	William H. Sandholm, "Population Games and Evolutionary Dynamics," Economic Learning and Social Evolution, MIT Press, Cambridge, MA, 2010.
[46]	J. Maynard Smith, Game theory and the evolution of fighting, in "On Evolution" (J. Maynard Smith), Edinburgh University Press, Edinburgh, (1972), 8-28.
[47]	Hamidou Tembine, Eitan Altman, Rachid El-Azouzi and Yezekael Hayel, Evolutionary games in wireless networks, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 40 (2010), 634-646.doi: 10.1109/TSMCB.2009.2034631.
[48]	Hamidou Tembine, Eitan Altman, Rachid El-Azouzi and Yezekael Hayel, Bio-inspired delayed evolutionary game dynamics with networking applications, Telecommunication Systems, 47 (2011), 137-152.doi: 10.1007/s11235-010-9307-1.
[49]	D. C. Trimble, "A Game-Theoretic Approach to Signal and Receiver Design," Ph.D. Thesis, Nov. 1972.doi: 10.1109/TIT.1972.1054913.
[50]	T. L. Vincent and J. S. Brown, "Evolutionary Game Theory, Natural Selection, and Darwinian Dynamics," Cambridge Univ Press, 2005.
[51]	J. G. Wardrop, Some theoretical aspects of road traffic research communication networks, Proc. Inst. Civ. Eng., Part 2, 1 (1952), 325-378.
[52]	Y. Zhang and M. Guizani, "Game Theory for Wireless Commun. and Networking," CRC, 2011.
[53]	Yan Zhang and Mohsen Guizani, "Game Theory for Wireless Communications and Networking," Taylor and Francis, 2010.
[54]	I. Ziedins, A paradox in a queueing network with state-dependent routing and loss, Journal of Applied Mathematics and Decision Sciences, 2007 (2007), Article ID 68280, 10 pp.doi: 10.1155/2007/68280.