Probabilistic analysis of simulation-based games
Probabilistic analysis of simulation-based games
复制标题
基于模拟的游戏的概率分析
DOI：
10.1145/1842713.1842719
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Yevgeniy Vorobeychik
中科院分区：
文献类型：
--
作者：
Yevgeniy Vorobeychik
博弈论领域已被证明是非常重要的建模在各种设置中的自利各方之间的相互作用。传统上，博弈论分析依赖于高度程式化的模型，以提供关于手头问题的有趣见解。这种模型的缺点是，它们往往不能捕捉到重要的细节。另一方面，许多真实的战略设置，如赞助搜索拍卖和供应链，可以在高分辨率模拟。最近，已经引入了许多方法来通过基于模拟的模型来执行博弈论场景的分析。这项工作的第一个贡献是从基于模拟的模型获得的纳什均衡的渐近分析。第二个贡献是推导出使用模拟数据获得的纳什均衡解的质量的概率界的表达式。在这种情况下，我们得到非常一般的分布自由的界限，以及依赖于标准的正态假设的界限，并通过Lipschitz连续性扩展到无限游戏的界限。最后，我们介绍了一个新的最大后验估计的纳什均衡的基础上博弈论的模拟数据，并表明它是一致的，几乎肯定是唯一的。
The field of game theory has proved to be of great importance in modeling interactions between self-interested parties in a variety of settings. Traditionally, game-theoretic analysis relied on highly stylized models to provide interesting insights about problems at hand. The shortcoming of such models is that they often do not capture vital detail. On the other hand, many real strategic settings, such as sponsored search auctions and supply-chains, can be modeled in high resolution using simulations. Recently, a number of approaches have been introduced to perform analysis of game-theoretic scenarios via simulation-based models. The first contribution of this work is the asymptotic analysis of Nash equilibria obtained from simulation-based models. The second contribution is to derive expressions for probabilistic bounds on the quality of Nash equilibrium solutions obtained using simulation data. In this vein, we derive very general distribution-free bounds, as well as bounds which rely on the standard normality assumptions, and extend the bounds to infinite games via Lipschitz continuity. Finally, we introduce a new maximum-a-posteriori estimator of Nash equilibria based on game-theoretic simulation data and show that it is consistent and almost surely unique.