Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and lot of work has been done in its computational complexity. If the payoffs are permitted to be real numbers, the answer is no, for continuity reasons. It is worthwhile to investigate the precise degree of non-computability (the Weihrauch degree), since knowing the degree entails what other approaches are available (eg, is there a randomized algorithm with positive success change?). The two player case has already been fully classified, but the multiplayer case remains open and is addressed here. Our approach involves classifying the degree of finding roots of polynomials, and lifting this to systems of polynomial inequalities via cylindrical algebraic decomposition.
翻译：是否有一种算法以正常形式游戏作为输入, 输出纳什均衡? 如果报酬是整数, 答案是肯定的, 并且计算的复杂性已经做了很多工作。 如果允许报酬是真实数字, 答案是否定的, 是因为连续性的原因。 值得调查不可计算的确切程度( Weihrauch 度 ), 因为知道这个程度意味着其他方法( 例如, 是否有随机算法, 并有积极的成功变化 ) 。 两个玩家案例已经完全分类了, 但多玩家案例仍然开放, 并在这里处理。 我们的方法是分类多面体的根部, 并通过圆柱形变形变形将它提升到多面不平等的系统中 。
相关内容
微信扫码咨询专知VIP会员