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.