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.

这项研究的目的是通过解决算法，网络和游戏理论之间的界面中的一些基本问题，从而获得对游戏理论算法以及互联网和全球网络的性质，效率和真正潜力的新见解。 所追求的问题领域包括开发算法以达到游戏中的近似平衡；了解通过做出路由决策的网络运营商更有效利用互联网所需的激励措施的性质；为互联网和SensOnets开发了改进的路由算法；并在全球范围内开发了一种以信息检索的经济理论。在研究者和同事关于计算纳什均衡的复杂性的最新结果中，正在追求近似nash均衡的算法。从游戏理论的角度来检查互联网工程（网络的大型联合会）并在其中制定路由决策的过程，并注视激励措施，而互联网中的爆发性BGP振荡现象也被研究为NASH平衡计算。 正在开发一种游戏理论模型，其中诸如``搜索引擎的最佳排名算法是什么''之类的基本问题可以通过分析提出和回答。 最后，研究了与网络分解为组件的分解方式，以一种新型的有效和无地址路由的方式相关。