TY - JOUR
T1 - FIXP-membership via Convex Optimization: Games, Cakes, and Markets
AU - Filos-Ratsikas, Aris
AU - Hansen, Kristoffer Arnsfelt
AU - Høgh, Kasper
AU - Hollender, Alexandros
N1 - Alexandros Hollender was supported by an EPSRC doctoral studentship (Reference 1892947).
PY - 2023/4/4
Y1 - 2023/4/4
N2 - 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.
AB - 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.
U2 - 10.1137/22M1472656
DO - 10.1137/22M1472656
M3 - Article
SN - 0097-5397
SP - 1
EP - 55
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
ER -