Computing Walrasian equilibria: fast algorithms and structural properties

DOI10.1137/1.9781611974782.42zbMATH Open1417.91330arXiv1511.04032OpenAlexW2341533178MaRDI QIDQ4575778FDOQ4575778

Authors: Renato Paes Leme, Sam Chiu-wai Wong 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and emph{general} buyer valuations having only access to an emph{aggregate demand oracle}, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle $widetildeO(n)$ times and takes $widetildeO(n^3)$ time, where $n$ is the number of goods. At the heart of our solution is a method for exactly minimizing certain convex functions which cannot be evaluated but for which the subgradients can be computed. We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the emph{value oracle model}. Our algorithm has running time $widetildeO((mn+n^3)T_V)$ where $T_V$ is the cost of querying the value oracle. A key technical ingredient is to regularize a convex programming formulation of the problem in a way that subgradients are cheap to compute. En route, we give necessary and sufficient conditions for the existence of emph{robust Walrasian prices}, i.e., prices for which each agent has a unique demanded bundle and the demanded bundles clear the market. When such prices exist, the market can be perfectly coordinated by solely using prices.

Full work available at URL: https://arxiv.org/abs/1511.04032

Recommendations

• Computing Walrasian equilibria: fast algorithms and structural properties
• A simple and efficient algorithm for computing market equilibria
• On the polynomial time computation of equilibria for certain exchange economies
• Market equilibrium via the excess demand function
• Gross substitutability: an algorithmic survey

zbMATH Keywords

convex programmingpolynomial time algorithmWalrasian equilibria computation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) General equilibrium theory (91B50)

Cited In (9)

• Do prices coordinate markets?
• Computing Walrasian equilibria: fast algorithms and structural properties
• Computing the Evolution of Walrasian Behaviour
• Walrasian equilibria from an optimization perspective: A guide to the literature
• Gross substitutability: an algorithmic survey
• Walrasian equilibrium: Hardness, approximations and tractable instances
• A constant factor prophet inequality for online combinatorial auctions
• Title not available (Why is that?)
• Equilibrium, auction, and generalized gross substitutes and complements

This page was built for publication: Computing Walrasian equilibria: fast algorithms and structural properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575778)