Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation
Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation
复制标题
有效解决具有广泛形式相关性的轮流随机博弈
DOI：
10.1145/3580507.3597665
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Conitzer, Vincent
中科院分区：
文献类型：
--
作者：
Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
本文研究了两人回合随机博弈中具有广义相关的均衡计算问题。我们的主要结果有两个方面：（1）我们给出了一个计算Stackelberg扩展形式相关均衡（SEFCE）的算法，该算法在游戏大小的时间多项式中运行，以及编码每个输入数字所需的比特数。(2)本文给出了一个近似计算最优扩展形式相关均衡（EFCE）的有效算法，该算法的近似误差ε是关于博弈规模的时间多项式，并且是log（1/ε）.我们的SEFCE算法是第一个在这类随机博弈中求解承诺均衡的多项式时间算法. SEFCE的现有算法通常做出更强的假设，如没有机会移动，并设计用于不太简洁的树形式的扩展形式的游戏。我们的算法近似最优EFCE是，据我们所知，第一个算法，同时实现3个desiderata：近似最优性，多项式依赖于近似误差和兼容性随机游戏更简洁的图形形式。现有的算法实现了这些desiderata中的最多2个，通常还依赖于额外的技术假设。
We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation errorεin time polynomial in the size of the game, as well as log(1/ε).Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.
登录
查看更多内容
广义博弈中具有中介者的多项式时间最优均衡
DOI：
--
发表时间：
2022
期刊：
NeurIPS
影响因子：
--
作者：
Zhang, B.;Sandholm, T.
通讯作者：
Sandholm, T.
广义和扩展型博弈中的最优相关均衡：固定参数算法、硬度和两侧列生成
DOI：
--
发表时间：
2022
期刊：
ICLR-22 Workshop on Gamification and Multiagent Solutions
影响因子：
--
作者：
Zhang, B.;Farina, G.;Celli, A.;Sandholm, T.
通讯作者：
Sandholm, T.
扩展型博弈中的相关性：鞍点公式和基准
DOI：
--
发表时间：
2019
期刊：
Conference on Neural Information Processing Systems.
影响因子：
--
作者：
Farina, G;Ling, C K;Fang, F;Sandholm, T
通讯作者：
Sandholm, T
具有公共机会移动及其他情况的两人扩展形式博弈中最优相关均衡的多项式时间计算
DOI：
--
发表时间：
2020
期刊：
Conference on Neural Information Processing Systems
影响因子：
--
作者：
Farina, G.;Sandholm, T.
通讯作者：
Sandholm, T.
关于纳什均衡的新复杂性结果
DOI：
--
发表时间：
2008
期刊：
Games Econ. Behav.
影响因子：
--
作者：
Vincent Conitzer;T. Sandholm
通讯作者：
T. Sandholm