PPAD-membership for problems with exact rational solutions: a general approach via convex optimization
Author(s)
Filos-Ratsikas, Aris
Hansen, Kristoffer Arnsfelt
Høgh, Kasper
Hollender, Alexandros
Type
Journal Article
Abstract
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problems with polynomial-time verifiable solutions. In particular, we construct a “pseudogate,” coined the linear-OPT-gate, which can be used as a “plug-and-play” component in a piecewise-linear (PL) arithmetic circuit, as an integral component of the “Linear-FIXP” equivalent definition of the class. The linear-OPT-gate can solve several convex optimization programs, including quadratic programs, which often appear organically in the simplest existence proofs for these problems. This effectively transforms existence proofs to PPAD-membership proofs, and consequently establishes the existence of solutions described by rational numbers. Using the linear-OPT-gate, we are able to significantly simplify and generalize almost all known PPAD-membership proofs for finding exact solutions in the application domains of game theory, competitive markets, auto-bidding auctions, and fair division, as well as to obtain new PPAD-membership results for problems in these domains.
Date Issued
2025-08-18
Date Acceptance
2025-12-29
Citation
SIAM journal on computing (Print), 2025
ISSN
0097-5397
Publisher
Society for Industrial and Applied Mathematics
Journal / Book Title
SIAM journal on computing (Print)
Copyright Statement
© 2026 Society for Industrial and Applied Mathematics
Publication Status
Published online
Article Number
STOC23-397-FOCS21-412
Date Publish Online
2026-08-18