Under de senaste decennierna sökandet efter algoritmer för att beräkna Nash equilibria i allmänna stokastiska spel har intensifierats och flera viktiga algoritmer (jfr. [9], [12], [16], [7]) har föreslagits. De lider dock av antingen brist på allmängiltighet eller är svåråtkomliga för till och med medelstora problem eller båda. I detta dokument formulerar vi först ett icke-linjärt optimeringsproblem för stokastiska spel och sedan dela upp det i enklare subproblem som säkerställer att det inte finns något Bellman fel för en given stat och agent. Därefter får vi en uppsättning nya nödvändiga och tillräckliga villkor för att lösa dessa delproblem att vara Nash jämvikt i det underliggande spelet. Med hjälp av dessa villkor utvecklar vi två nya algoritmer -OFF-SGSP och ON-SGSP,respektive. OFF-SGSP är en offline centraliserad algoritm som förutsätter fullständig information om spelet. Å andra sidan är ON-SGSP en online decentraliserad algoritm som fungerar med simulerade övergångar av det stokastiska spelet. Båda algoritmerna är garanterade att konvergera till Nash jämviktsstrategier för allmänna-summan (diskonterade) stokastiska spel.
En algoritm för allmänna stokastiska spel i två scenarier är på REF.
Algorithms for Nash Equilibria in General-Sum Stochastic Games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}