FIXP-membership via convex optimization: games, cakes, and markets
Author(s)
Filos-Ratsikas, Aris
Hansen, Kristoffer A
Høgh, Kasper
Hollender, Alexandros
Type
Journal Article
Abstract
We introduce a new technique for proving membership of problems in FIXP: the class capturing the complexity of computing a fixed point of an algebraic circuit. Our technique constructs a “pseudogate,” which can be used as a black box when building FIXP circuits. This pseudogate, which we term the “OPT-gate,” can solve most convex optimization problems. Using the OPT-gate, we prove new FIXP-membership results, and we generalize and simplify several known results from the literature on fair division, game theory, and competitive markets. In particular, we prove complexity results for two classic problems: Computing a market equilibrium in the Arrow–Debreu model with general concave utilities is in FIXP, and computing an envy-free division of a cake with very general valuations is FIXP-complete. We further showcase the wide applicability of our technique by using it to obtain simplified proofs and extensions of known FIXP-membership results for equilibrium computation for various types of strategic games as well as the pseudomarket mechanism of Hylland and Zeckhauser.
Date Issued
2023-04-04
Date Acceptance
2022-12-15
Citation
SIAM journal on computing (Print), 2023
ISSN
0097-5397
Publisher
Society for Industrial and Applied Mathematics
Journal / Book Title
SIAM journal on computing (Print)
Copyright Statement
© 2023 Society for Industrial and Applied Mathematics.
Publication Status
Published online
Date Publish Online
2023-04-04