CAREER: Towards a Constructive Theory of Networked Interactions

随着计算机科学努力理解互联网及其功能，计算机科学家正在将经济学和博弈论的概念和方法纳入他们的学科。在过去的十年里，围绕着以下问题的研究有了巨大的增长：什么样的博弈论工具适用于计算机系统？由于用户和管理员的利益冲突，系统的性能离最佳状态有多远？此外，我们如何设计一个系统，使其在系统内部的潜在利益冲突方面表现稳健？这项研究旨在解决计算机科学和博弈论之间的一些基本问题，重点是网络互动。博弈论家传统上用来模拟互动个体系统中行为的工具，如纳什均衡和市场均衡，最近已被证明是计算上难以解决的。这些概念的复杂性限制了它们在政策制定中的适用性，因为它们的预测虽然在数学上有明确的定义，但很难计算。此外，这个难以解决的结果引起了人们对这些预测是否在现实中出现的怀疑：如果不能有效地找到某个均衡概念所预测的行为，那么理性的个人是如何找到并采用它的呢？该项目的目标是开发一种不会遇到计算复杂性障碍的网络交互理论，回答这样的问题：在什么情况下可以使用现有的工具（如纳什均衡）来有效地预测自私行为？交互作用图的结构如何影响均衡的易处理性？当计算纳什均衡是棘手的，是否有可能有效地作出近似预测？如果这是不可行的，是否有其他均衡的概念是合理的和易于处理的？此外，在交易的背景下：什么样的市场均衡会出现在一个交易网络？它总是与假设完全信息的市场均衡相同吗？如果是这样的话，在网络结构所施加的通信约束存在的情况下，它是如何产生的？如果不是，有什么不同？对于什么样的网络，它与全信息网络相似？网络交互的成功理论的发展将需要回答计算理论中的深层次问题。平衡概念通常对应于连续映射的不动点，这已经被证明是本技术的一个具有挑战性的计算对象。近年来，计算平衡的算法进步为理论计算机科学界带来了新技术。类似地，描述博弈论概念的复杂性已经扩大了计算复杂性的范围，超出了传统的复杂性类别。几个问题，如近似复杂性的纳什均衡，简单的随机游戏的复杂性，以及其他不动点的复杂性类称为PLS和PPAD的交叉点，和复杂性的市场均衡的恒定替代弹性（CES）效用函数，回避现有的技术。为了进一步理解大型系统中的理性行为，我们必须开发新的算法和复杂性理论工具来应对这些问题带来的挑战。

As Computer Science struggles to understand the Internet and its capabilities, computer scientists are incorporating concepts and methodologies from Economics and Game Theory into their discipline. In the past decade, there has been a tremendous growth in research, centering around the following questions: what game-theoretic tools are applicable to computer systems? How far is the performance of a system from optimality due to the conflict of interests of its users and administrators? And, how can we design a system whose performance is robust with respect to the potential conflict of interests inside the system? The proposed research aims to tackle some of the fundamental problems at the interface of Computer Science and Game Theory, with a focus on networked interactions.The tools that game theorists have traditionally used to model behavior in systems of interacting individuals, such as the Nash and the market equilibria, have been recently shown to be computationally intractable. The intractability of these concepts limits their applicability to policy making since their predictions, although mathematically well-defined, are hard to compute. Moreover, this intractability result raises suspicion as to whether these predictions arise in actuality: if the behavior predicted by some equilibrium concept cannot be found efficiently, how is it that rational individuals find it and adopt it?The goal of this project is to develop a theory of networked interactions that does not run into the computational complexity barrier, answering such questions as: In what settings is it possible to use existing tools, such as the Nash equilibrium, to predict selfish behavior computationally efficiently? How does the structure of the interaction graph affect the tractability of equilibria? When computing Nash equilibria is intractable, is it possible to make approximate predictions efficiently? And if this is infeasible, are there other concepts of equilibrium that are both plausible and tractable? Also, in the context of trading: What kind of market equilibrium comes about in a trading network? Is it always identical to the market equilibrium assuming full information? If so, how does it come to arise in the presence of the communication constraints imposed by the network structure? If not, how different is it? And for what kinds of networks is it similar to the full-information one?The development of a successful theory of networked interactions will necessitate answering deep questions within the theory of computation. Equilibrium concepts typically correspond to fixed points of continuous maps, which have proven to be a challenging computational object for present techniques. In recent years, algorithmic progress on computing equilibria has brought new techniques to the theoretical computer science community. Likewise, characterizing the complexity of game-theoretic concepts has broadened the computational complexity landscape beyond traditional complexity classes. Several questions, such as the approximation complexity of Nash equilibria, the complexity of simple stochastic games as well as other fixed points at the intersection of the complexity classes known as PLS and PPAD, and the complexity of market equilibria for constant elasticity of substitution (CES) utility functions, are evading existing techniques. Furthering our understanding of rational behavior in large systems will necessarily involve developing novel algorithmic and complexity-theoretic tools to meet the challenges posed by these problems.