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.
