A Discrete Nash Theorem with
        Quadratic Complexity and Dynamic Equilibria

     Stephane Le Roux, Pierre Lescanne, Rene Vestergaard*


Nash's Theorem guarantees the existence of compromising Nash
equilibria for finite strategic games. The typical proof of the
result uses Brouwer's Fixed Point Theorem on probabilistic
strategies. We show that Tarski's Fixed Point Theorem points to
a similar result, except with discrete equilibria and for a
larger class of games that we call conversion/preference games:
C/P games, for short. Our result rests on a unifying graph
characterisation of our and Nash�fs equilibria that,
additionally, i) reifies the obvious decision procedure for
pure Nash equilibria, ii) allows us to compute our compromising
equilibria in quadratic time in the number of game situations,
and iii) makes our compromising equilibria explicitly dynamic
in nature. We conclude by discussing key examples and the
extended range of applications of Nash-style game theory that
our result enables.

*: corresponding