Editing Knaster–Tarski theorem (section)

== Application in game theory ==
Tarski's fixed-point theorem has applications to [[supermodular game]]s.<ref name=":0">{{cite arXiv | eprint=2005.09836 | last1=Dang | first1=Chuangyin | last2=Qi | first2=Qi | last3=Ye | first3=Yinyu | title=Computations and Complexities of Tarski's Fixed Points and Supermodular Games | date=2020 | class=cs.GT }}</ref> A ''supermodular game'' (also called a ''game of strategic complements''<ref>{{Cite journal |last=Vives |first=Xavier |date=1990-01-01 |title=Nash equilibrium with strategic complementarities |url=https://dx.doi.org/10.1016/0304-4068%2890%2990005-T |journal=Journal of Mathematical Economics |volume=19 |issue=3 |pages=305–321 |doi=10.1016/0304-4068(90)90005-T |issn=0304-4068}}</ref>) is a [[Game theory|game]] in which the [[utility function]] of each player has [[increasing differences]], so the [[best response]] of a player is a weakly-increasing function of other players' strategies. For example, consider a game of competition between two firms. Each firm has to decide how much money to spend on research. In general, if one firm spends more on research, the other firm's best response is to spend more on research too. Some common games can be modeled as supermodular games, for example [[Cournot competition]], [[Bertrand competition]] and [[Investment Game]]s.

Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a [[Pure strategy|pure-strategy]] [[Nash equilibrium]] (PNE) in a supermodular game. Moreover, Topkis<ref>{{Cite journal |last=Topkis |first=Donald M. |date=1979-11-01 |title=Equilibrium Points in Nonzero-Sum n -Person Submodular Games |url=http://epubs.siam.org/doi/10.1137/0317054 |journal=SIAM Journal on Control and Optimization |language=en |volume=17 |issue=6 |pages=773–787 |doi=10.1137/0317054 |issn=0363-0129}}</ref> showed that the set of PNE of a supermodular game is a complete lattice, so the game has a "smallest" PNE and a "largest" PNE.

Echenique<ref>{{Cite journal |last=Echenique |first=Federico |date=2007-07-01 |title=Finding all equilibria in games of strategic complements |url=https://www.sciencedirect.com/science/article/pii/S0022053106001086 |journal=Journal of Economic Theory |volume=135 |issue=1 |pages=514–532 |doi=10.1016/j.jet.2006.06.001 |issn=0022-0531}}</ref> presents an algorithm for finding all PNE in a supermodular game. His algorithm first uses best-response sequences to find the smallest and largest PNE; then, he removes some strategies and repeats, until all PNE are found. His algorithm is exponential in the worst case, but runs fast in practice. Deng, Qi and Ye<ref name=":0" /> show that a PNE can be computed efficiently by finding a Tarski fixed-point of an order-preserving mapping associated with the game.