Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/150300
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBei, Xiaohuien_US
dc.contributor.authorGarg, Jugalen_US
dc.contributor.authorHoefer, Martinen_US
dc.date.accessioned2021-05-20T06:48:37Z-
dc.date.available2021-05-20T06:48:37Z-
dc.date.issued2019-
dc.identifier.citationBei, X., Garg, J. & Hoefer, M. (2019). Ascending-price algorithms for unknown markets. ACM Transactions On Algorithms, 15(3), 37-. https://dx.doi.org/10.1145/3319394en_US
dc.identifier.issn1549-6325en_US
dc.identifier.urihttps://hdl.handle.net/10356/150300-
dc.description.abstractWe 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.en_US
dc.language.isoenen_US
dc.relation.ispartofACM Transactions on Algorithmsen_US
dc.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).en_US
dc.subjectScience::Mathematicsen_US
dc.titleAscending-price algorithms for unknown marketsen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.identifier.doi10.1145/3319394-
dc.description.versionAccepted versionen_US
dc.identifier.scopus2-s2.0-85067230590-
dc.identifier.issue3en_US
dc.identifier.volume15en_US
dc.identifier.spage37en_US
dc.subject.keywordsMarket Equilibriumen_US
dc.subject.keywordsEquilibrium Computationen_US
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Ascending price algorithms for unknown markets.pdf905.62 kBAdobe PDFView/Open

SCOPUSTM   
Citations 20

2
Updated on May 20, 2021

PublonsTM
Citations 20

2
Updated on May 20, 2021

Page view(s)

127
Updated on Jul 3, 2022

Download(s)

16
Updated on Jul 3, 2022

Google ScholarTM

Check

Altmetric


Plumx

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