On Algorithms for Nash Equilibria
On Algorithms for Nash Equilibria
复制标题
纳什均衡算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Daniel Kane
中科院分区：
文献类型：
--
作者：
Timothy G. Abbott;Daniel Kane
我们提出了一份关于寻找两人矩阵博弈样本纳什均衡的算法正在进行的研究的进展报告。我们提供了背景材料、新结果和进一步研究的方向的组合。我们的新结果包括从一般对策到{0，1}对策的简化，寻找纳什均衡的复杂性与程序混淆之间的关系，以及具有有界树宽和度的对策的固定参数易处理算法。
We present a progress report on ongoing research in algorithms for finding sample Nash equilibria of two-player matrix games. We present a combination of background material, new results, and promising directions for further study. Our new results include a reduction from general games to {0, 1} games, a relation between the complexity of finding Nash equilibria and program obfuscation, and a fixedparameter tractable algorithm for games with bounded treewidth and degree.