ACO Home Page   Admission Information Program Description Affiliated Faculty Students Alumni Research Program ACO News ACO Events ACO Internal   Georgia Tech College of Computing School of Ind. Sys. Eng. School of Mathematics School of Electrical Eng.   Help Advanced Search   Contact WEBmaster

Nikhil R. Devanur Defense

Title: Efficient Algorithms for Market Equilibria

Time:	Monday, May 14, 10:00am
Location:	Klaus 2108
Advisor:	Dr. Vijay Vazirani
Committee:	Dr. Robin Thomas, School of Mathematics
	Dr. Santosh Vempala, College of Computing
	Dr. Dana Randall, College of Computing
Reader:	Dr. Subhash Khot, College of Computing

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

<Plain-Text Page>  (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: May 17, 2008 Georgia Tech Disclaimer: Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.