ABSTRACT
Game theory was founded by von Neumann and Morgenstern and can be defined as the study of mathematical models of interactive decision making. Game theory provides general mathematical techniques for analyzing situations in which two or more individuals, called players, make decisions that will influence one another’s welfare. The dominant aspect of game theory is the belief that each player is rational, in the sense that he/she makes decisions consistently in pursuit of his/her own objectives, and this rationality is common knowledge. This chapter is an introduction to the basic concepts and the advances of a new field, that of
computational (or algorithmic) game theory. This field is a fertile interaction between the very deep and older field of game theory on the one hand, and of the younger field of algorithms and complexity on the other. In the seminal paper of (Papadimitriou, 2001), the interactionbetweengame theory and theoretical
computer science was considered as a potential “object of the next great modeling adventure” of the field of computer scientists. In that work, it was pointed out that a fusion of algorithmic ideas and game theoretic concepts might yield to the most appropriate mathematical tools and insights for understanding the socio-economic complexity of the Internet. Furthermore, some game theoretic
concepts (e.g., Nash equilibria) are related to fundamental computational issues, such as finding solutions that are guaranteed to exist via nonconstructive methods, or approximating them. On the other hand, game theoretic concepts have been used by theoretical computer scientists as a means of studying the computational complexity of algorithms: proving lower bounds can be seen as a game between the algorithm designer and an adversary. In this chapter we deal with some basic topics of computational game theory. Namely, we study
the computational complexity of Nash equilibria (which constitute the most important solution concept in game theory) and review the related algorithms proposed in the literature. Then, given the apparent difficulty of computing exact Nash equilibria, we study the efficient computation of approximate notions of Nash equilibria. Next we deal with several computational issues related to the class of congestion games, which model the selfish behavior of individuals when competing on the usage of a common set of resources. Finally, we study the price of anarchy (in the context of congestion games), which is defined as a measure of the performance degradation due to the lack of coordination among the involved players. As this new field of computational game theory evolves, important research results have already
appeared in several directions that are not touched here, because of lack of space and because of our selection of what are the most basic topics. For example, mechanism design, cooperative games, Bayesian games and their computational issues are not considered in this chapter. We hope that the interested reader will be motivated by this chapter to also look into those new research lines.
