Ascending-price algorithms for unknown markets

Xiaohui Bei, Jugal Garg, Martin Hoefer

Research output: Contribution to journalArticle

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 languageEnglish (US)
Article number0080
JournalACM Transactions on Algorithms
Volume15
Issue number3
DOIs
StatePublished - May 2019

Fingerprint

Unknown
Polynomial-time Algorithm
Ellipsoid Method
Substitute
Gross
Open Problems
Resolve
Query
Polynomial
Market
Demand
Design
Knowledge
Class

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 journalArticle

Bei, Xiaohui ; Garg, Jugal ; Hoefer, Martin. / Ascending-price algorithms for unknown markets. In: ACM Transactions on Algorithms. 2019 ; Vol. 15, No. 3.
@article{cc06c7cc467f4a589e843239226b442e,
title = "Ascending-price algorithms for unknown markets",
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.",
keywords = "Equilibrium computation, Market equilibrium, Spending constraint utilities, Weak gross substitutes",
author = "Xiaohui Bei and Jugal Garg and Martin Hoefer",
year = "2019",
month = "5",
doi = "10.1145/3319394",
language = "English (US)",
volume = "15",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

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 -