Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games
Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games
复制标题
使用相关策略计算广义博弈中的 Stackelberg 均衡
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Christopher Kiekintveld
中科院分区：
文献类型：
--
作者：
Jiri Cermak;B. Bosanský;K. Durkota;V. Lisý;Christopher Kiekintveld
强Stackelberg均衡(SSE)是博弈论中的一个基本解概念，其中一个参与者致力于一种策略，而另一个参与者遵守这一承诺并做出最佳反应。针对非完全信息两人广义和对策(EFGs)，提出了一种计算SSE的新算法，其中SSE的计算是一个NP难问题。我们的算法基于SSE的一个相关版本，称为Stackelberg扩展形式相关均衡(SEFCE)。因此，我们的贡献是双重的：(1)我们给出了无机会计算EFGS中SEFCE的第一个线性规划；(2)我们在系统的搜索中反复地求解和修改这个线性规划，直到我们到达SSE。我们的新算法比以前最好的算法性能高出几个数量级。
Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.