ICES: Small: Distributed Computing with Adaptive Heuristics

计算节点或决策者随时间重复交互的动态环境出现在各种设置中，例如Internet协议、大规模市场、社会网络和多处理器计算机体系结构。在许多这样的设置中，节点的规定行为是简单、自然和短视的，反映了计算节点（无论是人还是计算机）提供快速响应和有限计算负担的愿望或必要性。从长远来看，这些“适应性启发式”通常可以将全球系统推向良好的方向，并产生高度理性和复杂的行为，例如在博弈论结果中证明了最佳反应或无悔动态趋同于平衡点。然而，博弈论中适应性启发式的这些积极结果主要基于通常不现实的前提，即节点的行动在某种程度上是同步协调的。在许多情况下，节点可以随时行动，这种同步是不可用的；人们早就知道，异步给分布式系统带来了很大的困难。该项目从分布式计算理论和博弈论中汲取思想，研究异步计算环境中自适应启发式的可证明性质和可能的最坏情况系统行为。项目研究的中心推力是用自适应启发式理解分布式计算的收敛行为。即使在异步的情况下，识别可证明收敛于均衡的动态既加强了关于游戏动力学的经典结果，也对广泛的应用领域产生了影响，包括：游戏动态收敛于纯纳什均衡；异步电路的稳定；并收敛到处理互联网路由的边界网关协议的稳定路由树。项目成果加强了游戏动力学方面的经典成果，并指导了路由、拥塞控制和其他互联网环境新协议的设计。该项目的成果包括博弈论和分布式计算现有技术的新应用，以及对两个社区都有用的新技术的开发。对系统收敛行为的透彻理解不仅具有科学意义，而且具有影响现实世界系统和政策决策的重大潜力。随着对复杂系统中有关环境和参与者的假设对可能的全球和地方结果的影响的更好理解，政策制定者、系统设计者和系统参与者可以参与更知情的讨论并做出更好的决策。

Dynamic environments where computational nodes or decision makers interact repeatedly over time arise in a variety of settings, such as Internet protocols, large-scale markets, social networks, and multi-processor computer architectures. In many such settings, the prescribed behavior of the nodes is simple, natural, and myopic, reflecting either the desire or necessity for computational nodes (whether humans or computers) to provide quick responses and have a limited computational burden. These "adaptive heuristics" can often, in the long run, move the global system in good directions and yield highly rational and sophisticated behavior, such as in game-theoretic results demonstrating the convergence of best-response or no-regret dynamics to equilibrium points. However, these positive results for adaptive heuristics in game theory are primarily based on the often unrealistic premise that nodes' actions are somehow synchronously coordinated. In many settings, where nodes can act at any time, this kind of synchrony is not available; it has long been known that asynchrony introduces substantial difficulties in distributed systems. The project draws ideas from distributed-computing theory and from game theory to investigate provable properties and possible worst-case system behavior of adaptive heuristics in asynchronous computational environments. A central thrust of project research is understanding the convergence behavior of distributed computing with adaptive heuristics. Identifying dynamics that provably converge to equilibria even in the presence of asynchrony both strengthens classic results regarding game dynamics and has implications across a wide domain of applications, including: convergence of game dynamics to pure Nash equilibria; stabilization of asynchronous circuits; and convergence to a stable routing tree of the Border Gateway Protocol, which handles Internet routing.Project results strengthen classic results regarding game dynamics and guide the design of new protocols for routing, congestion control, and other Internet environments. The outcomes of this project include new applications of existing techniques from game theory and distributed computing and the development of new techniques that are of use to both communities. A thorough understanding of convergence behaviors of systems is both of scientific interest and has significant potential to affect real-world systems and policy decisions. With an improved understanding of the impact that assumptions about the environment and participants of a complex system have on possible global and local outcomes, policy makers, system designers, and system participants can engage in more informed discussion and make better decisions.