How Many Totally Mixed Nash Equilibria Can Graphical Games Have?Algebra & Discrete Mathematics
|Ruchira Datta, UC Davis
|Fri, Feb 27 2004, 12:10PM
Game theory formalizes strategic interaction, and in graphical games the payoff to each player depends only on the actions of "neighboring" players in the graph. Nash equilibria are the main objects of study in game theory, and totally mixed Nash equilibria are the solutions to certain squarefree polynomial systems. The Bernstein-Kouchnirenko Theorem tells us how to find the Bernstein number: the number of complex roots of a generic sparse polynomial system. We define a certain sparsity condition on squarefree polynomial systems, described by an associated graph, the polynomial graph. We show that the Bernstein number is the permanent of a matrix derived from the adjacency matrix of this graph, and we apply this theorem to graphical games.