Do Prices Coordinate Markets?

Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, Rakesh Vohra

[arXiv]

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:

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.

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).

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.