Ascending-Price Algorithms for Unknown Markets

摘要: We design a simple ascending-price algorithm to compute (1+\varepsilon)-approximate equilibrium in Arrow-Debreu exchange markets with weak gross substitute (WGS) property, which runs time polynomial market parameters and log 1/varepsilon. This is the first polynomial-time for most of known tractable classes markets, easy implement avoids heavy machinery such as ellipsoid method. In addition, our can be applied an unknown setting without exact knowledge about number agents, their individual utilities endowments. Instead, only relies on queries global demand oracle by posting prices receiving aggregate goods feedback. When demands are real-valued functions prices, oracles return values bounded precision based real utility functions. Due this more realistic assumption, representation become major technical challenge, we develop new tools insights that may independent interest. Furthermore, approach also gives spending constraint utilities, piecewise linear concave generalization utilities. resolves open problem posed by~\citet{DuanM15}.