AN ALGORITHM FOR DETERMINING A CLASS OF TWO-PERSON GAMES HAVING A PURE-STRATEGY NASH EQUILIBRIUM

摘要

Sato and Kawasaki (Preprint) introduced a class of n-person games called partially monotone games, and showed that any partially monotone game has a pure-strategy Nash equilibrium. Further, they proved that partial monotonicity is necessary for the existence of a pure-strategy Nash equilibrium in the case of two persons. In this paper, we present an algorithm for determining whether a two-person game belongs to the class. Our algorithm requires O(m~2n~2) time, where m and n are the number of pure strategies of players 1 and 2, respectively.