Do Prices Coordinate Markets?
Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, Rakesh Vohra
Walrasian equilibrium prices have a remarkable property: they allow
each buyer to purchase a bundle of goods that she finds the most
desirable, while guaranteeing that the induced allocation over all
buyers will globally maximize social welfare. However, this clean
story has two important caveats:
To better understand the performance of Walrasian prices when facing
these two problems, we give results of two sorts. First, we show a
mild genericity condition on valuations under which the minimal
Walrasian equilibrium prices induce allocations which result in low
over-demand for arbitrary (even adversarial) tie-breaking by buyers.
In fact, our results show that the over-demand of any good can be
bounded by $1$, which is the best possible. We demonstrate our results
in the unit demand setting and give an extension to the class of
Matroid Based Valuations (MBV), conjectured to be equal to the class
of Gross Substitute valuations (GS).
- First, the prices may induce indifferences---in fact, the
minimal equilibrium prices necessarily induce
indifferences. In general, buyers may need to coordinate with one
another to resolve these indifferences, so the prices alone are
not sufficient to coordinate the market.
- Second, although we know natural procedures which converge to
Walrasian equilibrium prices on a fixed population, in practice
buyers typically observe prices without participating in a
tatonnement process. These prices cannot be perfect Walrasian
equilibrium prices, but instead somehow reflect distributional
information about the market.
Second, we use techniques from learning theory to argue that the
over-demand and welfare induced by a price vector converges to its
expectation uniformly over the class of all price vectors, with sample
complexity only linear in the number of goods in the market in the
former case and quadratic in the number of goods in the latter
case. These results make no assumption on the form of the valuation
functions of the buyers.
Combining these two results implies that under a mild genericity
condition, the exact Walrasian equilibrium prices computed in a market
are guaranteed to induce both low over-demand and high welfare when
used in a new market, in which agents are sampled independently from
the same distribution, whenever the number of agents is larger than
the number of commodities in the market.