تعیین نقطه تعادل در بازی های نرمال مارکفی گسسته دو نفره

نوع مقاله : مقاله پژوهشی

نویسنده

دانشیار گروه مهندسی صنایع، دانشگاه پیام نور

چکیده

ترکیبی از دو یا چند استراتژی که در ابتدا مدنظر یک بازیکن نبوده است می تواند در مراحل بعدی مدنظر آن بازیکن قرار گیرد. در این مقاله نوعی از بازی ها با نام بازی های مارکفی معرفی می گردند که چنانچه استراتژی های هر بازیکن را به عنوان یک حالت درنظر بگیرید که در مرحله بعدی با توجه به شرایط و موقعیت، همان بازیکن ممکن است همان استراتژی یا استراتژی دیگری را با احتمالی مشخص انتخاب نماید که این انتخاب می تواند بستگی به استراتژی بازیکنان رقیب داشته باشد. در این تحقیق یک بازی نرمال دونفره گسسته با رویکرد زنجیره مارکف درنظر گرفته می شود که احتمالات انتقال از قبل مشخص شده و مستقل بوده و فقط تحت تاثیر استراتژی های قبلی بازیکن رقیب می باشد. در این مقاله نحوه تعیین نقاط تعادل تحت این شرایط مورد ارزیابی و تحلیل قرار می گیرد. یک مثال عددی نیز جهت تشریح بیشتر فرآیند ارائه می گردد.

کلیدواژه‌ها


عنوان مقاله [English]

Determining the Equilibrium Solution in Two-Player Static Discrete Markovian Games

نویسنده [English]

  • Ramin Sadeghian
Associate Professor, Department of Industrial Engineering, Payame Noor University
چکیده [English]

A mix of two or more strategies can be more helpful for players in future. This article introduces a series of games called Markovian Dynamic Games that if you consider the strategies of each player as a state, the player can select the same or another state depending on the situation in the next steps. The selecting each state in each step will be done with a specified probability. This probability is depending on the strategies of the competing players. In this study, a static two-player discrete game with Markov chain approach is considered that the probability of transfer is well-known, independent and is only influenced by the competitor's previous strategies. In this paper, the equilibrium points in markovian static games are evaluated and analyzed. Numerical examples are also presented for more explanations. In this paper, the difference between single-stage and multi-stage games in determining equilibrium points is shown. If a game is played in a multilevel manner, it is possible to design a discrete game as a Markov chain using the probability of transferring and considering the strategies of the game as a mode in each step, and by determining the probabilities of the specified chain, points He gained some balance. For this purpose, static games were considered. One of the most important advantages of using the Markov chain to determine the limit equilibrium point is to find this point in the shortest time and with the least available calculations.

کلیدواژه‌ها [English]

  • Markovian Static Game
  • Multi-Stage Game
  • Markov Chain
  • Transition Probability Matrix
[1]    Asgharpour Mohammad Javad, (2003), Group Decision Making and Game Thory: an Approach on Operations Research, Samt Press, Tehran University, Tehran, Iran, (In Persian).
[2]    Krawczyk Jacek B. and Petkov Vladimir, Multistage Games, Handbook of Dynamic Game Theory, Springer International Publishing AG, 2016.
[3]    Myerson B. Roger, Multistage Games with Communication, Econometrica, March 1986, Vol. 54, No. 2, pp. 323-358.
[4]    Littman L. Michael, Value-function reinforcement learning in Markov games, 2001, Journal of Cognitive Systems Research, Vol. 2, 2001, pp. 55–66.
[5]    Vrancx Peter, Decentralised Reinforcement Learning in Markov Games, 2010, Dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Sciences, Brussel University, Brussels, Belgium.
[6]    Osborne J. Martin, An introduction to Game Theory, 2000, Oxford University Press, Oxford, UK.
[7]    Finus Michael, Game theory and international environmental cooperation, 2001, Edward Elgar Press, Massachusetts, USA.
[8] Bauso Dario and Cannon Mark, Consensus in opinion dynamics as a repeated game, Automatica, Vol. 90, April 2018, pp. 204-211.
[9] Cason N. Timothy and Mui Vai-Lam, Individual versus group choices of repeated game strategies: A strategy method approach, Games and Economic Behavior, Vol. 114, March 2019, pp. 128-145.
[10] Ashkenazi-Golan Galit and Lehrer Ehud, Blackwell's comparison of experiments and discounted repeated games, Games and Economic Behavior, Vol. 117, September 2019, pp. 163-194.
[11] Motalleb Mahdi, Annaswamy Anuradha and Ghorbani Reza, A real-time demand response market through a repeated incomplete-information game, Energy, Vol. 143, January 2018, pp. 424-438.
[12] Cason N. Timothy, Lau Paul Sau-Him and Mui Vai-Lam, Learning, teaching, and turn taking in the repeated assignment game, Economic Theory, October 2013, Vol. 54, No. 2, pp. 335–357.
[13] Shekary Maryam and Albadavi Amir, Calculating Customer Lifetime Value Considering Dynamic Behavior of Them Using Markov Chain Approach (Case study: Isaco), Management Researches in Iran, 2019, Vol. 22, No. 4, pp. 1-21, (In Persian).
[14] Singh Vikram Vikas, Lisser Abdel, Continuous Optimization: A second-order cone programming formulation for two player zero-sum games with chance constraints, European Journal of Operational Research, Vol. 275, No. 3, 16 June 2019, pp. 839-845.
[15] Ianovski Luke Ong Egor, The complexity of decision problems about equilibria in two-player Boolean games, Artificial Intelligence, Vol. 261, August 2018, pp. 1-15.
[16] Caruso Francesco, Ceparano Carmela Maria and Morgan Jacqueline, Uniqueness of Nash equilibrium in continuous two-player weighted potential games, Journal of Mathematical Analysis and Applications, Vol. 459, No. 2, 15 March 2018, pp. 1208-1221.
[17] Baskov V. O., Equilibrium payoffs in repeated two-player zero-sum games of finite automata, International Journal of Game Theory, June 2019, Vol. 48, No. 2, pp. 423–431.
[18] Lv Yongfeng, Ren Xuemei and Na Jing, Online optimal solutions for multi-player nonzero-sum game with completely unknown dynamics, Neurocomputing, Vol. 283, March 2018, pp. 87-97.
[19] Amoozad mahdiraji Hanan, Jaafarnejad Ahmad, Moddares Yazdi Mohammad and Mohaghar Ali, Cooperation Modeling for Unlimited Three Echelon Supply Chain: Game Theory Approach, Management Researches in Iran, 2014, Vol. 18, No. 1, pp. 171-191, (In Persian).
[20] Dori Mohsen, Jafari Eskandari Meisam, and Chaharsoghi Kamal, Choosing coordinated ordering policy in the two-level supply chain: A game theory approach, New researches in decision making, 2019, Vol. 4, No. 3, pp.47-73, (In Persian).

[21] Guo Ivan and Rutkowski Marek, Arbitrage-free pricing of multi-person game claims in iscrete time, Finance and Stochastics, January 2017, Vol. 21, No. 1, pp. 111–155.

[22] Abraham P. Mathew and Kulkarni A. Ankur, An Approach Based on Generalized Nash Games and Shared Constraints for Discrete Time Dynamic Games, Dynamic Games and Applications, December 2018, Vol. 8, No. 4, pp. 641–670.

[23] Guo Xin and Zhang Yi, Zero-sum continuous-time Markov pure jump game over a fixed duration, Journal of Mathematical Analysis and Applications, Vol. 452, No. 2, August 2017, pp. 1194-1208.
[24] Sorouri Ghare-Aghaj Saman, Sadeghian Ramin, Tavakkoli-Moghaddam Reza and Makui Ahmad, Introducing a framework for analyzing the cooperation of airlines by the game theory approach, New researches in decision making, 2019, Vol. 4, No. 1, pp. 78-99, (In Persian).
[25] Albarran E. Silvia and Clempner B. Julio, A Stackelberg security Markov game based on partial information for strategic decision making against unexpected attacks, Engineering Applications of Artificial Intelligence, Vol. 81, May 2019, pp. 408-419.
[26] Lei Cheng, Zhang Hong-Qi, Wan Li-Ming, Liu Lu and Ma Duo-he, Incomplete information Markov game theoretic approach to strategy generation for moving target defense, Computer Communications, Vol. 116, January 2018, pp. 184-199.
[27] Kloosterman Andrew, Public information in Markov games, Journal of Economic Theory, Vol. 157, May 2015, pp. 28-48.
[28] Chang Yanling, Erera L. Alan and WhiteIII C. Chelsea, A leader–follower partially observed, multiobjective Markov game, Annals of Operations Research, December 2015, Vol. 235, No. 1, pp. 103–128.
[29] Mollering Karin, Inventory Rationing: A New Modeling Approach Using Markov Chain Theory, 2019, Springer Press, Koln, Germany.
[30] Gilks W. R., Richardson S. and Spiegelhalter D.J., Markov Chain Monte Carlo in Practice, 1996, Chapman & Hall Press, London, UK.