Algorithmic game theory and approximate network design

点击翻译按钮获取中文摘要

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.