Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Finding Nash Equilibria In Two-Player, Zero Sum Games, Jeffrey Wimpee
Finding Nash Equilibria In Two-Player, Zero Sum Games, Jeffrey Wimpee
Computer Science Graduate and Undergraduate Student Scholarship
In many games, it is desirable to find strategies for all players that simultaneously maximize their respective worst-case payoffs. A set of strategies satisfying this criterion is called a Nash equilibrium. Because the search space of possible strategies grows rapidly as the size of the game increases, specialized algorithms are needed to efficiently find Nash equilibria. In this paper, current equilibrium-finding methods are presented and key areas for future work are identified. The first algorithm, due to Koller, Megiddo, and von Stengel, computes standard Nash equilibria in two-player, zero-sum games. The second algorithm, due to Miltersen and Sorensen, extends the …