PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization

我们介绍了一种通用技术，用于证明具有精确有理解的搜索问题属于PPAD，这是包含具有多项式时间可验证解决方案的总搜索问题的最著名的类之一。特别地，我们构造了一个“伪门”，称为线性-OPT-门，它可以作为分段线性（PL）算术电路中的“即插即用”组件，作为“线性-FIXP”等价定义的一个组成部分。线性-OPT-门可以解决几个凸优化问题，包括二次规划问题，这些问题通常在这些问题的最简单存在证明中自然出现。这有效地将存在证明转化为PPAD成员证明，从而确立了由有理数描述的解的存在。 使用线性-OPT-门，我们能够显著简化和推广几乎所有已知的PPAD成员证明，以在博弈论、竞争市场、自动出价拍卖和公平分配等应用领域中寻找精确解决方案，并获得这些领域问题的新的PPAD成员结果。

在PPAD类问题中验证精确有理解的成员身份

构造了一种名为线性-OPT-门的伪门，可以用作分段线性（PL）算术电路的组成部分，用于解决包括二次规划在内的几个凸优化问题，从而将存在证明转化为PPAD成员身份证明。

使用线性-OPT-门，能够显著简化和推广几乎所有已知的PPAD成员身份证明，适用于博弈论、竞争市场、自动出价拍卖和公平分配等应用领域的问题。

最近的相关研究包括：“PPAD类问题的定量结果”、“PPAD完整性证明”和“PPAD类问题的固定点等价定义”。