---
OA_place: publisher
_id: '23079'
abstract:
- lang: eng
text: "We study the computational aspects of the two central solution concepts of
stochastic games\r\nplayed on finite graphs for an infinite number of steps: the
value in two-player zero-sum\r\ngames, and Nash equilibria in multi-player games.
In both settings, exact solutions are in\r\ntractable. Fortwo-playerzero-sumconcurrentstochasticgames,valuescanbeirrational,and\r\nthe
associated decision problem is SQRT-SUM hard. For multi-player turn-based stochastic\r\ngames,theequilibriumprobabilitiescanbeirrational,anddecidingtheconstrainedexistence\r\nof
a Nash equilibrium is undecidable in the presence of memory, and ∃R-complete when
the\r\nplayers are restricted to stationary strategies. Hence, in both settings,
the natural computational problem is the approximation of the solution within
an arbitrary additive error. In\r\nthis thesis, we present improved complexity
results and algorithms for such approximation\r\nproblems.\r\nThe first part of
the thesis considers two-player zero-sum concurrent stochastic games\r\nwith two
classic objectives: (a) stateful-discounted objectives, which are similar to the
classic\r\ndiscounted-sum objectives, but states are associated with different
discount factors rather\r\nthan a single discount factor; and (b) parity objectives,
which are a canonical representation\r\nfor ω-regular objectives. For stateful-discounted
objectives, given an ordering of the discount\r\nfactors, the limit value is the
limit of the value of the stateful-discounted objectives, as\r\nthe discount factors
approach zero according to the given order. The value-approximation\r\nproblem
is known to be in EXPSPACE for the limit value of stateful-discounted objectives
and\r\nin PSPACEforparityobjectives,andthebest-knownalgorithmsforbothproblemsareatleast\r\nexponential
time, with an exponential dependence on the number of states and actions. Our\r\nmain
results for the value-approximation problem for the limit value of stateful-discounted\r\nobjectives
and parity objectives areas follows: (a)we establish TFNPNP complexity; and (b)we\r\npresent
algorithms that improve the dependency on the number of actions in the exponent\r\nfrom
linear to logarithmic. In particular, if the number of states is constant, our
algorithms\r\nrun in polynomial time.\r\nThe second part of the thesis considers
multi-player turn-based stochastic games with\r\nterminal payoffs, where the players
are restricted to stationary strategies. We study the\r\napproximate constrained
existence problem of Nash equilibria: given a game that has a Nash\r\nequilibrium
in which the payoff of every player lies in a given interval, compute a strategy\r\nprofile
that is an ε-Nash equilibrium and that satisfies the same constraints up to an
additive\r\nerror ε. Our main results are as follows: (a) we present an FNPNP
algorithm for the problem;\r\nand(b)we establish that its decision version is
NP-hard, already with two players. For the\r\nupperbound,weshowthatifaconstrainedNashequilibriumexists,thenthereexists
one\r\nin which the non-zero probabilities are at least an inverse of a double-exponential
in the\r\ni\r\ninput size, and that such a strategy profile can be represented,
up to an additive error ε, with\r\nfloating-point numbers of polynomial size.
We complement the upper bound with a lower\r\nbound on this approach: we present
a game with only five players in which every constrained\r\nNash equilibrium requires
double-exponentially small probabilities.\r\nThe two parts share a common technical
toolkit: bounds on solutions of systems of\r\npolynomial inequalities that arise
from real algebraic geometry, the floating-point representation of doubly-exponentially
small numbers, and guess-and-verify procedures that resolve\r\nsingle-player games
with an NP oracle."
acknowledgement: "The research reported in Part I was partially supported by the European
Research\r\nCouncil (ERC) Consolidator Grant 863818 (ForM-SMArt), by the Austrian
Science Fund\r\n(FWF) 10.55776/COE12, and by the French Agence Nationale de la Recherche
(ANR) grant\r\nANR-21-CE40-0020 (CONVERGENCE project). The research reported in
Part II is a part of\r\nproject VAMOS, which has received funding from the European
Research Council (ERC) under\r\ngrant agreement No.101020093."
alternative_title:
- ISTA Master’s Thesis
article_processing_charge: No
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
citation:
ama: 'Asadi A. Approximation of values and equilibria in stochastic games: Complexity
and algorithms. 2026. doi:10.15479/AT-ISTA-23079'
apa: 'Asadi, A. (2026). Approximation of values and equilibria in stochastic
games: Complexity and algorithms. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT-ISTA-23079'
chicago: 'Asadi, Ali. “Approximation of Values and Equilibria in Stochastic Games:
Complexity and Algorithms.” Institute of Science and Technology Austria, 2026.
https://doi.org/10.15479/AT-ISTA-23079.'
ieee: 'A. Asadi, “Approximation of values and equilibria in stochastic games: Complexity
and algorithms,” Institute of Science and Technology Austria, 2026.'
ista: 'Asadi A. 2026. Approximation of values and equilibria in stochastic games:
Complexity and algorithms. Institute of Science and Technology Austria.'
mla: 'Asadi, Ali. Approximation of Values and Equilibria in Stochastic Games:
Complexity and Algorithms. Institute of Science and Technology Austria, 2026,
doi:10.15479/AT-ISTA-23079.'
short: 'A. Asadi, Approximation of Values and Equilibria in Stochastic Games: Complexity
and Algorithms, Institute of Science and Technology Austria, 2026.'
corr_author: '1'
date_created: 2026-10-08T09:07:53Z
date_published: 2026-10-09T00:00:00Z
date_updated: 2026-10-12T13:38:13Z
day: '09'
ddc:
- '000'
degree_awarded: MS
department:
- _id: GradSch
- _id: KrCh
doi: 10.15479/AT-ISTA-23079
doi_confirm: '1'
ec_funded: 1
file:
- access_level: open_access
checksum: c6b368f342409de884eafdd3af7867c5
content_type: application/pdf
creator: aasadi
date_created: 2026-10-09T11:12:08Z
date_updated: 2026-10-12T13:13:51Z
file_id: '23081'
file_name: 2026_Asadi_Ali_Thesis.pdf
file_size: 694682
relation: main_file
- access_level: closed
checksum: 71ecb0b666438f395a92b395e315f904
content_type: application/zip
creator: aasadi
date_created: 2026-10-09T11:12:56Z
date_updated: 2026-10-09T11:47:47Z
file_id: '23082'
file_name: 2026_Asadi_Ali_Thesis.zip
file_size: 1538723
relation: source_file
file_date_updated: 2026-10-12T13:13:51Z
fulldoi: https://doi.org/10.15479/AT-ISTA-23079
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
page: '83'
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication_identifier:
issn:
- 2791-4585
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '17099'
relation: part_of_dissertation
status: public
- id: '21281'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: 'Approximation of values and equilibria in stochastic games: Complexity and
algorithms'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...