Algorithmic game theory and approximate network design

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

• 批准号: 288340-2007
• 负责人: Konemann, Jochen
• 金额: $ 1.82万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=364984
• 关键词: 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.I have contributed to this area in joint work with S. Leonardi and G. Schaefer. We studied a game-theoretic variant of the Steiner forest problem, where each player j, out of a set of k players, strives to connect the vertices of her terminal pair (s_j, t_j) in a given undirected, edge-weighted graph G.  We show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein and Ravi [Siam J. of Computing, 1995] and Goemans and Williamson [Siam J. of Computing, 1995] yields a 2-budget balanced and group-strategyproof mechanism for this game.  We also showed that the mechanism-design ideas used in our work give rise to a new linear programming relaxation for the Steiner forest problem which is strictly stronger than the well-known undirected cut relaxation for this problem. As short-term goals, I plan to address the following questions: can we use the new Steiner forest LP relaxation to obtain better Steiner forest approximation algorithms? Can the mechanism design techniques used for the Steiner forest problem be applied to a larger class of network design problems? Can we obtain tighter LP relaxations for these problems?

在过去的十年里，人们对经典博弈论重新产生了兴趣，这是一个研究竞争环境中理性自利主体行为的领域。目前的焦点是游戏的算法方面：我们能在某些游戏中有效地找到纳什均衡吗？如果允许参与者独立和自由地行动，社会福利的损失（无政府状态的代价）是什么？是否有激励机制迫使玩家以诚实和公平的方式行事？ 对于这些问题中的许多问题，来自组合优化和理论计算机科学的思想提供了关键的新见解。相反，Gupta等人。[STOC '03，FOCS '03]表明博弈论的成本分担思想可以卓有成效地应用于网络设计问题的近似算法的设计和分析。我研究的长期目标是进一步探索博弈论，理论计算机科学和组合优化。我在与S。Leonardi和G.谢弗我们研究了斯坦纳森林问题的一个博弈论变体，其中k个参与者中的每个参与者j都努力连接她的终端对的顶点（s_j，t_j）在一个给定的无向，边加权图G。我们表明，一个自然的适应原始对偶施泰纳森林算法的Agrawal，克莱因和拉维[Siam J计算，1995]和Goemans和威廉姆森[Siam J. of Computing，1995]给出了该博弈的一个2-budget平衡和防组策略的机制，并证明了该机制设计思想对Steiner森林问题产生了一个新的线性规划松弛，它严格强于井-已知无向切削松弛。作为短期目标，我计划解决以下问题：我们可以使用新的Steiner森林LP松弛，以获得更好的Steiner森林近似算法？用于斯坦纳森林问题的机制设计技术可以应用于更大类的网络设计问题吗？我们可以得到更严格的LP松弛这些问题？