College Affiliation
College of Science and Engineering
Document Type
Research Paper
Publication Date
2008
Department or Program Affiliation
Computer Science Department
Keywords
Nash equilibrium, game theory, two-player games, zero-sum games
Abstract
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 method of Koller, Megiddo, and von Stengel to find proper equilibria. Both algorithms run in polynomial time in the worst case. The hardness of the equilibrium-finding problem for general-sum games highlights the need for new approximation methods.
Subject – LCSH
Game theory, Noncooperative games (Mathematics), Equilibrium (Economics)
Publisher
Western Washington University
Recommended Citation
Wimpee, Jeffrey, "Finding Nash equilibria in two-player, zero sum games" (2008). Computer Science Graduate and Undergraduate Student Scholarship. 3.
https://cedar.wwu.edu/computerscience_stupubs/3
Genre/Form
term papers
Type
Text
Rights
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.
Language
English
Format
application/pdf