Algorithm design in game-theoretic environments and settings with uncertainty

随着信息和通信系统变得越来越复杂，越来越需要开发有效的算法工具，用于设计、维护和管理此类系统，特别是诸如互联网和高速电信网络等分散式网络。该研究计划将调查在这种情况下出现的算法问题，重点关注两个主要问题： (a)需要在存在自利代理的情况下发挥作用的协议的设计（例如，互联网上的自治子网）。在这种情况下，算法设计的任务是复杂的，因为与问题相关的数据往往是由自私的代理人控制的。因此，我们需要通过巧妙地激励用户来获取这些数据，以便自利行为导致理想的结果。我们将着重于开发设计和分析这种有效的“抗操纵”机制的技术。一个特别的重点将是确定的方法“出口”的算法到抗操纵的机制，从而有助于算法的机制设计领域。 (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 subnetworks 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, and thus contribute to the field of algorithmic mechanism design. (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. One of the broad objectives 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 algorithmic problems that capture the underlying difficulties in such settings, and develop techniques that will find use in a variety of settings. 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.