PPAD-membership for problems with exact rational solutions: a general approach via convex optimization
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...
| Huvudupphovsmän: | , , , |
|---|---|
| Materialtyp: | Conference item |
| Språk: | English |
| Publicerad: |
Association for Computing Machinery
2024
|
| _version_ | 1826313290035232768 |
|---|---|
| author | Filos-Ratsikas, A Hansen, KA Høgh, K Hollender, A |
| author_facet | Filos-Ratsikas, A Hansen, KA Høgh, K Hollender, A |
| author_sort | Filos-Ratsikas, A |
| collection | OXFORD |
| description | 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.<br>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. |
| first_indexed | 2024-09-25T04:10:43Z |
| format | Conference item |
| id | oxford-uuid:89107e9c-59ed-4bab-863f-b60a49f13f4c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:10:43Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:89107e9c-59ed-4bab-863f-b60a49f13f4c2024-06-14T15:26:27ZPPAD-membership for problems with exact rational solutions: a general approach via convex optimizationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:89107e9c-59ed-4bab-863f-b60a49f13f4cEnglishSymplectic ElementsAssociation for Computing Machinery2024Filos-Ratsikas, AHansen, KAHøgh, KHollender, AWe 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.<br>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. |
| spellingShingle | Filos-Ratsikas, A Hansen, KA Høgh, K Hollender, A PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title | PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title_full | PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title_fullStr | PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title_full_unstemmed | PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title_short | PPAD-membership for problems with exact rational solutions: a general approach via convex optimization |
| title_sort | ppad membership for problems with exact rational solutions a general approach via convex optimization |
| work_keys_str_mv | AT filosratsikasa ppadmembershipforproblemswithexactrationalsolutionsageneralapproachviaconvexoptimization AT hansenka ppadmembershipforproblemswithexactrationalsolutionsageneralapproachviaconvexoptimization AT høghk ppadmembershipforproblemswithexactrationalsolutionsageneralapproachviaconvexoptimization AT hollendera ppadmembershipforproblemswithexactrationalsolutionsageneralapproachviaconvexoptimization |