Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912418971516928 |
|---|---|
| author | Gan, Jiarui Majumdar, Rupak |
| author_facet | Gan, Jiarui Majumdar, Rupak |
| contents | We study the problem of computing optimal correlated equilibria (CEs) in infinite-horizon multi-player stochastic games, where correlation signals are provided over time. In this setting, optimal CEs require history-dependent policies; this poses new representational and algorithmic challenges as the number of possible histories grows exponentially with the number of time steps. We focus on computing $(ε, δ)$-optimal CEs -- solutions that achieve a value within $ε$ of an optimal CE, while allowing the agents' incentive constraints to be violated by at most $δ$. Our main result is an algorithm that computes an $(ε,δ)$-optimal CE in time polynomial in $1/(εδ(1 - γ))^{n+1}$, where $γ$ is the discount factor, and $n$ is the number of agents. For (a slightly more general variant of) turn-based games, we further reduce the complexity to a polynomial in $n$. We also establish that the bi-criterion approximation is necessary by proving matching inapproximability bounds.
Our technical core is a novel approach based on inducible value sets, which leverages a compact representation of history-dependent CEs through the values they induce to overcome the representational challenge. We develop the value-set iteration algorithm -- which operates by iteratively updating estimates of inducible value sets -- and characterize CEs as the greatest fixed point of the update map. Our algorithm provides a groundwork for computing optimal CEs in general multi-player stochastic settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07186 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games Gan, Jiarui Majumdar, Rupak Computer Science and Game Theory We study the problem of computing optimal correlated equilibria (CEs) in infinite-horizon multi-player stochastic games, where correlation signals are provided over time. In this setting, optimal CEs require history-dependent policies; this poses new representational and algorithmic challenges as the number of possible histories grows exponentially with the number of time steps. We focus on computing $(ε, δ)$-optimal CEs -- solutions that achieve a value within $ε$ of an optimal CE, while allowing the agents' incentive constraints to be violated by at most $δ$. Our main result is an algorithm that computes an $(ε,δ)$-optimal CE in time polynomial in $1/(εδ(1 - γ))^{n+1}$, where $γ$ is the discount factor, and $n$ is the number of agents. For (a slightly more general variant of) turn-based games, we further reduce the complexity to a polynomial in $n$. We also establish that the bi-criterion approximation is necessary by proving matching inapproximability bounds. Our technical core is a novel approach based on inducible value sets, which leverages a compact representation of history-dependent CEs through the values they induce to overcome the representational challenge. We develop the value-set iteration algorithm -- which operates by iteratively updating estimates of inducible value sets -- and characterize CEs as the greatest fixed point of the update map. Our algorithm provides a groundwork for computing optimal CEs in general multi-player stochastic settings. |
| title | Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.07186 |