# Computing Walrasian Equilibria: Fast Algorithms and Structural Properties

### Venue

ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) (2017)

### Publication Year

2017

### Authors

Renato Paes Leme, Sam Chiu-wai Wong

### BibTeX

## 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 O˜(n) times and takes O˜(n3) 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 O˜((mn+n3)TV) where TV 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.