Algorithmic game theory and approximate network design

在过去的十年里，人们对经典博弈论重新产生了兴趣--这是一个研究竞争环境中理性自利代理人行为的领域。目前的焦点是博弈的算法方面：我们能否在某些博弈中有效地找到纳什均衡？如果允许玩家独立和贪婪地行动，社会福利的损失(无政府状态的代价)是什么？有没有激励机制迫使玩家以真实和公平的方式行事？对于其中的许多问题，来自组合优化和理论计算机科学的想法提供了关键的新见解。相反，Gupta等人。[STOC‘03，FOCS’03]表明博弈论的成本分担思想可以卓有成效地应用于网络设计问题的近似算法的设计和分析。我研究的长期目标是进一步探索博弈论、理论计算机科学和组合优化之间的关系。我与S.Leonardi和G.Schaefer共同致力于这一领域的研究。我们研究了Steiner森林问题的一个博弈论变体，其中k个参与者中的每个参与者j都努力在给定的无向边权重图G中连接她的终端对(S_j，t_j)的顶点。我们证明了Agrawal，Klein和Ravi的原始-对偶Steiner森林算法[Siam J.of Computing，1995]以及Goemans和Williamson[Siam J.of Computing，我们还证明了我们工作中使用的机制设计思想给出了Steiner森林问题的一个新的线性规划松弛，它严格地强于这个问题的众所周知的无向割松弛。作为短期目标，我计划解决以下问题：我们能否使用新的斯泰纳森林LP松弛来获得更好的斯泰纳森林近似算法？用于斯坦纳森林问题的机制设计技术是否可以应用于更大类别的网络设计问题？对于这些问题，我们能否获得更严格的LP放松？

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?