Quick links

Computer Science and Game Theory: Mutual Influences and Synergies

Date and Time
Monday, April 14, 2003 - 4:00pm to 5:30pm
Computer Science Small Auditorium (Room 105)
Kevin Leyton-Brown, from Stanford University
Kenneth Steiglitz
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
Follow us: Facebook Twitter Linkedin