### 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 1 2019 |

### Fingerprint

### Keywords

- Equilibrium computation
- Market equilibrium
- Spending constraint utilities
- Weak gross substitutes

### ASJC Scopus subject areas

- Mathematics (miscellaneous)

### Cite this

*ACM Transactions on Algorithms*,

*15*(3), [0080]. https://doi.org/10.1145/3319394

**Ascending-price algorithms for unknown markets.** / Bei, Xiaohui; Garg, Jugal; Hoefer, Martin.

Research output: Contribution to journal › Article

*ACM Transactions on Algorithms*, vol. 15, no. 3, 0080. https://doi.org/10.1145/3319394

}

TY - JOUR

T1 - Ascending-price algorithms for unknown markets

AU - Bei, Xiaohui

AU - Garg, Jugal

AU - Hoefer, Martin

PY - 2019/5/1

Y1 - 2019/5/1

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

VL - 15

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 0080

ER -