Show simple item record

dc.contributor.authorDevanur, Nikhil Rangarajanen_US
dc.date.accessioned2007-08-16T17:57:52Z
dc.date.available2007-08-16T17:57:52Z
dc.date.issued2007-05-18en_US
dc.identifier.urihttp://hdl.handle.net/1853/16282
dc.description.abstractThe 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.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectCombinatorialen_US
dc.subjectNetwork flowen_US
dc.subjectUtilitiesen_US
dc.subjectArrow-Debreuen_US
dc.subjectFisheren_US
dc.titleEfficient Algorithms for Market Equilibriaen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentComputingen_US
dc.description.advisorCommittee Chair: Vazirani, Vijay V.; Committee Member: Khot, Subhash; Committee Member: Randall, Dana; Committee Member: Thomas, Robin; Committee Member: Vempala, Santoshen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record