We introduce a new technique for proving membership of problems in FIXP - the class capturing the complexity of computing a fixed-point of an algebraic circuit. Our technique constructs a "pseudogate" which can be used as a black box when building FIXP circuits. This pseudogate, which we term the "OPT-gate", can solve most convex optimization problems. Using the OPT-gate, we prove new FIXP-membership results, and we generalize and simplify several known results from the literature on fair division, game theory and competitive markets. In particular, we prove complexity results for two classic problems: computing a market equilibrium in the Arrow-Debreu model with general concave utilities is in FIXP, and computing an envy-free division of a cake with general valuations is FIXP-complete. We further showcase the wide applicability of our technique, by using it to obtain simplified proofs and extensions of known FIXP-membership results for equilibrium computation for various types of strategic games, as well as the pseudomarket mechanism of Hylland and Zeckhauser.
翻译:我们引入了一种新的技术来证明FIXP中的问题的会籍。 这个分类抓住了计算一个代数电路固定点的复杂性。 我们的技术构建了一个“ 假格 ”, 在建造 FIXP 电路时可以用作黑盒。 这个假格, 我们称之为“ OPT 门 ”, 能够解决最大的 convex 优化问题 。 我们用 Offal- Gate, 证明FIXP 的会籍结果, 我们推广和简化了关于公平分化、游戏理论和竞争性市场的文献中的若干已知结果。 特别是, 我们证明两个经典问题具有复杂的结果: 在箭头- Debreu 模型中计算一个与一般 concave 公用事业的市场平衡是 FIXP 。 我们进一步展示了我们技术的广泛适用性, 利用它来获得简化的证明和扩展已知的 FIXP 成员结果, 用于各种战略游戏的均衡计算, 以及Hylland 和 Zeckha 用户的假市场机制。