A Survey of Some Recent Research at the Border of Game Theory and Theoretical Computer Science

CS Distinguished Lecture
Speaker: Prof. Anna Karlin, University of Washington
Host: Prof. David KempeAbstract:
The design of protocols for resource allocation and electronic commerce among parties with diverse and selfish interests has spawned a great deal of recent research at the boundary between economics, game theory and computer science.In the process, completely new areas of research have emerged such as computational economics. We need to understand the complexity of computing various equilibria. New notions such as the "price of anarchy" arise in an attempt to quantify the efficiency lost due to selfish behavior in natural games. Finally, there is "mechanism design", a fascinating subfield of game theory and microeconomics, focusing on "incentive engineering". A mechanism is an algorithm or protocol that is explicitly designed so that rational participants, motivated solely by their self-interest, will end up achieving the designer's goals.In this talk, we survey some of the research and open problems in these areas. (No background in game theory will be assumed.)Biography:
Anna Karlin is a Professor of Computer Science and Engineering at the University of Washington. She received her Ph.D. from Stanford University and then spent 5 years as a researcher at (what was then) Digital Equipment Corporation's Systems Research Center before coming to the University of Washington. Her professional activities have included serving on the National Research Council's Computer Science and Telecommunications Board, the editorial board for SIAM Journal on Computing, the committee to award the ACM Paris Kanellakis Theory and Practice Award (including chairing that committee in 2006), and serving as Program Chair for the 1997 IEEE Symposium on Foundations of Computer Science. She has given a number of Distinguished Lectures at major universities including among others MIT, Brown, Penn and Duke.Her research is primarily in theoretical computer science: the design and analysis of algorithms, particularly probabilistic and online algorithms. Much of her work is also at the interface between theory and other areas, such as economics and game theory, data mining, operating systems, networks, and distributed systems.Outside of work, her main claim to fame is having formerly been part of "an obscure and very bad rock band of furry Palo Alto geeks" (according to the Rolling Stones) called Severe Tire Damage (or STD for short). STD was the first band to broadcast live over the Internet (back in 1993).

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia