Reducing stochastic games to semidefinite programming

DOI10.4230/LIPICS.ICALP.2025.145MaRDI QIDQ7397604zbMATH OpenFDO

Authors Manuel Bodirsky, Georg Loho, Mateusz Skomra

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.145

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• A recursive approach to solving parity games in quasipolynomial time
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Algorithms in real algebraic geometry
• An exact duality theory for semidefinite programming and its complexity implications
• An exponential lower bound for Cunningham's rule
• An exponential lower bound for Zadeh's pivot rule
• An improved bound on sums of square roots via the subspace theorem
• Borel determinacy
• Combinatorial simplex algorithms can solve mean payoff games
• Comparison of algorithms for simple stochastic games
• Deciding Parity Games in Quasi-polynomial Time
• From Parity and Payoff Games to Linear Programming
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 5685899 (Why is no real title available?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Linear complementarity algorithms for infinite games
• Linear complementarity and P-matrices for stochastic games
• On the Complexity of Numerical Analysis
• On the complexity of semidefinite programs
• Positional strategies for mean payoff games
• Principles of systems design. Essays dedicated to Thomas A. Henzinger on the occasion of his 60th birthday
• Register games
• Scheduling with AND/OR Precedence Constraints
• Semidefinite programming and arithmetic circuit evaluation
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Spectrahedral shadows
• Stochastic Games with Perfect Information and Time Average Payoff
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games
• The complexity of mean payoff games on graphs
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games
• The Max-Atom Problem and Its Relevance
• The mu-calculus and Model Checking
• The Theory of Universal Graphs for Infinite Duration Games
• Tropical polyhedra are equivalent to mean payoff games
• Tropicalizing the simplex algorithm
• Unique end of potential line
• What Tropical Geometry Tells Us about the Complexity of Linear Programming

This page was built for publication: Reducing stochastic games to semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7397604)