04-14

Computer Science and Game Theory: Mutual Influences and Synergies

The last few years have seen a surge of interest in problems at the intersection between computer science and game theoretic economics. Sometimes, practical use of game theoretic mechanisms or solution concepts requires the application of ideas from computer science; in other cases problems in computer systems can be best addressed by the introduction of game theoretic incentives. Finally, the influence between the disciplines can be more symmetric, requiring a synthesized view of both computational limitations and the self-interested behavior of agents. This talk will describe one example of each of these three cases:

• modeling the empirical computational hardness of selecting the winners of a combinatorial auction, analyzing these models, and applying them to construct algorithm portfolios and to generate hard problem instances
• using incentives to diffuse temporally-focused usage of network resources at the lowest possible cost
• local-effect games, a novel class of multi-player general-sum games for which representation is compact, pure-strategy Nash equilibria often exist, and equilibria can often be computed efficiently