Algorithms for planning under uncertainty and in the presence of selfish users

过去几年的技术进步导致系统的规模和复杂性迅速增加。这种系统的设计、维护和管理，特别是高速电信网络和分散式网络，如因特网，是未来重要的计算和通信平台，提出了若干挑战。在本提案中，我们将集中讨论在设计这种系统时出现的两个重要问题：（a）数据或规格的不确定性。不确定性是许多实际决策环境的一个方面，为了有效地运作，人们需要预测不确定性，并采取措施在不确定性的存在下保持稳健。我们将研究抽象这些设置的模型中的关键底层算法问题，并开发有效解决这些问题的技术和有效算法。(b)系统中存在不协调的组件，具有“自私”的利益。在一个有着自利用户的环境中，比如有着自治子网的互联网，人们不能再假设用户会按照系统设计者的规定来优化性能。我们将研究，什么时候，以及在多大程度上，自私的行为会影响性能，如何减轻由此产生的低效率，以及如何在这种自私的环境中设计算法，抵制操纵。在许多情况下，遇到的算法问题在计算上是难以处理的（例如，NP-hard）优化问题，因此不太可能在多项式时间内计算出精确解，我们的方法将是为该问题设计一个近似算法，即总是提供可证明的接近最优可行解的多项式时间算法。近似算法构成了这项研究的一个统一的主题，我们的研究也将通过进一步发展这些算法的设计和分析的一般原则，对这个丰富而令人兴奋的领域产生影响。

Technological advances over the past few years have led to the development of systems of rapidly increasing size and complexity. The design, maintenance and management of such systems, especially high-speed telecommunication networks and decentralized networks like the Internet, which are the important computing and communication platforms of the future, present several challenges. In this proposal, we shall focus on two important issues that arise in the design of such systems: (a) Uncertainty in the data or specifications. Uncertainty is a facet of many practical decision environments, and to function effectively one needs to anticipate uncertainty and take measures to be robust in the presence of uncertainty. We will investigate the key underlying algorithmic problems in models that  abstract these settings, and develop techniques and efficient algorithms for effectively tackling these problems. (b) The presence of uncoordinated components in the system with ``selfish'' interests. In an environment with self-interested users, like the Internet with its autonomous sub-networks, one can no longer assume that the users will act as stipulated by the system designer to optimize performance. We shall study, when, and to what extent, does selfish behavior affect performance, ways to mitigate the resulting inefficiencies, and ways to devise algorithms in such selfish environments that resist manipulation. In many cases, the algorithmic problems encountered are computationally intractable (e.g., NP-hard) optimization problems, so it is unlikely that exact solutions can be computed in polynomial time, and our approach will be to devise an approximation algorithm for the problem, that is, a polynomial-time algorithm that always delivers a provably near-optimal feasible solution. Approximation algorithms constitute a unifying theme of this research, and our research will also have impact on this rich and exciting field by furthering the development of general principles for the design and analysis of these algorithms.