Equilibrium Computation for Extensive Games
Equilibrium Computation for Extensive Games
复制标题
广泛博弈的均衡计算
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Wan Huang
中科院分区：
文献类型：
--
作者：
Wan Huang
本文研究了可拓对策的均衡计算算法。我们专注于纳什均衡的枚举和计算的广泛形式的相关均衡。本论文的贡献包括两个部分。首先，我们研究了一个两人扩展博弈的所有纳什均衡的算法。该算法基于扩展博弈纳什均衡的序列形式描述（von Stengel 1996）。我们开发了一个系统的方法来消除冗余在这个系统中，并证明了所有的平衡点表示的一对多面体的顶点。然后，我们应用Avis（2000）的反向搜索顶点枚举算法来枚举这对多面体的所有顶点。我们使用标签系统来验证代表纳什均衡的顶点对。其次，我们提出了一个多项式时间算法计算广泛的形式相关均衡（EFCE）的多人游戏的机会移动。为了实现这一目标，我们首先将EFCE描述为满足一组激励约束的产品分布。然后，我们提供了一个建设性的证明EFCE的存在。基于这个证明，我们证明了一个多人游戏的机会移动的EFCE可以在多项式时间内计算。
This thesis studies equilibrium computation algorithms for extensive games. We focus on the enumeration of Nash equilibria and on the computation of an extensive form correlated equilibrium. The contribution of this thesis consists of two parts. First, we study an algorithm for enumerating all Nash equilibria of a two-player extensive game. This algorithm is based on the sequence form description for Nash equilibria of extensive games (von Stengel 1996). We develop a systematic way of eliminating redundancy in this system, and prove that all the equilibria are represented by vertices of a pair of polyhedra. Then we apply the reverse search vertex enumeration algorithm by Avis (2000) to this pair of polyhedra to enumerate all the vertices. We use a label system to verify pairs of vertices that represent Nash equilibria. Second, we present a polynomial time algorithm for computing an extensive form correlated equilibrium (EFCE) of a multi-player game with chance moves. To achieve this, we first characterize the EFCE as product distributions that satisfy a set of incentive constraints. We then provide a constructive proof of the existence of EFCE. Based on this proof, we show that an EFCE of a multi-player game with chance moves can be computed in polynomial time.
影响因子：
1.3
作者：
Avis, David;Rosenberg, Gabriel D.;von Stengel, Bernhard
通讯作者：
von Stengel, Bernhard