ICES: Small: Distributed Computing with Adaptive Heuristics

计算节点或决策者随时间反复交互的动态环境出现在各种设置中，诸如互联网协议、大规模市场、社交网络和多处理器计算机架构。在许多这样的设置中，节点的规定行为是简单、自然和短视的，反映了计算节点（无论是人类还是计算机）提供快速响应并具有有限计算负担的愿望或必要性。从长远来看，这些“适应性策略”通常可以使全球系统朝着良好的方向发展，并产生高度理性和复杂的行为，例如博弈论结果表明最佳反应或无悔动态收敛到平衡点。然而，博弈论中自适应策略的这些积极结果主要是基于一个通常不切实际的前提，即节点的行动以某种方式同步协调。在许多情况下，节点可以在任何时候行动，这种同步是不可用的;很久以前就知道，分布式系统中的同步带来了很大的困难。 该项目从分布式计算理论和博弈论中汲取思想，以研究异步计算环境中自适应算法的可证明属性和可能的最坏情况系统行为。项目研究的一个中心推力是理解分布式计算与自适应算法的收敛行为。 识别动态，证明收敛到均衡，即使在存在的Nash都加强了经典的结果，关于游戏动态，并在广泛的应用领域的影响，包括：收敛的游戏动态纯纳什均衡;稳定的异步电路;并收敛到边界网关协议的稳定路由树，项目结果加强了关于博弈动态的经典结果，并指导了路由、拥塞控制和其他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.