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

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

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.