A discrete Nash Theorem with low complexity and dynamic equilibria

Nash's Theorem guarantees the existence of Nash equilibria for strategic-form games. The typical proof of the result uses Brouwer's Fixed Point Theorem on probabilistic strategies. We show that Tarski's Fixed Point Theorem can be used to establish a similar result for discrete equilibria in a much larger class of games that we call conversion/preference games. Our result rests on a graph characterisation of Nash equilibria that i) reifies the decision procedure for pure Nash equilibria, ii) allows us to compute the equilibria in quadratic time in the number of game situations, and iii) makes the equilibria explicitly dynamic in nature. We also briefly discuss the extended range of technical applications of non-cooperative game theory that results from the new theorem, including for gene regulation and cell-level signal transduction.リサーチレポート（北陸先端科学技術大学院大学情報科学研究科