FIXP-membership via Convex Optimization: Games, Cakes, and Markets



Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Hansen, Kristoffer Arnsfelt, Hogh, Kasper and Hollender, Alexandros
(2022) FIXP-membership via Convex Optimization: Games, Cakes, and Markets. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022-2-7 - 2022-2-10, Denver, Colorado, USA.

Access the full-text of this item by clicking on the Open Access link.
[img] Text
Cakes__Games__Markets_and_more.pdf - Submitted version

Download (416kB) | Preview

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 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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: FIXP, fixed point theorems, game theory, equilibrium computation, Arrow-Debreu markets, cake cutting, stochastic games
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 06 Oct 2021 09:12
Last Modified: 18 Jan 2023 21:27
DOI: 10.1109/FOCS52979.2021.00085
Open Access URL: https://arxiv.org/pdf/2111.06878.pdf
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3139461