Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)
Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)
复制标题
随机 Bimatrix 博弈渐近容易求解（简单证明）
DOI：
--
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
Panagiota N. Panagopoulou;P. Spirakis
我们专注于计算近似纳什均衡和支持的近似纳什均衡的随机双矩阵游戏，其中每个玩家的收益是有界的和独立的随机变量，不一定是相同的分布，但几乎共同的期望的问题。我们表明，完全混合的统一策略配置文件，即，混合策略的组合（每个参与人一个），其中每个参与人以相等的概率使用她的每一个可用的纯策略，是具有高概率的$\sqrt{\frac{3\ln n}{n}}$-纳什均衡和$\sqrt{\frac{3\ln n}{n}}$-良好支持的纳什均衡，其中n是每个参与人可用的纯策略的数量。这表明，完全混合的、统一的策略配置文件是随机双矩阵博弈的几乎纳什均衡，因为它很有可能是一个n-良好支持的纳什均衡，当n趋于无穷大时，n趋于零。
We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player’s payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a $\sqrt{\frac{\ln n}{n}}$-Nash equilibrium and a $\sqrt{\frac{3\ln n}{n}}$-well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ϵ-well-supported Nash equilibrium where ϵ tends to zero as n tends to infinity.