论文标题
多项式优化与游戏不完美的游戏之间的桥梁
A Bridge between Polynomial Optimization and Games with Imperfect Recall
论文作者
论文摘要
我们为解决不完美的召回的游戏提供了几个积极和负面的复杂性结果。在另一侧使用这些游戏之间的一对一对应关系，另一侧使用多元多项式，我们表明求解具有不完美召回的游戏就像解决真实的一阶理论的某些问题一样困难。即使对于特定的A-loss游戏，我们也会建立平方根硬度。从积极的一面来看，我们发现对桥梁竞标所激发的游戏和策略的限制，这使多项式时间复杂。
We provide several positive and negative complexity results for solving games with imperfect recall. Using a one-to-one correspondence between these games on one side and multivariate polynomials on the other side, we show that solving games with imperfect recall is as hard as solving certain problems of the first order theory of reals. We establish square root sum hardness even for the specific class of A-loss games. On the positive side, we find restrictions on games and strategies motivated by Bridge bidding that give polynomial-time complexity.
