Mô hình lý thuyết trò chơi cho giao tiếp giữa các tác nhân: một cái nhìn tổng quan

Springer Science and Business Media LLC - Tập 4 - Trang 1-31 - 2016
Aisha D. Farooqui1, Muaz A. Niazi2
1Software Engineering Department, Bahria University, Islamabad, Pakistan
2Computer Science Department, COMSATS Institute of IT, Islamabad, Pakistan

Tóm tắt

Trong thế giới thực, các tác nhân hay thực thể luôn ở trong trạng thái tương tác liên tục. Những tương tác này dẫn đến nhiều loại động lực phức tạp. Một trong những khó khăn chính trong việc nghiên cứu các tương tác phức tạp giữa các tác nhân là việc mô hình hóa giao tiếp giữa các tác nhân dựa trên phần thưởng. Lý thuyết trò chơi cung cấp một góc nhìn để phân tích và mô hình hóa những tương tác này. Trước đây, mặc dù có nhiều tài liệu về lý thuyết trò chơi, phần lớn chúng đều đến từ các lĩnh vực cụ thể và không phù hợp với các khái niệm từ góc nhìn dựa trên tác nhân. Ở đây, trong bài báo này, chúng tôi trình bày một bài tổng quan toàn diện và phân loại hiện đại về các mô hình lý thuyết trò chơi cho các tương tác phức tạp giữa các tác nhân.

Từ khóa

#lý thuyết trò chơi #giao tiếp #tác nhân #tương tác phức tạp #mô hình hóa

Tài liệu tham khảo

Abu-Khalaf M, Lewis FL, Huang J (2008) Neurodynamic programming and zero-sum games for constrained control systems. IEEE Trans Neural Netw 19(7):1243–1252 Ahmad I, Luo J (2006) On using game theory to optimize the rate control in video coding. IEEE Trans Circuits Syst Video Technol 16(2):209–219 Al-Tamimi A, Abu-Khalaf M, Lewis FL (2007) Adaptive critic designs for discrete-time zero-sum games with application to control. IEEE Trans Syst Man Cybern Part B Cybern 37(1):240–247 Al-Tamimi A, Lewis FL, Abu-Khalaf M (2007) Model-free q-learning designs for linear discrete-time zero-sum games with application to h-infinity control. Automatica 43(3):473–481 Alpcan T, Buchegger S (2011) Security games for vehicular networks. IEEE Trans Mobile Comput 10(2):280–290 Altman E (1994) Flow control using the theory of zero sum Markov games. IEEE Trans Autom Control 39(4):814–818 Altman E, Avrachenkov K, Bonneau N, Debbah M, El-Azouzi R, Menasche DS (2008) Constrained cost-coupled stochastic games with independent state processes. Oper Res Lett 36:160–164 Athey S (2001) Single crossing properties and the existence of pure strategy equilibria in games of incomplete information. Econometrica 69(4):861–889 Aumann RF, Maschler M, Stearns RE (1995) Repeated games with incomplete information. MIT press, Cambridge Bahel E, Haller H (2013) Cycles with undistinguished actions and extended rock-paper-scissors games. Econ Lett 120(3):588–591 Batt C (1999) Rock, paper, scissors. Food Microbiol 16(1):1 Bell MGF (2003) The use of game theory to measure the vulnerability of stochastic networks. IEEE Trans Reliab 52(1):63–68 Bell MGH, Fonzone A, Polyzoni C (2014) Depot location in degradable transport networks. Transp Res Part B Methodol 66:148–161 Belmega EV, Lasaulce S, Debbah M (2009) Power allocation games for mimo multiple access channels with coordination. IEEE Trans Wirel Commun 8(6):3182–3192 Bensoussan A, Siu CC, Yam SCP, Yang H (2014) A class of non-zero-sum stochastic differential investment and reinsurance games. Automatica 50(8):2025–2037 Bettiol P, Cardaliaguet P, Quincampoix M (2006) Zero-sum state constrained differential games: existence of value for Bolza problem. Int J Game Theory 34(4):495–527 Böge W, Eisele T (1979) On solutions of Bayesian games. Int J Game Theory 8(4):193–215 Bonabeau E (2002) Agent-based modeling: methods and techniques for simulating human systems. Proc Natl Acad Sci USA 99(suppl 3):7280–7287 Bopardikar SD, Borri A, Hespanha JP, Prandini M, Di Benedetto MD (2013) Randomized sampling for large zero-sum games. Automatica 49(5):1184–1194 Carlson LJ, Wilson PI (2004) Beyond zero-sum: game theory and national forest management. Soc Sci J 41(4):637–650 Carmichael F (2005) A guide to game theory. Pearson Education, New York Chang HS, Marcus SI (2003) Two-person zero-sum markov games: receding horizon approach. IEEE Trans Autom Control 48(11):1951–1961 Chen YW, Larbani M (2006) Two-person zero-sum game approach for fuzzy multiple attribute decision making problems. Fuzzy Sets Syst 157(1):34–51 Chen Y, Liu KJ (2012) Understanding microeconomic behaviors in social networking: an engineering view. IEEE Signal Process Mag 29(2):53–64 Chen MH, Lin SC, Hong YW, Zhou X (2013) On cooperative and malicious behaviors in multirelay fading channels. IEEE Trans Inf Forensics Secur 8(7):1126–1139 Daskalakis C, Deckelbaum A, Kim A (2015) Near-optimal no-regret algorithms for zero-sum games. Games Econ Behav 92:327–348 Deshmukh SD, Winston W (1978) A zero-sum stochastic game model of duopoly. Int J Game Theory 7(1):19–30 Dixit AK, Nalebuff BJ (1993) Thinking strategically: the competitive edge in business, politics, and everyday life. WW Norton & Company, New York City Dixit AK, Skeath S (1999) Games of strategy. Norton, New York Duersch P, Oechssler J, Schipper BC (2012) Pure strategy equilibria in symmetric two-player zero-sum games. Int J Game Theory 41(3):553–564 Edmonds J, Pruhs K (2006) Balanced allocations of cake. In: Null, IEEE, New York, p 623–634 Epstein JM (2008) Why model? J Artif Soc Soc Simul 11(4):12 Feldman AM (1973) Bilateral trading processes, pairwise optimality, and pareto optimality. Rev Econ Stud 40(4):463–473 Frey S, Goldstone RL, Szolnoki A (2013) Cyclic game dynamics driven by iterated reasoning. PloS one 8(2):e56416 Gawlitza TM, Seidl H, Adjé A, Gaubert S, Goubault É (2012) Abstract interpretation meets convex optimization. Journal Symb Comput 47(12):1416–1446 Geckil IK, Anderson PL (2009) Applied game theory and strategic behavior. CRC Press, Boca Raton Gensbittel F (2014) Extensions of the cav (u) theorem for repeated games with incomplete information on one side. Math Oper Res 40(1):80–104 Gharesifard B, Cortes J (2013) Distributed convergence to Nash equilibria in two-network zero-sum games. Automatica 49(6):1683–1692 Ghosh MK, Goswami A (2008) Partially observed semi-Markov zero-sum games with average payoff. J Math Anal Appl 345(1):26–39 Grauberger W, Kimms A (2014) Computing approximate nash equilibria in general network revenue management games. Eur J Oper Res 237(3):1008–1020 Guesnerie R (1975) Pareto optimality in non-convex economies. Econom J Econom Soc 1–29 Gul F (1989) Bargaining foundations of shapley value. Econom J Econom Soc 81–95 Hamadène S, Wang H (2009) BSDEs with two RCLL reflecting obstacles driven by Brownian motion and poisson measure and a related mixed zero-sum game. Stoch Process Appl 119(9):2881–2912 Hand JL (1986) Resolution of social conflicts: dominance, egalitarianism, spheres of dominance, and game theory. Q Rev Biol 201–220 Hart S (2008) Discrete colonel blotto and general lotto games. Int J Game Theory 36(3–4):441–460 Hart S, Modica S, Schmeidler D (1994) A neo2 Bayesian foundation of the maxmin value for two-person zero-sum games. Int J Game Theory 23(4):347–358 Hellman Z (2013) Weakly rational expectations. J Math Econ 49(6):496–500 Hernandez-Hernandez D, Simon RS, Zervos M et al (2015) A zero-sum game between a singular stochastic controller and a discretionary stopper. Ann Appl Probab 25(1):46–80 Hofbauer J, Sigmund K (1998) Evolutionary games and population dynamics. Cambridge University Press, Cambridge Hu J, Wellman MP (2003) Nash q-learning for general-sum stochastic games. J Mach Learn Res 4:1039–1069 Hutton W (1996) The state we are in London: Vintage Isaaks R (1952) A mathematical theory with applications to warfare and pursuit, control, and optimization. Wiley, New York Kacem I, Hammadi S, Borne P (2002) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Computers Simul 60(3):245–276 Kashyap A, Basar T, Srikant R (2004) Correlated jamming on MIMO Gaussian fading channels. IEEE Trans Inf Theory 50(9):2119–2123 Khosravifar B, Bentahar J, Mizouni R, Otrok H, Mahsa Alishahi, Philippe Thiran (2013) Agent-based game-theoretic model for collaborative web services: decision making analysis. Expert Syst Appl 40(8):3207–3219 Khouzani MHR, Sarkar S, Altman E (2012) Saddle-point strategies in malware attack. IEEE J Sel Areas Commun 30(1):31–43 Kilgour DM, Fraser NM (1988) A taxonomy of all ordinal 2\(\times\) 2 games. Theory Decis 24(2):99–117 Lansing JS (2003) Complex adaptive systems. Annu Rev Anthropol 183–204 Laraki R, Maitra AP, Sudderth WD (2013) Two-person zero-sum stochastic games with semicontinuous payoff. Dyn Games Appl 3(2):162–171 Larsson EG, Jorswieck EA, Lindblom J, Mochaourab R et al (2009) Game theory and the flat-fading gaussian interference channel. IEEE Signal Process Mag 26(5):18–27 Li D, Cruz JB (2009) Information, decision-making and deception in games. Decis Support Syst 47(4):518–527 Littlechild SC, Owen G (1973) A simple expression for the shapley value in a special case. Manag Sci 20(3):370–372 Liu D, Li H, Wang D (2013) Neural-network-based zero-sum game for discrete-time nonlinear systems via iterative adaptive dynamic programming algorithm. Neurocomputing 110:92–100 Maeda T (2003) On characterization of equilibrium strategy of two-person zero-sum games with fuzzy payoffs. Fuzzy Sets Syst 139(2):283–296 Marlow J, Peart DR (2014) Experimental reversal of soil acidification in a deciduous forest: implications for seedling performance and changes in dominance of shade-tolerant species. For Ecol Manag 313:63–68 Mazalov V (2014) Mathematical game theory and applications. Wiley, New York McCabe KA, Mukherji A, Runkle DE (2000) An experimental study of information and mixed-strategy play in the three-person matching-pennies game. Econ Theory 15(2):421–462 McDaniel RR, Driebe DJ (2001) Complexity science and health care management. Adv Health Care Manag 2(S11):37 Méndez-Naya L (1996) Zero-sum continuous games with no compact support. Int J Game Theory 25(1):93–111 Mertens JF, Neyman A (1981) Stochastic games. Int J Game Theory 10(2):53–66 Mertens JF, Zamir S (1971) The value of two-person zero-sum repeated games with lack of information on both sides. Int J Game Theory 1(1):39–64 Mitchell M (2009) Complexity: a guided tour. Oxford University Press, New York Morrow JD (1994) Game theory for political scientists. Princeton University Press, Princeton Moulin H (1976) Extensions of two person zero sum games. J Math Anal Appl 55(2):490–508 Moulin H, Vial J-P (1978) Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. Int J Game Theory 7(3–4):201–221 Mussa M (2002) The euro versus the dollar: not a zero sum game. J Policy Model 24(4):361–372 Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162 Nash J (1951) Non-cooperative games. Ann Math 286–295 Neumann G, Schuster S (2007) Continuous model for the rock-scissors-paper game between bacteriocin producing bacteria. J Math Biol 54(6):815–846 Nguyen PH, Kling WL, Ribeiro PF (2013) A game theory strategy to integrate distributed agent-based functions in smart grids. IEEE Trans Smart Grid 4(1):568–576 Niazi M, Hussain A (2011) Agent-based computing from multi-agent systems to agent-based models: a visual survey. Scientometrics 89(2):479–499 Niazi M, Hussain A et al (2011) A novel agent-based simulation framework for sensing in complex adaptive environments. IEEE Sens J 11(2):404–412 Niazi MA, Hussain A (2012) Cognitive agent-based computing-I: a unified framework for modeling complex adaptive systems using agent-based & complex network-based methods. Springer, Dordecht Okamura K, Kanaoka T, Okada T, Tomita S (1984) Learning behavior of variable-structure stochastic automata in a three-person zero-sum game. IEEE Trans Syst Man Cybern 6:924–932 Oliu-Barton M (2014) The asymptotic value in finite stochastic games. Math Oper Res 39(3):712–721 Parsons S, Wooldridge M (2002) Game theory and decision theory in multi-agent systems. Auton Agents Multiagent Syst 5(3):243–254 Perea F, Puerto J (2013) Revisiting a game theoretic framework for the robust railway network design against intentional attacks. Eur J Oper Res 226(2):286–292 Pérez-Castrillo D, Wettstein D (2001) Bidding for the surplus: a non-cooperative approach to the shapley value. J Econ Theory 100(2):274–294 Pham T, Zhang J (2014) Two person zero-sum game in weak formulation and path dependent Bellman–Isaacs equation. SIAM J Control Optim 52(4):2090–2121 Ponssard J-P (1975) A note on the lp formulation of zero-sum sequential games with incomplete information. Int J Game Theory 4(1):1–5 Ponssard J-P (1976) On the subject of non optimal play in zero sum extensive games: “the trap phenomenon”. Int J Game Theory 5(2–3):107–115 Ponssard JP, Sorin S (1980) Some results on zero-sum games with incomplete information: the dependent case. Int J Game Theory 9(4):233–245 Porter R, Nudelman E, Shoham Y (2008) Simple search methods for finding a Nash equilibrium. Games Econ Behav 63(2):642–662 Procaccia AD (2013) Cake cutting: not just child’s play. Commun ACM 56(7):78–87 Qing-Lai WEI, Zhang HG, Li-Li CUI (2009) Data-based optimal control for discrete-time zero-sum games of 2-d systems using adaptive critic designs. Acta Autom Sin 35(6):682–692 Quer G, Librino F, Canzian L, Badia L, Zorzi M (2013) Inter-network cooperation exploiting game theory and Bayesian networks. IEEE Trans Commun 61(10):4310–4321 Radzik T (1991) Pure-strategy \(\varepsilon\)-Nash equilibrium in two-person non-zero-sum games. Games Econ Behav 3(3):356–367 Radzik T (1993) Nash equilibria of discontinuous non-zero-sum two-person games. Int J Game Theory 21(4):429–437 Rapoport A, Guyer M (1978) A taxonomy of 2x2 games. Gen Syst 23:125–136 Roberson B (2006) The colonel blotto game. Econ Theory 29(1):1–24 Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2(1):65–67 Rosenthal RW (1974) Correlated equilibria in some classes of two-person games. Int J Game Theory 3(3):119–128 Roughgarden T (2010) Algorithmic game theory. Commun ACM 53(7):78–86 Sauder DW, Geraniotis E (1994) Signal detection games with power constraints. IEEE Trans Inf Theory 40(3):795–807 Semsar-Kazerooni E, Khorasani K (2009) Multi-agent team cooperation: a game theory approach. Automatica 45(10):2205–2213 Seo H, Lee D (2007) Temporal filtering of reward signals in the dorsal anterior cingulate cortex during a mixed-strategy game. J Neurosci 27(31):8366–8377 Shah IA, Jan S, Khan I, Qamar S (2012) An overview of game theory and its applications in communication networks. Int J Multidiscip Sci Eng 3:5–11 Shapley LS (1953) A value for n-person games. Contrib Theory Games 2:307–317 Shenoy PP, Yu PL (1981) Inducing cooperation by reciprocative strategy in non-zero-sum games. J Math Anal Appl 80(1):67–77 Shmaya E (2006) The value of information structures in zero-sum games with lack of information on one side. Int J Game Theory 34(2):155–165 Shoham Y, Leyton-Brown K (2008) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press, New York Sinervo B, Lively CM (1996) The rock-paper-scissors game and the evolution of alternative male strategies. Nature 380(6571):240–243 Singh VV, Hemachandra N (2014) A characterization of stationary Nash equilibria of constrained stochastic games with independent state processes. Oper Res Lett 42(1):48–52 Sirbu M (2014) On martingale problems with continuous-time mixing and values of zero-sum games without the Isaacs condition. SIAM J Control Optim 52(5):2877–2890 Socolar JES (2006) Nonlinear dynamical systems. In: Complex systems science in biomedicine. Springer, New York, pp 115–140 Sorin S (2011) Zero-sum repeated games: recent advances and new links with differential games. Dyn Games Appl 1(1):172–207 Southey F, Hoehn B, Holte RC (2009) Effective short-term opponent exploitation in simplified poker. Mach Learn 74(2):159–189 Spyridopoulos T (2013) A game theoretic defence framework against DoS/DDoS cyber attacks. Comput Secur 38:39–50 Stein ND, Ozdaglar A, Parrilo PA (2010) Structure of extreme correlated equilibria: a zero-sum example and its implications. arXiv preprint arXiv:1002.0035 Sullivan R, Purushotham AD (2011) Avoiding the zero sum game in global cancer policy: beyond 2011 un high level summit. Eur J Cancer 47(16):2375–2380 Tan CK, Chuah TC, Tan SW (2011) Fair subcarrier and power allocation for multiuser orthogonal frequency-division multiple access cognitive radio networks using a colonel Blotto game. IET Commun 5(11):1607–1618 Tucker AW (1959) Contributions to the theory of games, vol 4. Princeton University Press, Princeton Venkitasubramaniam P, Tong L (2012) A game-theoretic approach to anonymous networking. IEEE/ACM Trans Netw 20(3):892–905 Von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton Wang J, Chen F (2013) Feedback saddle point solution of counterterror measures and economic growth game. Oper Res Lett 41(6):706–709 Wang T, Georgios GB (2008) Mutual information jammer-relay games. IEEE Trans Inf Forensics Secur 3(2):290–303 Washburn AR (2003) Two-person zero-sum games. Springer, Berlin Wei S, Kannan R, Chakravarthy V, Rangaswamy M (2012) Csi usage over parallel fading channels under jamming attacks: a game theory study. IEEE Trans Commun 60(4):1167–1175 Wilson DJ (1972) Isaacs’ princess and monster game on the circle. J Optim Theory Appl 9(4):265–288 Winsberg E (2001) Simulations, models, and theories: complex physical systems and their representations. Philos Sci 68(3):S442–S454. http://www.jstor.org/stable/3080964 Wooldridge M (2009) An introduction to multiagent systems. Wiley, West Sussex Wooldridge M (2012) Does game theory work? IEEE Intell Syst 27(6):76–80 Wu HN, Luo B (2013) Simultaneous policy update algorithms for learning the solution of linear continuous-time hinfin state feedback control. Inf Sci 222:472–485 Xu H, Mizukami K (1994) Linear-quadratic zero-sum differential games for generalized state space systems. IEEE Trans Autom Control 39(1):143–147 Ye Y, Lu NG, Cen YW (2013) The multi-agent Parrondo’s model based on the network evolution. Phys A Stat Mech Appl 392(21):5414–5421 Yeung DWK, Petrosjan LA (2006) Cooperative stochastic differential games. Springer Science & Business Media, Berlin Van Zandt T, Zhang K (2011) A theorem of the maximin and applications to Bayesian zero-sum games. Int J Game Theory 40(2):289–308 Zhang X, Zhang H, Wang X, Luo Y (2011) A new iteration approach to solve a class of finite-horizon continuous-time nonaffine nonlinear zero-sum game. Int J Innov Comput Inf Control 7(2):597–608 Zhao L, Zhang J, Zhang H (2008) Using incompletely cooperative game theory in wireless mesh networks. IEEE Netw 22(1):39–44 Zhou X, Niyato D, Hjørungnes A (2011) Optimizing training-based transmission against smart jamming. IEEE Trans Veh Technol 60(6):2644–2655 Zoroa N, Fernández-Sáez MJ, Zoroa P (2012) Patrolling a perimeter. Eur J Oper Res 222(3):571–582