---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Ali
      foaf_name: Asadi, Ali
      foaf_surname: Asadi
      foaf_workInfoHomepage: http://www.librecat.org/personId=02d96aae-000e-11ec-b801-cadd0a5eefbb
  bibo_doi: 10.15479/AT-ISTA-23079
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2791-4585
  dct_language: eng
  dct_publisher: Institute of Science and Technology Austria@
  dct_title: 'Approximation of values and equilibria in stochastic games: Complexity
    and algorithms@'
...