TY - GEN

T1 - Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets

AU - Garg, Jugal

AU - Tao, Yixin

AU - Vegh, Laszlo A.

N1 - Funding Information:
∗A full version of the paper can be accessed at https://arxiv.org/abs/2107.05700. The first author is supported by NSF Grant CCF–1942321 (CAREER). The second and third authors received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt– 757481). †University of Illinois at Urbana-Champaign. ‡London School of Economics and Political Science. §London School of Economics and Political Science.
Publisher Copyright:
Copyright © 2022 by SIAM.

PY - 2022

Y1 - 2022

N2 - We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of goods is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017). The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by `robust' utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow{Debreu exchange market model.

AB - We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of goods is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017). The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by `robust' utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow{Debreu exchange market model.

UR - http://www.scopus.com/inward/record.url?scp=85130735800&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130735800&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85130735800

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2269

EP - 2284

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -