TY - JOUR
T1 - Ascending-price algorithms for unknown markets
AU - Bei, Xiaohui
AU - Garg, Jugal
AU - Hoefer, Martin
N1 - A one-page abstract of this work appeared in the proceedings of ACM EC’16 [4]. Jugal Garg was supported by NSF CRII Award 1755619. Authors’ addresses: M. Hoefer, Institute for Computer Science, Goethe University Frankfurt, Robert-Mayer-Strasse 11-15, 60325 Frankfurt am Main, Germany; email: [email protected]; J. Garg, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, 104 S Mathews Ave, Urbana, IL 61801, USA; email: [email protected]; X. Bei, Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2019/05-ART37 $15.00 https://doi.org/10.1145/3319394
PY - 2019/5
Y1 - 2019/5
N2 - We design a simple ascending-price algorithm to compute a (1 + ϵ )-approximate equilibrium in Arrow- Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ϵ and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.
AB - We design a simple ascending-price algorithm to compute a (1 + ϵ )-approximate equilibrium in Arrow- Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ϵ and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.
KW - Equilibrium computation
KW - Market equilibrium
KW - Spending constraint utilities
KW - Weak gross substitutes
UR - http://www.scopus.com/inward/record.url?scp=85067230590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85067230590&partnerID=8YFLogxK
U2 - 10.1145/3319394
DO - 10.1145/3319394
M3 - Article
AN - SCOPUS:85067230590
SN - 1549-6325
VL - 15
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 0080
ER -