ICES: Large: Collaborative Research: Markets, Algorithms, Applications and the Digital Economy

在过去十年中，在理论计算机科学领域所做的广泛工作，利用现代算法设计和算法复杂性理论的强大工具，为各种市场模型和效用函数的市场均衡的可计算性提供了深刻的见解。这是在数理经济学中一项长达一个世纪的工作的基础上进行的，目的是获得一种收敛于均衡的机制--由于对均衡的有效可计算性的某些负面结果，这一目标最终不得不放弃。塔塔咨询公司的工作在一定程度上是受到互联网市场应用程序的推动。目前的项目将沿着几个令人兴奋的方向扩展这项工作。首席原则调查员(PI)最近关于使用互补枢轴算法来获得某些市场模型的可用算法的工作，这些市场模型不太可能具有通常意义上的多项式最坏情况运行时间的有效算法，这为将这种方法扩展到更广泛的市场类别开辟了可能性，特别是有生产的市场。一个重大的新挑战是应对动态变化的市场。在市场应用方面，该团队为该项目带来了丰富的电力市场经验，这些经验来自与计算机科学和控制动力学研究人员的工作。私人投资机构计划利用他们在机制设计方面的专业知识，解决将可再生能源整合到智能电网中的问题，并为辅助服务的定价和分配提供更好的方法，以保证可靠性和稳定性。另一个新的挑战是将一般均衡理论--数理经济学无可争议的皇冠上的明珠--扩展到数字经济。传统的均衡概念不适用于数字产品--一旦生产出来，这类产品的复制品数量就会无限。数字领域非常丰富，在我们的经济中正日益占据更大的份额。因此，当务之急是实现对数字商品定价的理解与对传统商品定价的理解同样深入。该项目将提供算法和对市场计算方面的见解，包括电力市场和互联网交易，从而帮助提高其运作效率。因此，预计它将为科学和工程的进步做出贡献，并促进经济繁荣。

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.