Algebraic methods in game theory

In this dissertation we apply algebraic methods to game theory. The central objects of study in game theory, Nash equilibria, can be characterized in several ways. We focus on their characterization as the solutions to certain systems of polynomial equations and inequalities. Thus we bring to bear the techniques of commutative algebra, algebraic geometry, and combinatorics used in solving polynomial systems. In Chapter 1 we give a brief overview of the game theory we need. We restrict attention to games with a finite number of players each with a finite number of pure strategies. We mostly consider noncooperative normal form games, although we discuss finite-horizon extensive form games briefly and also mention cooperative games.; In Chapter 2 we prove the universality of Nash equilibria. Every real algebraic variety is isomorphic to the set of totally mixed Nash equilibria of some game with 3 players, and also of some game with N players in which each player has two pure strategies. Our proof is constructive. The numbers of pure strategies in the game with 3 players, and the number of players in the game with two pure strategies each, are polynomial in the degrees of the equations. Thus the problem of computing Nash equilibria in general is equivalent to the problem of finding the real roots of a system of polynomial equations.; In Chapter 3 we prove a theorem computing the number of solutions to a system of equations which is generic subject to the sparsity conditions embodied in a graph. We apply this theorem to games obeying graphical models and to extensive-form games. We define emergent-node tree structures as additional structures which normal form games may have. We apply our theorem to games having such structures. We briefly discuss how emergent node tree structures relate to cooperative games.; In Chapter 4 we discuss how to compute all Nash equilibria of a game using computer algebra. We find that polyhedral homotopy continuation is the most efficient available method in practice. It also has the advantage of being naturally parallelizable. We discuss further directions for developing algebraic algorithms for computing Nash equilibria.