Algorithm Design in Strategic and Uncertain Environments

随着信息和通信系统变得越来越复杂，越来越需要开发有效的算法工具来设计、维护和管理这些系统，特别是像互联网和高速电信网络这样的分散网络。本研究计划将调查在这种情况下出现的算法问题，重点关注两个主要问题。(a)需要在自利代理存在的情况下发挥作用的协议的设计（例如，互联网上的自治系统）。在这种情况下，算法设计的任务变得复杂，因为与问题相关的数据通常由自利的代理控制。因此，我们需要通过巧妙地激励用户来获取这些数据，从而使自利行为产生理想的结果。我们将把重点放在设计和分析这种有效的“抗操纵”机制的技术发展上。特别强调的是确定将算法“导出”到抗操纵机制的方法。我们将通过检查诸如真实性等根深蒂固的抗操纵概念，以及考虑设计纳什均衡具有理想属性的机制的算法纳什实现问题来完成这项任务。我们的研究将借鉴计算机科学和经济学的思想，并为算法机制设计这一蓬勃发展的领域做出贡献，这一领域的重要性已被b谷歌、雅虎、微软等领先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.