[{"publication":"45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":[{"full_name":"Asadi, Ali","last_name":"Asadi","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","first_name":"Ali"},{"last_name":"Brice","full_name":"Brice, Leonard","first_name":"Leonard"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"K. S.","last_name":"Thejaswini","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","full_name":"Thejaswini, K. S."}],"conference":{"location":"Pilani, India","end_date":"2025-12-19","name":"FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science","start_date":"2025-12-17"},"corr_author":"1","title":"ε-stationary Nash equilibria in multi-player stochastic graph games","oa":1,"publication_identifier":{"isbn":["9783959774062"]},"type":"conference","doi":"10.4230/lipics.fsttcs.2025.9","month":"12","license":"https://creativecommons.org/licenses/by/4.0/","page":"9:1-9:17","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"volume":360,"project":[{"grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020"}],"related_material":{"record":[{"id":"23079","relation":"dissertation_contains","status":"public"}]},"quality_controlled":"1","article_processing_charge":"Yes","date_created":"2026-02-17T08:27:14Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"file_date_updated":"2026-02-18T09:13:25Z","abstract":[{"lang":"eng","text":"A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating from their strategy. In this work, we use ε-Nash equilibria to approximate the computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer stochastic games played on graphs, where players are restricted to stationary strategies - strategies that use randomness but not memory.\r\nThe problem of deciding the constrained existence of stationary Nash equilibria - where each player’s payoff must lie within a given interval - is known to be ∃ℝ-complete in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to stationary ε-Nash equilibria and present an algorithm that solves the following promise problem: given a game with a Nash equilibrium satisfying the constraints, compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies the constraints up to an ε additive error. Our algorithm runs in FNP^NP time.\r\nTo achieve this, we first show that if a constrained Nash equilibrium exists, then one exists where the non-zero probabilities are at least an inverse of a double-exponential in the input. We further prove that such a strategy can be encoded using floating-point representations, as in the work of Frederiksen and Miltersen (2013), which finally gives us our FNP^NP algorithm. \r\nWe further show that the decision version of the promise problem is NP-hard. Finally, we show a partial tightness result by proving a lower bound for such techniques: if a constrained Nash equilibrium exists, then there must be one where the probabilities in the strategies are double-exponentially small."}],"alternative_title":["LIPIcs"],"date_updated":"2026-10-12T13:38:13Z","OA_place":"publisher","has_accepted_license":"1","date_published":"2025-12-09T00:00:00Z","OA_type":"gold","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/lipics.fsttcs.2025.9","arxiv":1,"day":"09","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","citation":{"ieee":"A. Asadi, L. Brice, K. Chatterjee, and K. S. Thejaswini, “ε-stationary Nash equilibria in multi-player stochastic graph games,” in <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Pilani, India, 2025, vol. 360, p. 9:1-9:17.","apa":"Asadi, A., Brice, L., Chatterjee, K., &#38; Thejaswini, K. S. (2025). ε-stationary Nash equilibria in multi-player stochastic graph games. In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 360, p. 9:1-9:17). Pilani, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>","ama":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. ε-stationary Nash equilibria in multi-player stochastic graph games. In: <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 360. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:9:1-9:17. doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>","ista":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. 2025. ε-stationary Nash equilibria in multi-player stochastic graph games. 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 360, 9:1-9:17.","short":"A. Asadi, L. Brice, K. Chatterjee, K.S. Thejaswini, in:, 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17.","mla":"Asadi, Ali, et al. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 360, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17, doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>.","chicago":"Asadi, Ali, Leonard Brice, Krishnendu Chatterjee, and K. S. Thejaswini. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, 360:9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>."},"acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093.\r\n","status":"public","_id":"21281","oa_version":"Published Version","external_id":{"arxiv":["2508.15356"]},"intvolume":"       360","file":[{"relation":"main_file","access_level":"open_access","checksum":"a66343e3ccc4a9cc5bc699c03d5764ff","content_type":"application/pdf","date_updated":"2026-02-18T09:13:25Z","creator":"dernst","file_id":"21316","success":1,"file_name":"2025_FSTTCS_Asadi.pdf","date_created":"2026-02-18T09:13:25Z","file_size":1054007}]}]