Algorithm Design in Strategic and Uncertain Environments

随着信息和通信系统变得越来越复杂，越来越需要开发有效的算法工具来设计、维护和管理这类系统，特别是像因特网和高速电信网络这样的分散网络。这项研究计划将调查在这种情况下出现的算法问题，集中在两个主要问题上。*(A)需要在存在自利代理(例如，互联网上的自治系统)的情况下运行的协议的设计。在这种情况下，算法设计的任务由于与问题相关的数据通常由自利的代理人控制的事实而变得复杂。因此，人们需要通过巧妙地激励用户来获得这些数据，这样自利的行为才能产生理想的结果。我们将专注于开发设计和分析这种有效的“防操纵”机制的技术。一个特别的重点将是确定将算法“输出”到防操纵机制的方法。我们将通过检查根深蒂固的抗操纵概念，如真实性，以及通过考虑设计其纳什均衡具有所需性质的机制的算法纳什实现问题来处理这一任务。我们的研究将借鉴计算机科学和经济学的思想，并为蓬勃发展的算法机制设计领域做出贡献，该领域的重要性已得到谷歌、雅虎、微软等领先IT公司的认可。*(B)不确定情况下的决策。不确定性是许多决策环境的一个方面，为了有效地进行决策，需要考虑明确包含不确定性的模型。我们研究的一个广泛目标是探索抽象此类设置的模型，并设计方法来解决此类模型中出现的算法问题。我们将研究在这种情况下捕捉潜在困难的关键问题，重点是丰富的随机车辆路径问题，并设计出将在各种情况下使用的技术。我们还将研究模棱两可的随机问题，其中模拟不确定性的分布本身是不精确的。我们开发的技术应该对通信网络的设计有用，因为通信网络经常必须处理不确定的流量。*在许多情况下，遇到的算法问题在计算上是棘手的，我们的方法将是为该问题设计一个近似算法，即总是提供可证明的近最优可行解的多项式时间算法。近似算法是我们研究的一个共同主线，我们的研究也将进一步发展这些算法的设计和分析技术。

As information and communication systems become increasingly complex, there is a growing need for the development of efficient algorithmic tools for the design, maintenance and management of such systems, especially decentralized networks like the Internet and high-speed telecommunication networks. This research program will investigate the algorithmic questions that arise in such settings, focusing on two main problems. ******(a) The design of protocols that need to function in the presence of self-interested agents (e.g., autonomous systems on the Internet). In such settings, the task of algorithm-design is complicated by the fact that the data relevant to the problem is often controlled by self-interested agents. Consequently, one needs to elicit this data by cleverly incentivizing the users so that self-interested behavior leads to desirable outcomes. We shall focus on the development of techniques for the design and analysis of such efficient "manipulation-resistant'' mechanisms. A particular emphasis will be to identify ways for "exporting'' algorithms into manipulation-resistant mechanisms. We shall approach this task both by examining well-entrenched notions of manipulation-resistance such as truthfulness, and by considering the algorithmic Nash implementation problem of designing mechanisms whose Nash equilibria possess desirable properties. Our research will draw upon ideas from Computer Science and Economics and contribute to the thriving field of algorithmic mechanism design, an area whose importance has been recognized by leading IT companies such as Google, Yahoo, Microsoft. ******(b) Decision-making under uncertainty. Uncertainty is a facet of many decision environments, and for effective decision making, one needs to consider models that explicitly incorporate the uncertainty. A broad objective of our research is to explore models that abstract such settings, and devise methods for solving the algorithmic problems that arise in such models. We shall study key problems that capture the underlying difficulties in such settings, focusing on the rich class of stochastic vehicle routing problems, and devise techniques that will find use in a variety of settings. We shall also investigate ambiguous stochastic problems, wherein the distribution modeling the uncertainty is itself imprecise. The techniques we develop should be useful in the design of communication networks, which often have to handle uncertain traffic. ******In many cases, the algorithmic problems encountered are computationally intractable, 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 are a common thread in our research, and our research will also further the development of techniques for the design and analysis of these algorithms.**