Skip to main content

A Survey of Some Recent Research Topics at the Intersection of Game Theory, Economics, and Theoretical Computer Science

A Survey of Some Recent Research Topics at the Intersection of Game Theory, Economics and Computer Science. (from the biased perspective of a theoretical computer scientist)

The boundary between mathematical economics, game theory and computer science has been teeming with activity over the last several years. Clearly, much of this research is motivated by the growing impact of the Internet on every walk of life. In the good old days, algorithm design was simple - a computational problem was defined and an algorithm was designed so that any instance of the problem was solved correctly and efficiently. The computer operated in totally isolation, the input was accurate and there was no outside influence on the computational procedure. 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 data that is the input to your program may be supplied by agents that compete against you on the market.

These developments have generated new areas of research within theoretical computer science such as computational economics, where the goal is 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, and this is the primary focus of this talk, "mechanism design" comes to the fore. 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 a few of the research questions and recent developments in these areas. Almost no background in game theory, economics or computer science will be assumed.