Research on Games, Networks, and Algorithms

博弈、网络和算法研究

• 批准号: 0635319
• 负责人: Christos Papadimitriou
• 金额: --
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-15 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635319&HistoricalAwards=false
• 关键词: Research; Games; Networks; Algorithms

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.

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