[{"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","type":"conference","OA_type":"gold","article_processing_charge":"Yes","year":"2025","abstract":[{"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.","lang":"eng"}],"related_material":{"record":[{"id":"23079","relation":"dissertation_contains","status":"public"}]},"has_accepted_license":"1","title":"ε-stationary Nash equilibria in multi-player stochastic graph games","intvolume":"       360","month":"12","file":[{"relation":"main_file","success":1,"creator":"dernst","checksum":"a66343e3ccc4a9cc5bc699c03d5764ff","content_type":"application/pdf","file_size":1054007,"date_created":"2026-02-18T09:13:25Z","file_id":"21316","access_level":"open_access","date_updated":"2026-02-18T09:13:25Z","file_name":"2025_FSTTCS_Asadi.pdf"}],"date_updated":"2026-10-12T13:38:13Z","alternative_title":["LIPIcs"],"arxiv":1,"publication":"45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","ddc":["000"],"ec_funded":1,"day":"09","date_created":"2026-02-17T08:27:14Z","oa_version":"Published Version","language":[{"iso":"eng"}],"corr_author":"1","_id":"21281","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.4230/lipics.fsttcs.2025.9","project":[{"grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"volume":360,"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"},"oa":1,"publication_status":"published","date_published":"2025-12-09T00:00:00Z","external_id":{"arxiv":["2508.15356"]},"publication_identifier":{"isbn":["9783959774062"]},"doi":"10.4230/lipics.fsttcs.2025.9","file_date_updated":"2026-02-18T09:13:25Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"OA_place":"publisher","page":"9:1-9:17","author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi","first_name":"Ali","full_name":"Asadi, Ali"},{"full_name":"Brice, Leonard","first_name":"Leonard","last_name":"Brice"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Thejaswini","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","full_name":"Thejaswini, K. S.","first_name":"K. S."}],"quality_controlled":"1","citation":{"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.","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>","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>.","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.","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>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public"}]