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

arXiv: https://arxiv.org/abs/2312.01237 · HTML: https://mlsanity.com/paper/2312.01237/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2023.

## Built on by (most cited first, 2 of 2)

- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

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.