.We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based upon certain extensions and specializations of an existing optimization approach pre- viously used for the derivation of xed approximations for this problem. In particular, the general two-person problem is reduced to an inde- nite quadratic programming problem of special structure involving the n x n adjacency matrix of an induced simple graph specied by the in- put data of the game, where n is the number of players' strategies.