We present a technique for reducing a normal-form (aka. (bi)matrix) game, O, to a smaller normal-form game, R, for the purpose of computing a Nash equilibrium. This is done by computing a Nash equilibrium for a subcomponent, G, of O for which a certain condition holds. We also show that such a subcomponent G on which to apply the technique can be found in polynomial time (if it exists), by showing that the condition that G needs to satisfy can be modeled as a Horn satisfiability problem. We show that the technique does not extend to computing Pareto-optimal or welfare-maximizing equilibria. We present a class of games, which we call ALAGIU (Any Lower Action Gives Identical Utility) games, for which recursive application of (special cases of) the technique is sufficient for finding a Nash equilibrium in linear time. Finally, we discuss using the technique to compute approximate Nash equilibria.
展开▼
机译：为了达到以下目的，我们提出了一种将规范形式（aka。（bi）matrix）游戏 O 简化为较小规范形式游戏 R 的技术。计算纳什均衡。这是通过计算满足特定条件的 O 子元素 G 的Nash平衡来完成的。通过显示 G 需要满足的条件，我们还表明可以在多项式时间（如果存在）中找到要应用该技术的子组件 G 。可以建模为Horn可满足性问题。我们表明，该技术不扩展到计算帕累托最优或福利最大化均衡。我们提出一类游戏，我们称之为ALAGIU（任何低等动作赋予相同效用）游戏，对于该类游戏（特殊情况）的递归应用足以在线性时间内找到纳什均衡。最后，我们讨论了使用该技术来计算近似纳什均衡。
展开▼
