The 8th Annual Paris C. Kanellakis Memorial Lecture

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

Anna Karlin, University of Washington

Thursday, December 4, 2008 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

The recent surge of activity at the boundary between game theory and theory of computation has brought a true intellectual renaissance to both fields. Clearly, much of this research is motivated by the emergence of the Internet and its growing impact on every walk of life. In the good old days, algorithms research was quite simple, at least in terms of its socio-economic context: a problem was formulated, usually by application demand, an algorithm was designed to solve it correctly and efficiently, accurate inputs were supplied readily by users eager to solve their problem, and the computer finished its business in total isolation.

This is, of course, far from the current reality, especially on the Internet. A fantastic number of users access this mega-computer simultaneously. Many of these users are driven by an economic goal, and they compete for the same resources. The serene view of computer science of days past no longer applies. Data may be supplied by agents that compete against you on the market. Deals have to be made to carry out your goals, and new research methodologies have to be created to handle these new complex situations.

These developments have generated completely new areas of research 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.)

This lecture series honors Paris Kanellakis, a distinguished computer scientist who was an esteemed and beloved member of the Brown Computer Science department. Paris joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20, 1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

A reception will follow.

Host: Maurice Herlihy

To see the poster for this lecture, please click here.