@inproceedings{3bd9ca9a6e524032bf594ba211ddd805,
title = "Auction algorithms for market equilibrium with weak gross substitute demands and their applications",
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{\^a}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. ",
keywords = "Auction algorithm, Fisher equilibrium, Gale equilibrium, Nash social welfare, Weak gross substitutes",
author = "Jugal Garg and Edin Husi{\'c} and V{\'e}gh, {L{\'a}szl{\'o} A.}",
note = "Funding Information: Jugal Garg was supported by the NSF CAREER Award 1942321. Edin Husi? and L?szl? A. V?gh were supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement ScaleOpt-757481). Funding Information: Funding Jugal Garg was supported by the NSF CAREER Award 1942321. Edin Husi{\'c} and L{\'a}szl{\'o} A. V{\'e}gh were supported by the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement ScaleOpt–757481). Publisher Copyright: {\textcopyright} Jugal Garg, Edin Husi{\'c}, and L{\'a}szl{\'o} A. V{\'e}gh; licensed under Creative Commons License CC-BY 4.0.; 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 ; Conference date: 16-03-2021 Through 19-03-2021",
year = "2021",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2021.33",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Markus Blaser and Benjamin Monmege",
booktitle = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021",
}