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

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 polynomialtime 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 PPADmembership 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 PPADmembership 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.
Original languageEnglish
Title of host publicationProceedings: 56th ACM Symposium on Theory of Computing (STOC)
PublisherACM
Pages1-115
Number of pages115
Publication statusAccepted/In press - 8 Feb 2024
Event56th ACM Symposium on Theory of Computing (STOC) - Vancouver, Canada
Duration: 24 Jun 202428 Jun 2024
Conference number: 56
http://acm-stoc.org/stoc2024/#:~:text=The%2056th%20ACM%20Symposium%20on,Friday%2C%20June%2028%2C%202024.

Conference

Conference56th ACM Symposium on Theory of Computing (STOC)
Abbreviated titleSTOC 2024
Country/TerritoryCanada
CityVancouver
Period24/06/2428/06/24
Internet address

Fingerprint

Dive into the research topics of 'PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization'. Together they form a unique fingerprint.

Cite this