Algorithmic game theory and approximate network design

算法博弈论和近似网络设计

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

The last decade has seen renewed interest in classical game theory -- a field that studies the behavior of rational self-interested agents in competitive environments. The current focus is on algorithmic aspects of games: Can we find Nash equilibria efficiently in certain games? What is the loss in social welfare (the price of anarchy) if players are allowed to act independently and greedily? Are there incentive mechanisms that force players to behave in a truthful and fair manner? For many of these questions, ideas from combinatorial optimization and theoretical computer science provide key new insights. Conversely, Gupta et al. [STOC '03, FOCS '03] showed that game-theoretic cost-sharing ideas can be fruitfully applied to the design and analysis of approximation algorithms for network design problems. The long-term goal of my research is to further explore the relationship between game theory, theoretical computer science and combinatorial optimization.

在过去的十年里，人们对经典博弈论重新产生了兴趣，这是一个研究竞争环境中理性自利主体行为的领域。目前的焦点是游戏的算法方面：我们能在某些游戏中有效地找到纳什均衡吗？如果允许参与者独立和自由地行动，社会福利的损失（无政府状态的代价）是什么？是否有激励机制迫使玩家以诚实和公平的方式行事？ 对于其中的许多问题，来自组合优化和理论计算机科学的思想提供了关键的新见解。 相反，Gupta等人[STOC '03，FOCS '03]表明，博弈论的成本分担思想可以有效地应用于网络设计问题的近似算法的设计和分析。 我研究的长期目标是进一步探索博弈论、理论计算机科学和组合优化之间的关系。