The Complexity of Infinite-Horizon General-Sum Stochastic Games: Turn-Based and Simultaneous Play

on YouTube ↗54m

" summary

Shows non‑stationary Nash equilibria computable poly(S,A) and stationary Nash equilibria computable poly(A), but proves computing an approximate stationary NE in turn‑based infinite‑horizon general‑sum stochastic games is PPAD‑complete in S for sufficiently large discount (gamma > 1/2). Key tools: a pseudo‑linear single‑state deviation property to get PPAD membership, and a reduction from generalized arithmetic circuits using gadgets with long output paths to force locality; hard instances use N players with rewards at ≤4 states or a 6‑player encoding.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 1:20General-sum stochastic (Markov) games
3. 3:36Turn-based stochastic games (TBSG's)
4. 6:29Possible evidence for polynomial-time computability
5. 8:23Possible evidence for intractability
6. 9:27Key questions: The complexity of stationary equilibria in infinite-horizon general-sum stochastic games
7. 10:24Outline of talk
8. 11:34Infinite-horizon simultaneous stochastic games (SimSG)
9. 14:35Infinite-horizon turn-based stochastic games (TBSG)
10. 15:39The PPAD complexity class
11. 16:43Challenges in studying SimSG and TBSG
12. 21:04Structural properties of SimSG and TBSG: Pseudolinearity
13. 25:10Building blocks for pseudo-linearity: "Two-policy" MDP "Two-policy" MDP: one state has two actions, every other state has only one action
14. 27:19Progress so far: The complexity of stationary equilibria in infinite-horizon general-sum stochastic games
15. 34:09A class of problems known to be PPAD-hard The generalized arithmetic circuit problem (G Circuit Input: A circuit that may contains cycles) of real-valued arithmetic operations, "fan-out"1
16. 36:17Review: Graphical "game gadget" (for equality gate)
17. 39:16TBSG game gadget for equality gate?
18. 41:28TBSG game gadgets with induced locality and linearity
19. 42:21Omitted details of reduction
20. 42:49Summary of our complexity characterization
21. 44:27Open problems Other instances of general-sum structure for polynomial-time stationary NE computation