Nash equilibria in random games
Nash equilibria in random games
复制标题
DOI：
10.1002/rsa.20199
复制
发表时间：
2007-12-01
影响因子：
1
通讯作者：
Vetta, Adrian
中科院分区：
文献类型：
--
作者：
Barany, Irnre;Vempala, Santosh;Vetta, Adrian
我们考虑2人随机博弈的纳什均衡，并分析了一个简单的拉斯维加斯算法找到一个均衡。该算法是组合的，总是找到一个平衡;在m × n支付矩阵，它运行的时间为O（m（2）n log log n + n（2）m log log m）的概率。我们的结果如下显示，一个2人的随机游戏有一个纳什支持的大小为2的高概率，至少1 - O（1/ log n）。我们的主要工具是均衡的公式化。(C)2007 Wiley Periodicals，Inc.
We consider Nash equilibria in 2-player random games and analyze a simple Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a equilibrium; on m x n payoff matrices, it runs in time O(m(2)n log log n + n(2)m log log m) with probability. Our result follows from showing that a 2-player random game has a Nash with supports of size two with high probability, at least 1 - O(1/ log n). Our main tool is a formulation of equilibria. (C) 2007 Wiley Periodicals, Inc.