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.**