Research on Games, Networks, and Algorithms

本研究的目标是通过解决算法，网络和博弈论领域之间的接口中的一些基本问题，获得对博弈论算法方面的新见解，以及互联网和万维网的性质，效率和真正潜力。 正在处理的问题领域包括：发展在博弈中达到近似均衡的算法;了解作出路由决定的网络经营者更有效地利用互联网所需的激励措施的性质;为互联网和传感网发展改进的路由算法;并为万维网上的信息检索发展了一种经济理论。鉴于研究者及其同事最近的研究结果，计算纳什均衡的复杂性，近似纳什均衡的算法正在追求。互联网（大联盟的网络）形成的过程中，路由决策在其中，从博弈论的角度来看，并着眼于激励措施，而dissuptive 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.