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

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Hogh, Alexandros Hollender

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

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.

OriginalsprogEngelsk
Titel2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Antal sider12
ForlagIEEE
Publikationsdato2022
Sider827-838
ISBN (Trykt)978-1-6654-2056-3
ISBN (Elektronisk)978-1-6654-2055-6
DOI
StatusUdgivet - 2022
Begivenhed62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, USA
Varighed: 7 feb. 202210 feb. 2022

Konference

Konference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Land/OmrådeUSA
ByVirtual, Online
Periode07/02/202210/02/2022
SponsorIEEE Computer Society Technical Committee on Mathematical Foundations of Computing
NavnProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN0272-5428

Fingeraftryk

Dyk ned i forskningsemnerne om 'FIXP-membership via Convex Optimization: Games, Cakes, and Markets'. Sammen danner de et unikt fingeraftryk.

Citationsformater