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.
| Original language | English (US) |
|---|---|
| Article number | 0080 |
| Journal | ACM Transactions on Algorithms |
| Volume | 15 |
| Issue number | 3 |
| DOIs | |
| State | Published - May 2019 |
Fingerprint
Keywords
- Equilibrium computation
- Market equilibrium
- Spending constraint utilities
- Weak gross substitutes
ASJC Scopus subject areas
- Mathematics (miscellaneous)
Cite this
Ascending-price algorithms for unknown markets. / Bei, Xiaohui; Garg, Jugal; Hoefer, Martin.
In: ACM Transactions on Algorithms, Vol. 15, No. 3, 0080, 05.2019.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Ascending-price algorithms for unknown markets
AU - Bei, Xiaohui
AU - Garg, Jugal
AU - Hoefer, Martin
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
VL - 15
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 3
M1 - 0080
ER -