Knaster–Tarski theorem

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

Let (L, ≤) be a complete lattice and let f : L → L be an order-preserving (monotonic) function w.r.t. ≤ . Then the set of fixed points of f in L forms a complete lattice under ≤ .

It was Tarski who stated the result in its most general form,[1] and so the theorem is often known as Tarski's fixed-point theorem. Some time earlier, Knaster and Tarski established the result for the special case where L is the lattice of subsets of a set, the power set lattice.[2]

The theorem has important applications in formal semantics of programming languages and abstract interpretation, as well as in game theory.

A kind of converse of this theorem was proved by Anne C. Davis: If every order-preserving function f : LL on a lattice L has a fixed point, then L is a complete lattice.[3]

Consequences: least and greatest fixed points

edit

Since complete lattices cannot be empty (they must contain a supremum and infimum of the empty set), the theorem in particular guarantees the existence of at least one fixed point of f, and even the existence of a least fixed point (or greatest fixed point). In many practical cases, this is the most important implication of the theorem.

The least fixpoint of f is the least element x such that f(x) = x, or, equivalently, such that f(x) ≤ x; the dual holds for the greatest fixpoint, the greatest element x such that f(x) = x.

If f(lim xn) = lim f(xn) for all ascending sequences xn, then the least fixpoint of f is lim fn(0) where 0 is the least element of L, thus giving a more "constructive" version of the theorem. (See: Kleene fixed-point theorem.) More generally, if f is monotonic, then the least fixpoint of f is the stationary limit of f α(0), taking α over the ordinals, where f α is defined by transfinite induction: f α+1 = f (f α) and f γ for a limit ordinal γ is the least upper bound of the f β for all β ordinals less than γ.[4] The dual theorem holds for the greatest fixpoint.

For example, in theoretical computer science, least fixed points of monotonic functions are used to define program semantics, see Least fixed point § Denotational semantics for an example. Often a more specialized version of the theorem is used, where L is assumed to be the lattice of all subsets of a certain set ordered by subset inclusion. This reflects the fact that in many applications only such lattices are considered. One then usually is looking for the smallest set that has the property of being a fixed point of the function f. Abstract interpretation makes ample use of the Knaster–Tarski theorem and the formulas giving the least and greatest fixpoints.

The Knaster–Tarski theorem can be used to give a simple proof of the Cantor–Bernstein–Schroeder theorem.[5][6]

Weaker versions of the theorem

edit

Weaker versions of the Knaster–Tarski theorem can be formulated for ordered sets, but involve more complicated assumptions. For example:[citation needed]

Let L be a partially ordered set with a least element (bottom) and let f : LL be an monotonic function. Further, suppose there exists u in L such that f(u) ≤ u and that any chain in the subset   has a supremum. Then f admits a least fixed point.

This can be applied to obtain various theorems on invariant sets, e.g. the Ok's theorem:

For the monotone map F : P(X ) → P(X ) on the family of (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P(X ) s.t.  , (i) F admits invariant set A in P(X ) i.e.  , (ii) F admits maximal invariant set A, (iii) F admits the greatest invariant set A.

In particular, using the Knaster-Tarski principle one can develop the theory of global attractors for noncontractive discontinuous (multivalued) iterated function systems. For weakly contractive iterated function systems the Kantorovich theorem (known also as Tarski-Kantorovich fixpoint principle) suffices.

Other applications of fixed-point principles for ordered sets come from the theory of differential, integral and operator equations.

Proof

edit

Let us restate the theorem.

For a complete lattice   and a monotone function   on L, the set of all fixpoints of f is also a complete lattice  , with:

  •   as the greatest fixpoint of f
  •   as the least fixpoint of f.

Proof. We begin by showing that P has both a least element and a greatest element. Let D = {x | xf(x)} and xD (we know that at least 0L belongs to D). Then because f is monotone we have f(x) ≤ f(f(x)), that is f(x) ∈ D.

Now let   (u exists because DL and L is a complete lattice). Then for all xD it is true that xu and f(x) ≤ f(u), so xf(x) ≤ f(u). Therefore, f(u) is an upper bound of D, but u is the least upper bound, so uf(u), i.e. uD. Then f(u) ∈ D (because f(u) ≤ f(f(u))) and so f(u) ≤ u from which follows f(u) = u. Because every fixpoint is in D we have that u is the greatest fixpoint of f.

The function f is monotone on the dual (complete) lattice  . As we have just proved, its greatest fixpoint exists. It is the least fixpoint of L, so P has least and greatest elements, that is more generally, every monotone function on a complete lattice has a least fixpoint and a greatest fixpoint.

For a, b in L we write [a, b] for the closed interval with bounds a and b: {xL | axb}. If ab, then ⟨[a, b], ≤⟩ is a complete lattice.

It remains to be proven that P is a complete lattice. Let  , WP and  . We show that f([w, 1L]) ⊆ [w, 1L]. Indeed, for every xW we have x = f(x) and since w is the least upper bound of W, xf(w). In particular wf(w). Then from y ∈ [w, 1L] follows that wf(w) ≤ f(y), giving f(y) ∈ [w, 1L] or simply f([w, 1L]) ⊆ [w, 1L]. This allows us to look at f as a function on the complete lattice [w, 1L]. Then it has a least fixpoint there, giving us the least upper bound of W. We've shown that an arbitrary subset of P has a supremum, that is, P is a complete lattice.

Computing a Tarski fixed-point

edit

Chang, Lyuu and Ti[7] present an algorithm for finding a Tarski fixed-point in a totally-ordered lattice, when the order-preserving function is given by a value oracle. Their algorithm requires   queries, where L is the number of elements in the lattice. In contrast, for a general lattice (given as an oracle), they prove a lower bound of   queries.

Deng, Qi and Ye[8] present several algorithms for finding a Tarski fixed-point. They consider two kinds of lattices: componentwise ordering and lexicographic ordering. They consider two kinds of input for the function f: value oracle, or a polynomial function. Their algorithms have the following runtime complexity (where d is the number of dimensions, and Ni is the number of elements in dimension i):

Input
Lattice
Polynomial function Value oracle
Componentwise    
Lexicographic    

The algorithms are based on binary search. On the other hand, determining whether a given fixed point is unique is computationally hard:

Input
Lattice
Polynomial function Value oracle
Componentwise coNP-complete  
Lexicographic coNP-complete  

For d=2, for componentwise lattice and a value-oracle, the complexity of   is optimal.[9] But for d>2, there are faster algorithms:

  • Fearnley, Palvolgyi and Savani[10] presented an algorithm using only   queries. In particular, for d=3, only   queries are needed.
  • Chen and Li[11] presented an algorithm using only   queries.

Application in game theory

edit

Tarski's fixed-point theorem has applications to supermodular games.[8] A supermodular game (also called a game of strategic complements[12]) is a 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 Games.

Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a pure-strategy Nash equilibrium (PNE) in a supermodular game. Moreover, Topkis[13] 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[14] 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[8] show that a PNE can be computed efficiently by finding a Tarski fixed-point of an order-preserving mapping associated with the game.

See also

edit

Notes

edit
  1. ^ Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics. 5 (2): 285–309. doi:10.2140/pjm.1955.5.285.
  2. ^ B. Knaster (1928). "Un théorème sur les fonctions d'ensembles". Ann. Soc. Polon. Math. 6: 133–134. With A. Tarski.
  3. ^ Anne C. Davis (1955). "A characterization of complete lattices". Pacific Journal of Mathematics. 5 (2): 311–319. doi:10.2140/pjm.1955.5.311.
  4. ^ Cousot, Patrick; Cousot, Radhia (1979). "Constructive versions of tarski's fixed point theorems". Pacific Journal of Mathematics. 82: 43–57. doi:10.2140/pjm.1979.82.43.
  5. ^ Uhl, Roland. "Tarski's Fixed Point Theorem". MathWorld. Example 3.
  6. ^ Davey, Brian A.; Priestley, Hilary A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. pp. 63, 4. ISBN 9780521784511.
  7. ^ Chang, Ching-Lueh; Lyuu, Yuh-Dauh; Ti, Yen-Wu (2008-07-23). "The complexity of Tarski's fixed point theorem". Theoretical Computer Science. 401 (1): 228–235. doi:10.1016/j.tcs.2008.05.005. ISSN 0304-3975.
  8. ^ a b c Dang, Chuangyin; Qi, Qi; Ye, Yinyu (2020-05-01). Computations and Complexities of Tarski's Fixed Points and Supermodular Games (Report). arXiv.org.
  9. ^ Etessami, Kousha; Papadimitriou, Christos; Rubinstein, Aviad; Yannakakis, Mihalis (2020). Vidick, Thomas (ed.). "Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria". 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs). 151. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 18:1–18:19. doi:10.4230/LIPIcs.ITCS.2020.18. ISBN 978-3-95977-134-4. S2CID 202538977.
  10. ^ Fearnley, John; Pálvölgyi, Dömötör; Savani, Rahul (2022-10-11). "A Faster Algorithm for Finding Tarski Fixed Points". ACM Transactions on Algorithms. 18 (3): 23:1–23:23. arXiv:2010.02618. doi:10.1145/3524044. ISSN 1549-6325. S2CID 222141645.
  11. ^ Chen, Xi; Li, Yuhao (2022-07-13). "Improved Upper Bounds for Finding Tarski Fixed Points". Proceedings of the 23rd ACM Conference on Economics and Computation. EC '22. New York, NY, USA: Association for Computing Machinery. pp. 1108–1118. arXiv:2202.05913. doi:10.1145/3490486.3538297. ISBN 978-1-4503-9150-4. S2CID 246823965.
  12. ^ Vives, Xavier (1990-01-01). "Nash equilibrium with strategic complementarities". Journal of Mathematical Economics. 19 (3): 305–321. doi:10.1016/0304-4068(90)90005-T. ISSN 0304-4068.
  13. ^ Topkis, Donald M. (1979-11-01). "Equilibrium Points in Nonzero-Sum n -Person Submodular Games". SIAM Journal on Control and Optimization. 17 (6): 773–787. doi:10.1137/0317054. ISSN 0363-0129.
  14. ^ Echenique, Federico (2007-07-01). "Finding all equilibria in games of strategic complements". Journal of Economic Theory. 135 (1): 514–532. doi:10.1016/j.jet.2006.06.001. ISSN 0022-0531.

References

edit

Further reading

edit
edit