PPAD-Membership for Problems With Exact Rational Solutions: A General Approach via Convex Optimization
SIAM Journal on Computing · 18.08.2026 · STOC24-297-STOC24-421
DOI: 10.1137/24m1689089 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 18.08.2026. Verfasst von Aris Filos-Ratsikas und 3 weiteren Autor:innen. Die Arbeit nennt 92 Literaturangaben. Gefördert von: Independent Research Fund Denmark, Swiss State Secretariat for Education Research and Innovation, Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
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.
Förderung
- Independent Research Fund Denmark
- Swiss State Secretariat for Education Research and Innovation
- Engineering and Physical Sciences Research Council
Zitieren
APA
Filos-Ratsikas, A., Hansen, K. A., Høgh, K., & Hollender, A. (2026). PPAD-Membership for Problems With Exact Rational Solutions: A General Approach via Convex Optimization. SIAM Journal on Computing, STOC24-297-STOC24-421. https://doi.org/10.1137/24m1689089
Vancouver
Filos-Ratsikas A, Hansen KA, Høgh K, Hollender A. PPAD-Membership for Problems With Exact Rational Solutions: A General Approach via Convex Optimization. SIAM Journal on Computing. 2026:STOC24-297-STOC24-421. doi:10.1137/24m1689089
BibTeX
@article{FilosRatsikas2026,
author = {Filos-Ratsikas, Aris and Hansen, Kristoffer Arnsfelt and Høgh, Kasper and Hollender, Alexandros},
title = {PPAD-Membership for Problems With Exact Rational Solutions: A General Approach via Convex Optimization},
journal = {SIAM Journal on Computing},
year = {2026},
pages = {STOC24--297--STOC24--421},
doi = {10.1137/24m1689089}
}
EUVIMED