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.