{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:54:34Z","timestamp":1740160474474,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T00:00:00Z","timestamp":1709337600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T00:00:00Z","timestamp":1709337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Dyn Games Appl"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we compare the value of zero-sum stochastic games under optimal strategies (that are, for single-controller stochastic games, stationary) to the commonly used time-independent strategies (\u201cstatic strategies\u201d). Our findings are summarized in a series of theorems which provide the lower bound on the optimality of the static strategy under different assumptions. These bounds can be used to assess whether the additional computational complexity is worth the extra payoff gain or, symmetrically, assess the price of playing sub-optimal but simple strategies when stationary ones are forbidden.\n\n<\/jats:p>","DOI":"10.1007\/s13235-024-00555-w","type":"journal-article","created":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T11:02:32Z","timestamp":1709377352000},"page":"1317-1332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Price of History-Independent Strategies in Games with Inter-Temporal Externalities"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7643-4073","authenticated-orcid":false,"given":"Yevgeny","family":"Tsodikovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1150-9139","authenticated-orcid":false,"given":"Xavier","family":"Venel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5530-1183","authenticated-orcid":false,"given":"Anna","family":"Zseleva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,2]]},"reference":[{"issue":"2","key":"555_CR1","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1137\/0331018","volume":"31","author":"A Arapostathis","year":"1993","unstructured":"Arapostathis A, Borkar VS, Fern\u00e1ndez-Gaucherand E, Ghosh MK, Marcus SI (1993) Discrete-time controlled Markov processes with average cost criterion: a survey. SIAM J Control Optim 31(2):282\u2013344","journal-title":"SIAM J Control Optim"},{"issue":"1","key":"555_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0022-0531(90)90056-P","volume":"51","author":"SK Chakrabarti","year":"1990","unstructured":"Chakrabarti SK (1990) Characterizations of the equilibrium payoffs of inertia supergames. J Econ Theor 51(1):171\u2013183","journal-title":"J Econ Theor"},{"issue":"4","key":"555_CR3","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF00935890","volume":"34","author":"JA Filar","year":"1981","unstructured":"Filar JA (1981) Ordered field property for stochastic games when the player who controls transitions changes from state to state. J Optim Theory Appl 34(4):503\u2013515","journal-title":"J Optim Theory Appl"},{"issue":"3","key":"555_CR4","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1287\/moor.9.3.356","volume":"9","author":"JA Filar","year":"1984","unstructured":"Filar JA, Raghavan TES (1984) A matrix game solution of the single-controller stochastic game. Math Oper Res 9(3):356\u2013362","journal-title":"Math Oper Res"},{"issue":"1","key":"555_CR5","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF01720770","volume":"8","author":"JA Filar","year":"1986","unstructured":"Filar JA, Schultz TA (1986) The traveling inspector model. Oper Res Spektr 8(1):33\u201336","journal-title":"Oper Res Spektr"},{"issue":"8","key":"555_CR6","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1109\/TAC.1985.1104060","volume":"30","author":"J Filar","year":"1985","unstructured":"Filar J (1985) Player aggregation in the traveling inspector model. IEEE Trans Autom Control 30(8):723\u2013729","journal-title":"IEEE Trans Autom Control"},{"issue":"2","key":"555_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1006\/jeth.2000.2655","volume":"93","author":"BL Lipman","year":"2000","unstructured":"Lipman BL, Wang R (2000) Switching costs in frequently repeated games. J Econ Theor 93(2):149\u2013190","journal-title":"J Econ Theor"},{"issue":"1","key":"555_CR8","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/j.geb.2008.04.018","volume":"66","author":"BL Lipman","year":"2009","unstructured":"Lipman BL, Wang R (2009) Switching costs in infinitely repeated games. Games Econ Behav 66(1):292\u2013314","journal-title":"Games Econ Behav"},{"key":"555_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-021-00282-7","author":"G Liuzzi","year":"2021","unstructured":"Liuzzi G, Locatelli M, Piccialli V, Rass S (2021) Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex qp problems. Comput Optim Appl. https:\/\/doi.org\/10.1007\/s10589-021-00282-7","journal-title":"Comput Optim Appl"},{"issue":"3","key":"555_CR10","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/BF00935250","volume":"33","author":"T Parthasarathy","year":"1981","unstructured":"Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33(3):375\u2013392","journal-title":"J Optim Theory Appl"},{"key":"555_CR11","doi-asserted-by":"crossref","unstructured":"Raghavan TES (2003) Finite-step algorithms for single-controller and perfect information stochastic games. In Stochastic games and applications, pp 227\u2013251. Springer","DOI":"10.1007\/978-94-010-0189-2_15"},{"issue":"6","key":"555_CR12","first-page":"437","volume":"35","author":"TES Raghavan","year":"1991","unstructured":"Raghavan TES, Filar JA (1991) Algorithms for stochastic games\u2014a survey. Z Oper Res 35(6):437\u2013472","journal-title":"Z Oper Res"},{"issue":"2","key":"555_CR13","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1287\/moor.27.2.384.318","volume":"27","author":"TES Raghavan","year":"2002","unstructured":"Raghavan TES, Syed Z (2002) Computing stationary nash equilibria of undiscounted single-controller stochastic games. Math Oper Res 27(2):384\u2013400","journal-title":"Math Oper Res"},{"issue":"1","key":"555_CR14","doi-asserted-by":"publisher","first-page":"e0168675","DOI":"10.1371\/journal.pone.0168675","volume":"12","author":"S Rass","year":"2017","unstructured":"Rass S, Konig S, Schauer S (2017) Defending against advanced persistent threats using game-theory. PLoS ONE 12(1):e0168675","journal-title":"PLoS ONE"},{"issue":"3","key":"555_CR15","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10957-007-9318-6","volume":"136","author":"G Schoenmakers","year":"2008","unstructured":"Schoenmakers G, Flesch J, Thuijsman F, Vrieze OJ (2008) Repeated games with bonuses. J Optim Theory Appl 136(3):459\u2013473","journal-title":"J Optim Theory Appl"},{"key":"555_CR16","doi-asserted-by":"crossref","unstructured":"Tsodikovich Y, Venel X, Zseleva A (2024) Folk theorems in repeated games with switching costs","DOI":"10.2139\/ssrn.4583297"},{"issue":"4","key":"555_CR17","first-page":"1899","volume":"48","author":"Y Tsodikovich","year":"2023","unstructured":"Tsodikovich Y, Venel X, Zseleva A, Tsodikovich Y, Venel X, Zseleva A (2023) The regularity of the value function of repeated games with switching costs. Math Oper Res 48(4):1899\u20131905","journal-title":"Math Oper Res"},{"issue":"3","key":"555_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3390\/g9030059","volume":"9","author":"J Wachter","year":"2018","unstructured":"Wachter J, Rass S, Konig S (2018) Security from the adversarys inertia-controlling convergence speed when playing mixed strategy equilibria. Games 9(3):59","journal-title":"Games"}],"container-title":["Dynamic Games and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-024-00555-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13235-024-00555-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-024-00555-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T18:04:10Z","timestamp":1728842650000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13235-024-00555-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,2]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["555"],"URL":"https:\/\/doi.org\/10.1007\/s13235-024-00555-w","relation":{},"ISSN":["2153-0785","2153-0793"],"issn-type":[{"type":"print","value":"2153-0785"},{"type":"electronic","value":"2153-0793"}],"subject":[],"published":{"date-parts":[[2024,3,2]]},"assertion":[{"value":"24 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval."}}]}}