We all try to design systems with optimal or near-optimal performance. In the age of the Internet, however, we must take into account that many users of our systems are driven by an economic goal, and interact with varying degrees of collaboration and competition. Moreover, the strategic nature of interactions in online dynamic marketplaces means that a tweak you make to your system today, expecting improved performance, can end up degrading performance tomorrow, due to unanticipated responses by strategic users.

Thankfully, the fascinating field of game theory provides precisely the theoretical foundation we need to think about optimization in the presence of strategic users. In this talk, we give a brief introduction to the algorithmic game theory, which addresses topics at the intersection of game theory and computer science. For example, we give an overview of how game theory is applied in ad auctions and search engines.

Anna Karlin is the Microsoft Professor of Computer Science and Engineering at the University of Washington. She received her Ph.D. from Stanford University in 1987. and then spent 5 years as a researcher at (what was then) Digital Equipment Corporation’s Systems Research Center before joining the University of Washington. Her research is primarily in theoretical computer science: the design and analysis of algorithms, particularly probabilistic and online algorithms. She also works at the interface between theory and other areas, such as economics and game theory, data mining, operating systems, networks, and distributed systems.