Auction algorithms for market equilibrium with weak gross substitute demands and their applications

Jugal Garg, Edin Husić, László A. Végh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the Arrow-Debreu exchange market model where agents' demands satisfy the weak gross substitutes (WGS) property. This is a well-studied property, in particular, it gives a sufficient condition for the convergence of the classical tâtonnement dynamics. In this paper, we present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands. Such auction algorithms have been previously known for restricted classes of WGS demands only. As an application of our technique, we obtain an efficient algorithm to find an approximate spendingrestricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for NSW with budget separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

Original languageEnglish (US)
Title of host publication38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
EditorsMarkus Blaser, Benjamin Monmege
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771801
DOIs
StatePublished - Mar 1 2021
Event38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 - Virtual, Saarbrucken, Germany
Duration: Mar 16 2021Mar 19 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume187
ISSN (Print)1868-8969

Conference

Conference38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
Country/TerritoryGermany
CityVirtual, Saarbrucken
Period3/16/213/19/21

Keywords

  • Auction algorithm
  • Fisher equilibrium
  • Gale equilibrium
  • Nash social welfare
  • Weak gross substitutes

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Auction algorithms for market equilibrium with weak gross substitute demands and their applications'. Together they form a unique fingerprint.

Cite this