Algorithm design in game-theoretic environments and settings with uncertainty

点击翻译按钮获取中文摘要

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.