Title:
Efficient Algorithms for Market Equilibria
Efficient Algorithms for Market Equilibria
Author(s)
Devanur, Nikhil Rangarajan
Advisor(s)
Vazirani, Vijay V.
Editor(s)
Collections
Supplementary to
Permanent Link
Abstract
The mathematical modelling of a market, and the proof of existence of
equilibria have been of central importance in mathematical economics.
Since the existence proof is non-constructive in general,
a natural question is if computation of equilibria can be done efficiently.
Moreover, the emergence of Internet and e-commerce has given rise to new
markets that have completely changed the traditional notions.
Add to this the pervasiveness of computing resources,
and an algorithmic theory of market equilibrium becomes highly desirable.
The goal of this thesis is to provide polynomial time algorithms for
various market models.
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 exchange them for other goods.
We give the first polynomial time algorithm for exactly computing an
equilibrium in the Fisher model with linear utilities. We also show that
the basic ideas in this algorithm can be extended to give a strongly
polynomial time approximation scheme in the Arrow-Debreu model.
We also give several existential, algorithmic and structural
results for new market models:
- the *spending constraint* utilities (defined by Vazirani) that captures
the "diminishing returns" property while generalizing the algorithm for
the linear case.
- the capacity allocation market (defined by Kelly), motivated
by the study of fairness and stability of the Transmission Control
Protocol (TCP) for the Internet, and more generally the class of
Eisenberg-Gale (EG) markets (defined by Jain and Vazirani).
In addition, we consider the adwords market
on search engines and show that some of these models are a natural fit
in this setting. Finally, this line of research has given insights into
the fundamental techniques in algorithm design. The primal-dual schema
has been a great success in combinatorial optimization and approximation
algorithms. Our algorithms use this paradigm in the enhanced setting of
Karush-Kuhn-Tucker (KKT) conditions and convex programs.
Sponsor
Date Issued
2007-05-18
Extent
Resource Type
Text
Resource Subtype
Dissertation