Efficient Algorithms For Unknown Markets

I survey our recent work on revealed preference problems in classic market models without information about the number of agents, their individual utilities and endowments. Here we only rely on queries that return aggregate demand for goods in order to, e.g., learn utility functions or compute a market equilibrium.

As a main result, we design a simple ascending-price algorithm to compute a (1+eps)-approx. equilibrium in exchange markets with weak gross substitute (WGS) property. It runs in time polynomial in market parameters and log(1/eps). It is the first efficient algorithm for this broad class of markets which is easy to implement and avoids heavy machinery such as the ellipsoid method. Moreover, we show several extensions of our technique – the first efficient algorithm to compute an exact equilibrium for markets with spending constraint utilities, and the first efficient algorithm for Fisher markets with budget-additive utilities.