Research on Games, Networks, and Algorithms

本研究的目标是通过解决算法、网络和博弈论领域之间的一些基本问题，获得对博弈论算法方面的新见解，以及对互联网和万维网的性质、效率和真正潜力的新见解。所追求的问题领域包括开发在游戏中达到近似平衡的算法；了解网络运营商在制定路由决策时更有效地利用互联网所需的激励措施的性质；为互联网和传感器网络开发改进的路由算法；并为万维网中的信息检索发展经济理论。鉴于研究者及其同事最近关于计算纳什均衡复杂性的结果，人们正在研究近似纳什均衡的算法。互联网（大型网络联盟）形成的过程，以及在其中做出路由决策的过程，从博弈论的角度进行了检查，并着眼于激励，而互联网中的破坏性BGP振荡现象也作为纳什均衡计算进行了研究。万维网的博弈论模型正在被开发出来，在这个模型中，诸如“搜索引擎的最佳排名算法是什么？”的问题可以被分析地提出和回答。最后，研究了一个图论问题，该问题与将网络分解成组件的方式有关，从而实现一种新型的高效和无地址路由。

The goal of this research is to gain new insights into the algorithmic aspects of Game Theory, as well as into the nature, efficiency, and true potential of the Internet and the worldwide web, by addressing some fundamental problems in the interface between the fields of Algorithms, Networking, and Game Theory. The problem areas being pursued include developing algorithms for arriving at approximate equilibria in games; understanding the nature of the incentives needed for more efficient use of the Internet by network operators making routing decisions; developing improved routing algorithms for both the Internet and sensornets; and developing an economic theory for information retrieval in the worldwide web.In view of the recent results by the investigator and colleagues concerning the complexity of computing Nash equilibria, algorithms for approximate Nash equilibria are being pursued. The processes whereby internetworks (large federations of networks) are formed, and routing decisions are made in them, are examined from the point of view of Game Theory and with an eye towards incentives, while the disuptive BGP oscillation phenomenon in the Internet is also studied as a Nash equilibrium computation. A game-theoretic model of the worldwide web is being developed, in which fundamental questions such as ``what is the optimum ranking algorithm by a search engine?'' can be posed and answered analytically. Finally, a graph-theoretic problem is studied related to the decomposition of a network into components in a way that enables a novel form of efficient and address-free routing.