Market Equilibrium: Models and Algorithms

Nikhil Devanur

Georgia Tech

The mathematical modelling of a market, and the proof of existence of equilibria have been of central importance in mathematical economics. Two basic market models are the Fisher model: one in which there is a demarcation between buyers and sellers, buyers are interested in the goods that the sellers possess, and sellers are only interested in the money that the buyers have; and the Arrow-Debreu model: everyone has an endowment of goods, and wants to sell their goods and buy those of others. Since the existence proof is non-constructive in general, a natural question is if computation of equilibria can be done efficiently. From a computational point of view, the representation of the utility functions plays an important role. Traditionally, the utility function is assumed to be given explicitly, or through an oracle. But the utility function could also be represented implicitly, for instance, a market could be represented by a network, with each buyer being a source-sink pair, and the goods being the edge capacities. The utility of any buyer is the maximum flow he can send from his source to his sink using the edge capacities he is allocated. This is an instance of a "resource allocation market", and was defined by Kelly in order to understand TCP congestion control. In fact, further abstraction gives a market with no goods! A Uniform Utility Allocation (UUA) market is defined simply by a polytope given by packing constraints, which represents the set of feasible utilities.

I will present combinatorial algorithms to compute equilibria in the traditional Fisher and Arrow-Debreu market models with linear utilites. I will also present some recent algorithmic and structural results in the resource allocation and UUA framework.