Document Type


Date of Degree

Fall 2009

Degree Name

PhD (Doctor of Philosophy)

Degree In

Computer Science

First Advisor

Kasturi Varadarajan

First Committee Member

Samuel Burer

Second Committee Member

Sukumar Ghosh

Third Committee Member

Suely Oliveira

Fourth Committee Member

Sriram Pemmaraju


It is demonstrated that for certain markets where traders have constant elasticity of substitution utility (CES) functions, the existence of a price equilibrium can be determined in polynomial time. It is also shown that for a certain range of elasticity of substitution where the CES market does not satisfy gross subsitutability that price equilibira can be computed in polynomial time. It is also shown that for markets satisfying gross substitutability, equilibria can be computed in polynomial time even if the excess demand is a correspondence. On the experimental side, equilibrium computation algorithms from computer science without running time guarantees are shown to be competitive with software packages used in applied microeconomics. Simulations also lend support to the Nash equilibrium solution concept by showing that agents employing heuristics in a restricted form of Texas Holdem converge to an approximate equilibrium. Monte Carlo simulations also indicate the long run preponderance of skill over chance in Holdem tournaments.


Algorithms, Game Theory, Market Equilibrium


xiii, 146 pages


Includes bibliographical references (pages 139-146).


Copyright 2009 Benton John McCune