Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games
Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games
复制标题
计算广义博弈中Stackelberg均衡的序列形式算法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Jiri Cermak
中科院分区：
文献类型：
--
作者：
B. Bosanský;Jiri Cermak
斯塔克尔伯格均衡是一个解决方案概念，它为玩家规定了要承诺的最佳策略，假设对手知道这一承诺并做出最佳反应。尽管这个解决方案概念是许多安全应用的基石，但现有的工作通常没有考虑玩家在游戏过程中可以观察对手的行为并做出反应的情况。我们将现有的算法工作扩展到扩展形式的游戏，并引入了计算 Stackelberg 均衡的新算法，该算法利用了策略的紧凑序列形式表示。我们的算法将线性程序的大小从基线方法中的指数减小到博弈树大小的线性。对随机生成的游戏和受安全启发的搜索游戏的实验评估表明，与基线方法相比，可扩展性有了显着提高。
Stackelberg equilibrium is a solution concept prescribing for a player an optimal strategy to commit to, assuming the opponent knows this commitment and plays the best response. Although this solution concept is a cornerstone of many security applications, the existing works typically do not consider situations where the players can observe and react to the actions of the opponent during the course of the game. We extend the existing algorithmic work to extensive-form games and introduce novel algorithm for computing Stackelberg equilibria that exploits the compact sequence-form representation of strategies. Our algorithm reduces the size of the linear programs from exponential in the baseline approach to linear in the size of the game tree. Experimental evaluation on randomly generated games and a security-inspired search game demonstrates significant improvement in the scalability compared to the baseline approach.