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

Aris Filos-Ratsikas; Kristoffer Arnsfelt Hansen; Kasper Høgh; Alexandros Hollender

doi:10.1109/FOCS52979.2021.00085

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

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	827-838
Number of pages	12
ISBN (Electronic)	978-1-6654-2055-6
ISBN (Print)	978-1-6654-2056-3
DOIs	https://doi.org/10.1109/FOCS52979.2021.00085
Publication status	Published - 4 Mar 2022
Event	62nd Annual Symposium on Foundations of Computer Science, 2022 - Online Duration: 7 Feb 2022 → 10 Feb 2022 Conference number: 62 https://focs2021.cs.colorado.edu/

Publication series

Name	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science
Publisher	IEEE
ISSN (Print)	1523-8288
ISSN (Electronic)	2575-8454

Conference

Conference	62nd Annual Symposium on Foundations of Computer Science, 2022
Abbreviated title	FOCS 2022
Period	7/02/22 → 10/02/22
Internet address	https://focs2021.cs.colorado.edu/

Keywords

FIXP
fixed point theorems
game theory
equilibrium computation
Arrow-Debreu markets
cake cutting
stochastic games

Access to Document

10.1109/FOCS52979.2021.00085Licence: All Rights Reserved

https://ieeexplore.ieee.org/document/9719799Licence: All Rights Reserved

Cite this

Filos-Ratsikas, A., Hansen, K. A., Høgh, K., & Hollender, A. (2022). FIXP-membership via Convex Optimization: Games, Cakes, and Markets. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 827-838). (2021 IEEE 62nd Annual Symposium on Foundations of Computer Science). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/FOCS52979.2021.00085

@inproceedings{ea9e500419fe4839a9c84b533c2e82c3,

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

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

keywords = "FIXP, fixed point theorems, game theory, equilibrium computation, Arrow-Debreu markets, cake cutting, stochastic games",

author = "Aris Filos-Ratsikas and Hansen, {Kristoffer Arnsfelt} and Kasper H{\o}gh and Alexandros Hollender",

note = "Funding Information: ACKNOWLEDGMENTS We thank the anonymous reviewers for comments and suggestions that helped improve the presentation of the paper. We thank Kousha Etessami for discussions about the Kakutani fixed point theorem. Kristoffer Arnsfelt Hansen and Kasper H{\o}gh were supported by the Independent Research Fund Denmark under grant no. 9040-00433B. Alexandros Hollender was supported by an EPSRC doctoral studentship (Reference 1892947). Publisher Copyright: {\textcopyright} 2022 IEEE.; 62nd Annual Symposium on Foundations of Computer Science, 2022, FOCS 2022 ; Conference date: 07-02-2022 Through 10-02-2022",

year = "2022",

month = mar,

day = "4",

doi = "10.1109/FOCS52979.2021.00085",

language = "English",

isbn = "978-1-6654-2056-3",

series = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

pages = "827--838",

booktitle = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)",

address = "United States",

url = "https://focs2021.cs.colorado.edu/",

}

Filos-Ratsikas, A, Hansen, KA, Høgh, K & Hollender, A 2022, FIXP-membership via Convex Optimization: Games, Cakes, and Markets. in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers (IEEE), pp. 827-838, 62nd Annual Symposium on Foundations of Computer Science, 2022, 7/02/22. https://doi.org/10.1109/FOCS52979.2021.00085

FIXP-membership via Convex Optimization: Games, Cakes, and Markets. / Filos-Ratsikas, Aris; Hansen, Kristoffer Arnsfelt; Høgh, Kasper et al.

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Institute of Electrical and Electronics Engineers (IEEE), 2022. p. 827-838 (2021 IEEE 62nd Annual Symposium on Foundations of Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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 - Conference code: 62

PY - 2022/3/4

Y1 - 2022/3/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 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 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.

KW - FIXP

KW - fixed point theorems

KW - game theory

KW - equilibrium computation

KW - Arrow-Debreu markets

KW - cake cutting

KW - stochastic games

U2 - 10.1109/FOCS52979.2021.00085

DO - 10.1109/FOCS52979.2021.00085

M3 - Conference contribution

SN - 978-1-6654-2056-3

T3 - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science

SP - 827

EP - 838

BT - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 62nd Annual Symposium on Foundations of Computer Science, 2022

Y2 - 7 February 2022 through 10 February 2022

ER -

Filos-Ratsikas A, Hansen KA, Høgh K, Hollender A. FIXP-membership via Convex Optimization: Games, Cakes, and Markets. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Institute of Electrical and Electronics Engineers (IEEE). 2022. p. 827-838. (2021 IEEE 62nd Annual Symposium on Foundations of Computer Science). doi: 10.1109/FOCS52979.2021.00085

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this