Stationary Equilibria in Stochastic Games: Structure, Selection and Computation
Stationary Equilibria in Stochastic Games: Structure, Selection and Computation
复制标题
随机博弈中的平稳均衡：结构、选择和计算
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Peeters
中科院分区：
文献类型：
--
作者：
P. Herings;R. Peeters
本文首次提出了一种计算随机对策平稳均衡的算法，并证明了该算法对几乎所有的随机对策都是收敛的。此外，由于总体上平稳均衡的数量是压倒性的，所以我们关注均衡选择的问题。我们通过将线性跟踪过程扩展到随机对策类来实现这一点，称为随机跟踪过程。从计算的角度来看，与正规型对策相比，这类随机对策具有相当大的难度。除了技术上的困难外，还有概念上的困难，例如如何将线性跟踪过程推广到随机对策的环境中.我们证明了这类随机对策存在一个通用子类，对于它，随机跟踪过程是一个紧致的一维分段可微流形.进一步，我们证明了随机跟踪过程产生了一条从任何外在指定的先验信念通向平稳均衡的唯一路径。通过一个精心选择的变量变换，构造了一个处处可微的同伦函数，其零点描述了随机跟踪过程产生的(唯一)路径。由于可微性，我们能够使用标准的路径跟踪技术来跟踪这条路径。这产生了一种全局收敛的算法，该算法在使用现有软件例程的计算机上容易且健壮地实现。作为我们结果的一个副产品，我们将最近关于随机对策中平稳均衡的一般有限性的一个结果推广到均衡的奇异性。
This paper is the first to introduce an algorithm to compute stationary equilibria in stochastic games, and shows convergence of the algorithm for almost all such games. Moreover, since in general the number of stationary equilibria is overwhelming, we pay attention to the issue of equilibrium selection. We do this by extending the linear tracing procedure to the class of stochastic games, called the stochastic tracing procedure. From a computational point of view, the class of stochastic games possesses substantial difficulties compared to normal form games. Apart from technical difficulties, there are also conceptual difficulties, for instance the question how to extend the linear tracing procedure to the environment of stochastic games.We prove that there is a generic subclass of the class of stochastic games for which the stochastic tracing procedure is a compact one-dimensionalpiecewise differentiable manifold with boundary. Furthermore, we prove that the stochastic tracing procedure generates a unique path leading from any exogenously specified prior belief, to a stationary equilibrium. A well-chosen transformation of variables is used to formulate an everywhere differentiable homotopy function, whose zeros describe the (unique) path generated by the stochastic tracing procedure. Because of differentiability we are able to follow this path using standard path-following techniques. This yields a globally convergent algorithm that is easily and robustly implemented on a computer using existing software routines. As a by-product of our results, we extend a recent result on the generic finiteness of stationary equilibria in stochastic games to oddness of equilibria.