Extensive work over the last decade, done within theoretical computer science, has provided deep insights into the computability of market equilibria for various market models and utility functions, using the powerful tools of the modern theories of algorithmic design and algorithmic complexity. This follows up on a century-long work, within mathematical economics, on obtaining a mechanism that converges to equilibrium -- a goal that had to be eventually abandoned due to certain negative results on efficient computability of the equilibrium. The work in TCS was motivated in part by applications to markets on the Internet.
The current project will extend this work along several exciting directions. Recent work of the lead Principle Investigator (PI) on using complementary pivot algorithms, for obtaining usable algorithms for certain market models that are unlikely to have efficient algorithms in the usual sense of polynomial worst-case running time, opens up the possibility of extending this approach to broader classes of markets, in particular, markets with production. A major new challenge is to address dynamically evolving markets.
In terms of applications of markets, the team brings to this project a wealth of experience on electricity markets, gained from work done with researchers in computer science and control dynamics. The PIs plan on bringing their expertise in mechanism design to bear on the problems of integrating renewable energy sources into the smart grid and providing better approaches to the pricing and allocation of ancillary services to guarantee reliability and stability. Another new challenge is to extend general equilibrium theory, the undisputed crown jewel of mathematical economics, to the digital economy. The traditional notion of equilibrium is not applicable to digital goods -- once produced, an unbounded number of copies of such goods are available. The digital realm is very rich and is increasingly occupying a larger share of our economy. It is imperative, therefore, to achieve the same depth of understanding of pricing for digital goods as was obtained for conventional goods.
This project will provide algorithms and insights into the computational aspects of markets, including electricity markets and transactions on the Internet, thereby helping make their operation more efficient. Hence, it is expected to contribute to advances in science and engineering, as well as to promote economic prosperity.
