ICES: Small: Distributed Computing with Adaptive Heuristics

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

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.