Upper and lower values in zero-sum stochastic games with asymmetric information. (English) Zbl 1532.91013
Summary: A general model for zero-sum stochastic games with asymmetric information is considered. In this model, each player’s information at each time can be divided into a common information part and a private information part. Under certain conditions on the evolution of the common and private information, a dynamic programming characterization of the value of the game (if it exists) is presented. If the value of the zero-sum game does not exist, then the dynamic program provides bounds on the upper and lower values of the game.
MSC:
| 91A15 | Stochastic games, stochastic differential games |
| 91A10 | Noncooperative games |
| 90C39 | Dynamic programming |
References:
| [1] | Alpcan, T.; Başar, T., Network security: a decision and game-theoretic approach (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1200.68002 · doi:10.1007/978-3-642-17197-0 |
| [2] | Amin, S.; Litrico, X.; Sastry, S.; Bayen, AM, Cyber security of water scada systemspart I: analysis and experimentation of stealthy deception attacks, IEEE Trans Control Syst Technol, 21, 5, 1963-1970 (2012) · doi:10.1109/TCST.2012.2211873 |
| [3] | Amin, S.; Schwartz, GA; Cardenas, AA; Sastry, SS, Game-theoretic models of electricity theft detection in smart utility networks: providing new capabilities with advanced metering infrastructure, IEEE Control Syst Mag, 35, 1, 66-81 (2015) · Zbl 1476.94024 · doi:10.1109/MCS.2014.2364711 |
| [4] | Aumann, RJ; Maschler, M.; Stearns, RE, Repeated games with incomplete information (1995), Cambridge: MIT Press, Cambridge · Zbl 0972.91501 |
| [5] | Başar, T., On the saddle-point solution of a class of stochastic differential games, J Optim Theory Appl, 33, 4, 539-556 (1981) · Zbl 0453.90113 · doi:10.1007/BF00935757 |
| [6] | Basar, T.; Olsder, GJ, Dynamic noncooperative game theory (1999), Philadelphia: SIAM, Philadelphia · Zbl 0946.91001 |
| [7] | Bondi E, Oh H, Xu H, Fang F, Dilkina B, Tambe M (2019) Using game theory in real time in the real world: A conservation case study. In: Proceedings of the 18th international conference on autonomous agents and multiagent systems, pp. 2336-2338. International Foundation for Autonomous Agents and Multiagent Systems |
| [8] | Fang, F.; Nguyen, TH; Pickles, R.; Lam, WY; Clements, GR; An, B.; Singh, A.; Schwedock, BC; Tambe, M.; Lemieux, A., Paws-a deployed game-theoretic application to combat poaching, AI Mag, 38, 1, 23-36 (2017) |
| [9] | Fang F, Stone P, Tambe M (2015) When security games go green: Designing defender strategies to prevent poaching and illegal fishing. In: Twenty-fourth international joint conference on artificial intelligence |
| [10] | Filar, J.; Vrieze, K., Competitive Markov decision processes (2012), Berlin: Springer, Berlin · Zbl 0934.91002 |
| [11] | Fudenberg, D.; Tirole, J., Game theory (1991), Cambridge: MIT Press, Cambridge · Zbl 1339.91001 |
| [12] | Gensbittel, F.; Oliu-Barton, M.; Venel, X., Existence of the uniform value in zero-sum repeated games with a more informed controller, J Dyn Games, 1, 3, 411-445 (2014) · Zbl 1314.91026 · doi:10.3934/jdg.2014.1.411 |
| [13] | Gensbittel, F.; Renault, J., The value of Markov chain games with incomplete information on both sides, Math Oper Res, 40, 4, 820-841 (2015) · Zbl 1330.91030 · doi:10.1287/moor.2014.0697 |
| [14] | Hansen EA (1998) Solving pomdps by searching in policy space. In: Proceedings of the fourteenth conference on Uncertainty in artificial intelligence, pp 211-219 |
| [15] | Haywood, O. Jr, Military decision and game theory, J Oper Res Soc Am, 2, 4, 365-385 (1954) · Zbl 1414.90179 |
| [16] | Hernández-Lerma, O.; Lasserre, JB, Discrete-time Markov control processes: basic optimality criteria (2012), Berlin: Springer, Berlin · Zbl 0840.93001 |
| [17] | Kartik D, Nayyar A (2019) Stochastic zero-sum games with asymmetric information. In: 58th IEEE conference on decision and control. IEEE · Zbl 1532.91013 |
| [18] | Kartik D, Nayyar A (2019) Zero-sum stochastic games with asymmetric information. arXiv preprint arXiv:1909.01445 · Zbl 1532.91013 |
| [19] | Li L, Shamma J (2014) LP formulation of asymmetric zero-sum stochastic games. In: 53rd IEEE conference on decision and control, pp. 1930-1935. IEEE |
| [20] | Li, X.; Venel, X., Recursive games: uniform value, tauberian theorem and the mertens conjecture, Int J Game Theory, 45, 1-2, 155-189 (2016) · Zbl 1388.91043 · doi:10.1007/s00182-015-0496-4 |
| [21] | Loch J, Singh SP (1998) Using eligibility traces to find the best memoryless policy in partially observable markov decision processes. In: Proceedings of the fifteenth international conference on machine learning, pp. 323-331 |
| [22] | Maschler M, Solan E, Zamir S (2013) Game theory. Cambridge University Press. doi:10.1017/CBO9780511794216 · Zbl 1403.91003 |
| [23] | Mertens, JF; Sorin, S.; Zamir, S., Repeated games (2015), Cambridge: Cambridge University Press, Cambridge · Zbl 1336.91005 · doi:10.1017/CBO9781139343275 |
| [24] | Morrow, JD, Game theory for political scientists (1994), Princeton: Princeton University Press, Princeton |
| [25] | Nayyar A, Gupta A (2017) Information structures and values in zero-sum stochastic games. In: American control conference (ACC), 2017, pp. 3658-3663. IEEE |
| [26] | Nayyar, A.; Gupta, A.; Langbort, C.; Başar, T., Common information based Markov perfect equilibria for stochastic games with asymmetric information: finite games, IEEE Trans Autom Control, 59, 3, 555-570 (2014) · Zbl 1360.91021 · doi:10.1109/TAC.2013.2283743 |
| [27] | Nayyar, A.; Mahajan, A.; Teneketzis, D., Optimal control strategies in delayed sharing information structures, IEEE Trans Autom Control, 56, 7, 1606-1620 (2010) · Zbl 1368.90170 · doi:10.1109/TAC.2010.2089381 |
| [28] | Nayyar, A.; Mahajan, A.; Teneketzis, D., Decentralized stochastic control with partial history sharing: a common information approach, IEEE Trans Autom Control, 58, 7, 1644-1658 (2013) · Zbl 1369.90187 · doi:10.1109/TAC.2013.2239000 |
| [29] | Osborne, MJ; Rubinstein, A., A course in game theory (1994), Cambridge: MIT Press, Cambridge · Zbl 1194.91003 |
| [30] | Ouyang, Y.; Tavafoghi, H.; Teneketzis, D., Dynamic games with asymmetric information: common information based perfect bayesian equilibria and sequential decomposition, IEEE Trans Autom Control, 62, 1, 222-237 (2017) · Zbl 1359.91017 · doi:10.1109/TAC.2016.2544936 |
| [31] | Ponssard, JP; Sorin, S., The lp formulation of finite zero-sum games with incomplete information, Int J Game Theory, 9, 2, 99-105 (1980) · Zbl 0433.90090 · doi:10.1007/BF01769767 |
| [32] | Renault, J., The value of Markov chain games with lack of information on one side, Math Oper Res, 31, 3, 490-512 (2006) · Zbl 1276.91023 · doi:10.1287/moor.1060.0199 |
| [33] | Renault, J., The value of repeated games with an informed controller, Math Oper Res, 37, 1, 154-179 (2012) · Zbl 1238.91027 · doi:10.1287/moor.1110.0518 |
| [34] | Rosenberg, D., Duality and markovian strategies, Int J Game Theory, 27, 4, 577-597 (1998) · Zbl 0959.91006 · doi:10.1007/s001820050091 |
| [35] | Rosenberg, D.; Solan, E.; Vieille, N., Stochastic games with a single controller and incomplete information, SIAM J Control Optim, 43, 1, 86-110 (2004) · Zbl 1101.91001 · doi:10.1137/S0363012902407107 |
| [36] | Rudin, W., Principles of mathematical analysis (1964), New York: McGraw-hill, New York · Zbl 0148.02903 |
| [37] | Sandell NR Jr (1974) Control of Finite-State, Finite-Memory Stochastic Systems, Massachusetts Institute of Technology, PhD Thesis. https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19740018646.pdf |
| [38] | Shelar, D.; Amin, S., Security assessment of electricity distribution networks under der node compromises, IEEE Trans Control Netw Syst, 4, 1, 23-36 (2017) · Zbl 1370.94566 · doi:10.1109/TCNS.2016.2598427 |
| [39] | Teneketzis, D., On the structure of optimal real-time encoders and decoders in noisy communication, IEEE Trans Inf Theory, 52, 9, 4017-4035 (2006) · Zbl 1309.94086 · doi:10.1109/TIT.2006.880067 |
| [40] | Vasal, D.; Sinha, A.; Anastasopoulos, A., A systematic process for evaluating structured perfect bayesian equilibria in dynamic games with asymmetric information, IEEE Trans Autom Control, 64, 1, 78-93 (2019) · Zbl 1425.91063 · doi:10.1109/TAC.2018.2809863 |
| [41] | Washburn, A.; Wood, K., Two-person zero-sum games for network interdiction, Oper Res, 43, 2, 243-251 (1995) · Zbl 0832.90124 · doi:10.1287/opre.43.2.243 |
| [42] | Wu, M.; Amin, S., Securing infrastructure facilities: When does proactive defense help?, Dyn Games Appl, 9, 1-42 (2018) · Zbl 1431.91032 |
| [43] | Zheng J, Castañón DA (2013) Decomposition techniques for Markov zero-sum games with nested information. In: 52nd IEEE conference on decision and control, pp. 574-581. IEEE |
| [44] | Zhu, Q.; Basar, T., Game-theoretic methods for robustness, security, and resilience of cyberphysical control systems: games-in-games principle for optimal cross-layer resilient control systems, IEEE Control Syst Mag, 35, 1, 46-65 (2015) · Zbl 1476.93098 · doi:10.1109/MCS.2014.2364710 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
