Diseño de un algoritmo eficiente para encontrar equilibrios puros de Nash en juegos de estrategia (Design of an efficient algorithm to find pure Nash equilibria on strategic games)

Omar Pérez Barrios (omar.perez@solarium.cs.buap.mx)1, Guillermo De Ita Luna (deita@cs.buap.mx)1, Luis Manuel Polanco Balcazar (luis.polanco@cs.buap.mx)1

1Benemerita Universidad Autonoma de Puebla

This paper appears in: Revista IEEE América Latina

Publication Date: Jan. 2016
Volume: 14,   Issue: 1 
ISSN: 1548-0992

Pure Nash Equilibria are states in strategic games in which no player has motivation to change of strategy, and then the game is stabilized in such optimal states. A general objective in all strategic game is to determine if it has pure Nash equilibria, and when they exist, find such optimal points in an efficient way. We present here, an efficient algorithm (a time polynomial procedure based on the size of their inputs) to find Nash pure equilibria for any strategic game, independent to the number of players and the number of strategies for each player. As inputs for this algorithm, we request the values of the utility function for each player and for each one of the possible states of the game. Our Algorithm is an iterative process for searching the optimal states for each player (the player's Pareto) without caring about the strategies the other players are using. The algorithm goes comparing a Pareto set of a player with the next one, in order to keep just the common pareto states. If at the end of the process of searching for the Pareto set of the players, there exists Pareto states common to all involved players, then these states represent the pure Nash equilibria of the game.

Index Terms:
Nash Pure Equilibrium, Strategic Games, Pareto Points, Computational Game Theory.   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (343)]