Defines reciprocal fair and core-stable data exchanges, proves exact existence for monotone continuous utilities, and places approximate computation in the complexity class CLS for submodular settings.
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted 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 the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.
fields
cs.GT 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On the Theoretical Foundations of Data Exchange Economies
Defines reciprocal fair and core-stable data exchanges, proves exact existence for monotone continuous utilities, and places approximate computation in the complexity class CLS for submodular settings.