Please use this identifier to cite or link to this item:
Title: Ascending-price algorithms for unknown markets
Authors: Bei, Xiaohui
Garg, Jugal
Hoefer, Martin
Keywords: Science::Mathematics
Issue Date: 2019
Source: Bei, X., Garg, J. & Hoefer, M. (2019). Ascending-price algorithms for unknown markets. ACM Transactions On Algorithms, 15(3), 37-.
Journal: ACM Transactions on Algorithms
Abstract: 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.
ISSN: 1549-6325
DOI: 10.1145/3319394
Rights: © 2019 The Owner/Author(s). All rights reserved. This paper was published by Association for Computing Machinery in ACM Transactions on Algorithms and is made available with permission of The Owner/Author(s).
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Ascending price algorithms for unknown markets.pdf905.62 kBAdobe PDFView/Open

Citations 20

Updated on May 20, 2021

Citations 20

Updated on May 20, 2021

Page view(s)

Updated on Jul 3, 2022


Updated on Jul 3, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.