ICES: Small: A Probabilistic Look at Algorithmic Game Theory

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

Recent years have seen a remarkable growth of communication networks and computational platforms overlaid on these networks; primary examples are the Internet and the systems created and enabled by it. At the same time, it has been recognized that to properly understand and engineer such systems one needs to incorporate insights and methods from both Computer Science and Economics into their study, as these systems tend to be large, highly distributed, and owned, operated and used by thousands, or even millions, of self-interested parties. The proposed research will contribute to the growing interactions between Computer Science and Economics a new research direction motivated by a systematic study of the role of uncertainty in the structure and tractability of economic systems. Crucial in this study will be the use of concepts and tools from Statistical Physics and Probability Theory, ultimately strengthening the interaction of these fields with Algorithmic Game Theory.Uncertainty is most certainly both present and taken into account in the study of systems of interacting individuals. A player of a game may be uncertain about her opponents'payoffs or even her own payoff, may be unable to fully observe the strategies used by the other players and the potential opportunities created by these strategies, or may even be uncertain about the exact number of opponents, the structure of the game, the order of players' moves, etc. Likewise a social planner, or mechanism designer, may have uncertainty about the values or budgets of the agents in the mechanism, the number of participants, the information that the participants have about the other participants, etc. This uncertainty is sometimes modeled by assigning probabilistic beliefs to the parameters of the system that are not fixed, and other times eliminated by obtaining worst-case guarantees.Both harnessing uncertainty in the Bayesian way and tackling it via worst-case/prior-free results have been central in the development of Game Theory. Nevertheless, we believe that there still remain large benefits to be obtained by a systematic treatment of uncertainty, through the import of tools from Probability Theory, Statistical Physics and Algorithms into Game Theory. We will employ these tools (1) to understand the equilibrium structure and complexity of large games of aggregative form (games with a lot of symmetries or anonymity), (2) to make progress in optimal multi-dimensional mechanism design, (3) to study dynamics in network games, (4) to understand the correlation of behaviors across large networks of interacting individuals, (5) to characterize the complexity and structural properties of equilibria in random ensembles of games, and (6) to study the Price of Anarchy in selfish routing games where the players' utilities are non-linear probabilistic functions of the delay.