Algorithmic game theory and graph theory

算法博弈论和图论

• 批准号: 356035-2008
• 负责人: Farzad, Babak
• 金额: $ 1.24万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=402827
• 关键词: Algorithmic; game; theory; graph

Fundamental problems in computer science revolve around the discovery of efficient algorithms. In the past 5-6 years, computer scientists have witnessed an explosive growth of interest in algorithmic game theory which deals with models where there are no trusted coordinator and the outcome depends on the cooperation or competition by parties of different interests. One aspect of my research will focus on network routing and its generalizations as a non-cooperative game - a line of research in algorithmic game theory. As an example, this work includes a precise analysis of the extension of the classical selfish routing model to the model in which we incorporate the concept of "time" (when all users of a link do not experience the same latency).

计算机科学的基本问题围绕着高效算法的发现。在过去的5-6年里，计算机科学家们对算法博弈论的兴趣呈爆炸性增长，该理论处理的模型没有可信的协调者，结果取决于不同利益方的合作或竞争。我的研究的一个方面将集中在网络路由和它的推广作为一个非合作博弈-在算法博弈论的研究线。作为一个例子，这项工作包括一个精确的分析扩展的经典自私的路由模型的模型中，我们将“时间”的概念（当所有用户的链接不经历相同的延迟）。