2421:
Echenique 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
2395:
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
1798:
1888:
921:
1953:
851:
2452:
389:. 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
2356:
512:
2239:
2081:
1297:
783:
711:
2509:
743:
2418:(PNE) in a supermodular game. Moreover, Topkis 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.
1410:
597:
2285:
2172:
1449:
1052:
2121:
1664:
1989:
1631:
640:
3141:
S. Heikkilä (1990). "On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities".
2422:
practice. Deng, Qi and Ye show that a PNE can be computed efficiently by finding a Tarski fixed-point of an order-preserving mapping associated with the game.
3235:
667:
1718:
1307:
has least and greatest elements, that is more generally, every monotone function on a complete lattice has a least fixpoint and a greatest fixpoint.
647:
In particular, using the
Knaster-Tarski principle one can develop the theory of global attractors for noncontractive discontinuous (multivalued)
1669:
Deng, Qi and Ye present several algorithms for finding a Tarski fixed-point. They consider two kinds of lattices: componentwise ordering and
1804:
412:
Weaker versions of the
Knaster–Tarski theorem can be formulated for ordered sets, but involve more complicated assumptions. For example:
861:
101:
1899:
791:
1637:
is the number of elements in the lattice. In contrast, for a general lattice (given as an oracle), they prove a lower bound of
3012:
2993:
2831:
2719:
3225:
2603:
2411:
Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a
2293:
452:
2617:
2185:
401:
2985:
3207:: Given a book with 100 pages and 100 lemmas, prove that there is some lemma written on the same page as its index
2031:
1260:
2692:
Etessami, Kousha; Papadimitriou, Christos; Rubinstein, Aviad; Yannakakis, Mihalis (2020). Vidick, Thomas (ed.).
1570:
as a function on the complete lattice . Then it has a least fixpoint there, giving us the least upper bound of
1323:
3083:
E.A. Ok (2004). "Fixed set theory for closed correspondences with applications to self-similarity and games".
3230:
756:
684:
716:
377:
397:
makes ample use of the
Knaster–Tarski theorem and the formulas giving the least and greatest fixpoints.
2609:
434:
368:
309:
61:
2934:
2634:
3164:
1379:
567:
170:
of the empty set), the theorem in particular guarantees the existence of at least one fixed point of
128:
69:
3097:
2248:
2135:
648:
77:
It was Tarski who stated the result in its most general form, and so the theorem is often known as
1425:
1028:
394:
105:
2097:
1640:
3092:
2486:
2388:
1959:
1670:
1601:
228:
2678:
2576:
3220:
659:
418:
333:
610:
2401:
182:
3162:
R. Uhl (2003). "Smallest and greatest fixed points of quasimonotone increasing mappings".
1681:, or a polynomial function. Their algorithms have the following runtime complexity (where
81:. Some time earlier, Knaster and Tarski established the result for the special case where
36:
8:
2397:
652:
2431:
3177:
2837:
2809:
2782:
2756:
2725:
120:
3196:
3132:
3115:
2856:
2808:. EC '22. New York, NY, USA: Association for Computing Machinery. pp. 1108–1118.
2693:
658:
Other applications of fixed-point principles for ordered sets come from the theory of
3181:
3154:
3008:
2989:
2954:
2915:
2876:
2872:
2841:
2827:
2786:
2774:
2729:
2715:
2654:
2613:
2368:
663:
642:, (ii) F admits maximal invariant set A, (iii) F admits the greatest invariant set A.
515:
372:
353:
232:
175:
65:
1299:. As we have just proved, its greatest fixpoint exists. It is the least fixpoint of
556:
of (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P
3169:
3150:
3127:
3102:
3069:
3042:
2946:
2907:
2868:
2819:
2766:
2705:
2704:. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 18:1–18:19.
2646:
2599:
2554:
2521:
2464:
2415:
2384:
386:
364:
188:). In many practical cases, this is the most important implication of the theorem.
116:
57:
2396:
research too. Some common games can be modeled as supermodular games, for example
360:
for all β ordinals less than γ. The dual theorem holds for the greatest fixpoint.
2801:
2405:
1793:{\displaystyle O(\operatorname {poly} (\log L)\cdot \log N_{1}\cdots \log N_{d})}
86:
2710:
446:
3058:"The Tarski-Kantorovitch principle and the theory of iterated function systems"
3047:
3030:
2977:
381:
for an example. Often a more specialized version of the theorem is used, where
325:
192:
28:
3074:
3057:
2950:
2650:
1590:
Chang, Lyuu and Ti present an algorithm for finding a Tarski fixed-point in a
3214:
3106:
2958:
2919:
2880:
2778:
2679:
Computations and
Complexities of Tarski's Fixed Points and Supermodular Games
2658:
2505:
2412:
2392:
2090:
2024:
1997:
524:
422:
301:
124:
40:
2895:
2823:
3204:
3173:
2559:
2542:
2526:
2469:
1678:
1595:
24:
2691:
2573:
2380:
1591:
109:
20:
2694:"Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria"
385:
is assumed to be the lattice of all subsets of a certain set ordered by
2698:
11th
Innovations in Theoretical Computer Science Conference (ITCS 2020)
2581:
400:
The
Knaster–Tarski theorem can be used to give a simple proof of the
159:
94:
2911:
2770:
2132:=2, for componentwise lattice and a value-oracle, the complexity of
2814:
2806:
Proceedings of the 23rd ACM Conference on
Economics and Computation
2761:
1883:{\displaystyle O(\log N_{1}\cdots \log N_{d})\approx O(\log ^{d}L)}
553:
281:
163:
2744:
308:, thus giving a more "constructive" version of the theorem. (See:
3055:
2975:
2182:
Fearnley, Palvolgyi and Savani presented an algorithm using only
167:
3035:
Publications of the
Research Institute for Mathematical Sciences
2743:
Fearnley, John; Pálvölgyi, Dömötör; Savani, Rahul (2022-10-11).
2484:
B. Knaster (1928). "Un théorème sur les fonctions d'ensembles".
2000:. On the other hand, determining whether a given fixed point is
655:(known also as Tarski-Kantorovich fixpoint principle) suffices.
153:
916:{\displaystyle \bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}}
90:
2896:"Equilibrium Points in Nonzero-Sum n -Person Submodular Games"
2700:. Leibniz International Proceedings in Informatics (LIPIcs).
2453:"A lattice-theoretical fixpoint theorem and its applications"
2633:
Chang, Ching-Lueh; Lyuu, Yuh-Dauh; Ti, Yen-Wu (2008-07-23).
1948:{\displaystyle O(\operatorname {poly} (\log L)\cdot \log L)}
846:{\displaystyle \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}}
2935:"Finding all equilibria in games of strategic complements"
1594:
lattice, when the order-preserving function is given by a
2543:"Constructive versions of tarski's fixed point theorems"
2802:"Improved Upper Bounds for Finding Tarski Fixed Points"
2742:
651:. For weakly contractive iterated function systems the
3205:
An application to an elementary combinatorics problem
2296:
2251:
2188:
2138:
2100:
2034:
1962:
1902:
1807:
1721:
1643:
1604:
1428:
1382:
1263:
1031:
938:
has both a least element and a greatest element. Let
864:
794:
759:
719:
687:
613:
570:
455:
2745:"A Faster Algorithm for Finding Tarski Fixed Points"
1673:. They consider two kinds of input for the function
2857:"Nash equilibrium with strategic complementarities"
2350:
2279:
2233:
2166:
2115:
2075:
1983:
1947:
1882:
1792:
1658:
1625:
1443:
1404:
1291:
1046:
915:
845:
777:
737:
705:
634:
591:
523:This can be applied to obtain various theorems on
506:
437:. Further, suppose there exists u in L such that f
72:of f in L forms a complete lattice under ≤ .
2677:Dang, Chuangyin; Qi, Qi; Ye, Yinyu (2020-05-01).
2367:Tarski's fixed-point theorem has applications to
2351:{\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}
1585:
507:{\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}
407:
3212:
2635:"The complexity of Tarski's fixed point theorem"
3113:
378:Least fixed point § Denotational semantics
3056:J. Jachymski; L. Gajek; K. Pokarowski (2000).
2597:
2290:Chen and Li presented an algorithm using only
2234:{\displaystyle O(\log ^{2\lceil d/3\rceil }L)}
2504:
2450:
2362:
154:Consequences: least and greatest fixed points
3031:"Self-similar sets as Tarski's fixed points"
2540:
2334:
2308:
2217:
2203:
2076:{\displaystyle \Theta (N_{1}+\cdots +N_{d})}
1292:{\displaystyle \langle L^{op},\geq \rangle }
1286:
1264:
910:
877:
840:
807:
772:
760:
700:
688:
501:
456:
3140:
2632:
1257:is monotone on the dual (complete) lattice
3236:Theorems in the foundations of mathematics
3028:
2483:
1574:. We've shown that an arbitrary subset of
100:The theorem has important applications in
3131:
3116:"Algorithms for the fixed point property"
3096:
3073:
3046:
2932:
2813:
2760:
2709:
2558:
2525:
2510:"A characterization of complete lattices"
2468:
316:is monotonic, then the least fixpoint of
102:formal semantics of programming languages
2900:SIAM Journal on Control and Optimization
2676:
2541:Cousot, Patrick; Cousot, Radhia (1979).
3082:
3002:
1692:is the number of elements in dimension
778:{\displaystyle \langle P,\leq \rangle }
706:{\displaystyle \langle L,\leq \rangle }
3213:
3161:
2893:
2799:
738:{\displaystyle f\colon L\rightarrow L}
2854:
2574:
1072:is a complete lattice). Then for all
62:order-preserving (monotonic) function
2672:
2670:
2668:
2178:>2, there are faster algorithms:
599:, (i) F admits invariant set A in P
16:Theorem in order and lattice theory
13:
3022:
2933:Echenique, Federico (2007-07-01).
2800:Chen, Xi; Li, Yuhao (2022-07-13).
2605:Introduction to Lattices and Order
2101:
2035:
1644:
402:Cantor–Bernstein–Schroeder theorem
158:Since complete lattices cannot be
14:
3247:
3189:
2861:Journal of Mathematical Economics
2665:
1685:is the number of dimensions, and
2894:Topkis, Donald M. (1979-11-01).
514:has a supremum. Then f admits a
2926:
2887:
2848:
2793:
2736:
1405:{\displaystyle 1_{L}=\bigvee L}
1238:. Because every fixpoint is in
592:{\displaystyle A\subseteq F(A)}
3007:. Cambridge University Press.
2749:ACM Transactions on Algorithms
2685:
2626:
2591:
2577:"Tarski's Fixed Point Theorem"
2567:
2547:Pacific Journal of Mathematics
2534:
2514:Pacific Journal of Mathematics
2498:
2477:
2457:Pacific Journal of Mathematics
2444:
2345:
2323:
2311:
2300:
2274:
2255:
2228:
2192:
2161:
2142:
2110:
2104:
2070:
2038:
1978:
1966:
1942:
1927:
1915:
1906:
1877:
1858:
1849:
1811:
1787:
1746:
1734:
1725:
1653:
1647:
1620:
1608:
1586:Computing a Tarski fixed-point
907:
901:
837:
831:
749:, the set of all fixpoints of
729:
629:
623:
586:
580:
486:
480:
408:Weaker versions of the theorem
215:, or, equivalently, such that
174:, and even the existence of a
1:
3133:10.1016/S0304-3975(98)00273-4
2969:
2377:game of strategic complements
2280:{\displaystyle O(\log ^{2}L)}
2167:{\displaystyle O(\log ^{2}L)}
1372:It remains to be proven that
1150:is the least upper bound, so
352:for a limit ordinal γ is the
292:, then the least fixpoint of
60:and let f : L → L be an
3155:10.1016/0362-546X(90)90082-R
2873:10.1016/0304-4068(90)90005-T
2855:Vives, Xavier (1990-01-01).
2639:Theoretical Computer Science
2241:queries. In particular, for
1996:The algorithms are based on
1566:. This allows us to look at
1484:is the least upper bound of
1246:is the greatest fixpoint of
853:as the greatest fixpoint of
678:Let us restate the theorem.
363:For example, in theoretical
79:Tarski's fixed-point theorem
7:
2711:10.4230/LIPIcs.ITCS.2020.18
2425:
1598:. Their algorithm requires
1444:{\displaystyle w=\bigvee W}
1376:is a complete lattice. Let
1047:{\displaystyle u=\bigvee D}
753:is also a complete lattice
320:is the stationary limit of
10:
3252:
3226:Fixed points (mathematics)
3003:Forster, T. (2003-07-21).
2939:Journal of Economic Theory
2610:Cambridge University Press
2363:Application in game theory
2116:{\displaystyle \Theta (L)}
1659:{\displaystyle \Omega (L)}
310:Kleene fixed-point theorem
64:w.r.t. ≤ . Then the
3165:Mathematische Nachrichten
3075:10.1017/S0004972700022243
3005:Logic, Induction and Sets
2951:10.1016/j.jet.2006.06.001
2651:10.1016/j.tcs.2008.05.005
2004:is computationally hard:
1984:{\displaystyle O(\log L)}
1626:{\displaystyle O(\log L)}
1578:has a supremum, that is,
934:We begin by showing that
923:as the least fixpoint of
649:iterated function systems
527:, e.g. the Ok's theorem:
129:order-preserving function
3114:B.S.W. Schröder (1999).
3107:10.1016/j.na.2003.08.001
3062:Bull. Austral. Math. Soc
3048:10.2977/prims/1195178796
2437:
971:(we know that at least 0
713:and a monotone function
673:
367:, least fixed points of
146:has a fixed point, then
43:, states the following:
3198:Notes on lattice theory
2824:10.1145/3490486.3538297
1582:is a complete lattice.
1369:is a complete lattice.
1142:) is an upper bound of
681:For a complete lattice
395:Abstract interpretation
324:(0), taking α over the
235:, the greatest element
150:is a complete lattice.
106:abstract interpretation
3174:10.1002/mana.200310016
2560:10.2140/pjm.1979.82.43
2527:10.2140/pjm.1955.5.311
2487:Ann. Soc. Polon. Math.
2470:10.2140/pjm.1955.5.285
2451:Alfred Tarski (1955).
2389:increasing differences
2352:
2281:
2235:
2168:
2117:
2077:
1985:
1949:
1884:
1794:
1671:lexicographic ordering
1660:
1627:
1445:
1406:
1293:
1048:
917:
847:
779:
739:
707:
636:
635:{\displaystyle A=F(A)}
593:
532:For the monotone map F
508:
312:.) More generally, if
33:Knaster–Tarski theorem
2353:
2282:
2236:
2169:
2118:
2078:
2010:Lattice v input >
1986:
1950:
1885:
1795:
1702:Lattice v input >
1661:
1628:
1446:
1407:
1294:
1049:
918:
848:
780:
740:
708:
637:
594:
509:
419:partially ordered set
334:transfinite induction
199:is the least element
162:(they must contain a
3231:Fixed-point theorems
3168:. 248–249: 204–210.
3120:Theoret. Comput. Sci
2681:(Report). arXiv.org.
2600:Priestley, Hilary A.
2402:Bertrand competition
2294:
2249:
2186:
2174:is optimal. But for
2136:
2098:
2032:
2013:Polynomial function
1960:
1900:
1805:
1719:
1705:Polynomial function
1641:
1602:
1458:. Indeed, for every
1426:
1380:
1261:
1029:
985:is monotone we have
862:
792:
757:
717:
685:
611:
568:
453:
280:) for all ascending
119:of this theorem was
3029:S. Hayashi (1985).
2976:Andrzej Granas and
2398:Cournot competition
2387:of each player has
2287:queries are needed.
1367:⟨, ≤⟩
1226:from which follows
653:Kantorovich theorem
371:are used to define
369:monotonic functions
300:(0) where 0 is the
2982:Fixed Point Theory
2612:. pp. 63, 4.
2369:supermodular games
2348:
2277:
2231:
2164:
2113:
2073:
1981:
1945:
1880:
1790:
1656:
1623:
1441:
1402:
1322:we write for the
1289:
1044:
913:
843:
775:
735:
703:
632:
589:
504:
435:monotonic function
425:(bottom) and let f
3014:978-0-521-53361-4
2995:978-0-387-00173-9
2833:978-1-4503-9150-4
2755:(3): 23:1–23:23.
2721:978-3-95977-134-4
2598:Davey, Brian A.;
2373:supermodular game
2126:
2125:
1994:
1993:
516:least fixed point
373:program semantics
354:least upper bound
233:greatest fixpoint
37:Bronisław Knaster
3243:
3185:
3158:
3137:
3135:
3110:
3100:
3079:
3077:
3052:
3050:
3041:(5): 1059–1066.
3018:
2999:
2963:
2962:
2930:
2924:
2923:
2891:
2885:
2884:
2852:
2846:
2845:
2817:
2797:
2791:
2790:
2764:
2740:
2734:
2733:
2713:
2689:
2683:
2682:
2674:
2663:
2662:
2630:
2624:
2623:
2608:(2nd ed.).
2595:
2589:
2587:
2586:
2571:
2565:
2564:
2562:
2538:
2532:
2531:
2529:
2502:
2496:
2494:
2481:
2475:
2474:
2472:
2448:
2432:Modal μ-calculus
2416:Nash equilibrium
2406:Investment Games
2385:utility function
2357:
2355:
2354:
2349:
2338:
2337:
2330:
2286:
2284:
2283:
2278:
2267:
2266:
2240:
2238:
2237:
2232:
2221:
2220:
2213:
2173:
2171:
2170:
2165:
2154:
2153:
2122:
2120:
2119:
2114:
2082:
2080:
2079:
2074:
2069:
2068:
2050:
2049:
2007:
2006:
1990:
1988:
1987:
1982:
1954:
1952:
1951:
1946:
1889:
1887:
1886:
1881:
1870:
1869:
1848:
1847:
1829:
1828:
1799:
1797:
1796:
1791:
1786:
1785:
1767:
1766:
1699:
1698:
1665:
1663:
1662:
1657:
1632:
1630:
1629:
1624:
1565:
1558:
1547:
1524:
1517:
1503:. In particular
1502:
1467:
1457:
1450:
1448:
1447:
1442:
1421:
1411:
1409:
1408:
1403:
1392:
1391:
1368:
1356:
1298:
1296:
1295:
1290:
1279:
1278:
1225:
1211:
1188:
1174:
1164:
1133:
1110:
1091:
1082:it is true that
1081:
1067:
1053:
1051:
1050:
1045:
1021:
1007:
981:). Then because
970:
960:
922:
920:
919:
914:
852:
850:
849:
844:
784:
782:
781:
776:
744:
742:
741:
736:
712:
710:
709:
704:
641:
639:
638:
633:
598:
596:
595:
590:
513:
511:
510:
505:
387:subset inclusion
365:computer science
108:, as well as in
58:complete lattice
3251:
3250:
3246:
3245:
3244:
3242:
3241:
3240:
3211:
3210:
3192:
3098:10.1.1.561.4581
3025:
3023:Further reading
3015:
2996:
2986:Springer-Verlag
2972:
2967:
2966:
2931:
2927:
2912:10.1137/0317054
2892:
2888:
2853:
2849:
2834:
2798:
2794:
2771:10.1145/3524044
2741:
2737:
2722:
2690:
2686:
2675:
2666:
2631:
2627:
2620:
2596:
2592:
2572:
2568:
2539:
2535:
2503:
2499:
2495:With A. Tarski.
2482:
2478:
2449:
2445:
2440:
2428:
2375:(also called a
2365:
2326:
2307:
2303:
2295:
2292:
2291:
2262:
2258:
2250:
2247:
2246:
2209:
2199:
2195:
2187:
2184:
2183:
2149:
2145:
2137:
2134:
2133:
2099:
2096:
2095:
2064:
2060:
2045:
2041:
2033:
2030:
2029:
1961:
1958:
1957:
1901:
1898:
1897:
1865:
1861:
1843:
1839:
1824:
1820:
1806:
1803:
1802:
1781:
1777:
1762:
1758:
1720:
1717:
1716:
1690:
1642:
1639:
1638:
1633:queries, where
1603:
1600:
1599:
1592:totally-ordered
1588:
1560:
1549:
1526:
1519:
1504:
1489:
1459:
1452:
1451:. We show that
1427:
1424:
1423:
1413:
1387:
1383:
1381:
1378:
1377:
1366:
1331:
1324:closed interval
1271:
1267:
1262:
1259:
1258:
1213:
1190:
1176:
1166:
1151:
1112:
1093:
1083:
1073:
1059:
1058:exists because
1030:
1027:
1026:
1009:
986:
976:
962:
939:
863:
860:
859:
793:
790:
789:
758:
755:
754:
718:
715:
714:
686:
683:
682:
676:
612:
609:
608:
569:
566:
565:
454:
451:
450:
445:u and that any
410:
291:
279:
266:
156:
17:
12:
11:
5:
3249:
3239:
3238:
3233:
3228:
3223:
3209:
3208:
3202:
3195:J. B. Nation,
3191:
3190:External links
3188:
3187:
3186:
3159:
3149:(5): 413–426.
3143:Nonlinear Anal
3138:
3126:(2): 301–358.
3111:
3091:(3): 309–330.
3085:Nonlinear Anal
3080:
3068:(2): 247–261.
3053:
3024:
3021:
3020:
3019:
3013:
3000:
2994:
2978:James Dugundji
2971:
2968:
2965:
2964:
2945:(1): 514–532.
2925:
2906:(6): 773–787.
2886:
2867:(3): 305–321.
2847:
2832:
2792:
2735:
2720:
2684:
2664:
2645:(1): 228–235.
2625:
2618:
2590:
2566:
2533:
2520:(2): 311–319.
2497:
2476:
2463:(2): 285–309.
2442:
2441:
2439:
2436:
2435:
2434:
2427:
2424:
2364:
2361:
2360:
2359:
2347:
2344:
2341:
2336:
2333:
2329:
2325:
2322:
2319:
2316:
2313:
2310:
2306:
2302:
2299:
2288:
2276:
2273:
2270:
2265:
2261:
2257:
2254:
2230:
2227:
2224:
2219:
2216:
2212:
2208:
2205:
2202:
2198:
2194:
2191:
2163:
2160:
2157:
2152:
2148:
2144:
2141:
2124:
2123:
2112:
2109:
2106:
2103:
2093:
2088:
2087:Lexicographic
2084:
2083:
2072:
2067:
2063:
2059:
2056:
2053:
2048:
2044:
2040:
2037:
2027:
2022:
2021:Componentwise
2018:
2017:
2014:
2011:
1992:
1991:
1980:
1977:
1974:
1971:
1968:
1965:
1955:
1944:
1941:
1938:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1895:
1894:Lexicographic
1891:
1890:
1879:
1876:
1873:
1868:
1864:
1860:
1857:
1854:
1851:
1846:
1842:
1838:
1835:
1832:
1827:
1823:
1819:
1816:
1813:
1810:
1800:
1789:
1784:
1780:
1776:
1773:
1770:
1765:
1761:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1714:
1713:Componentwise
1710:
1709:
1706:
1703:
1688:
1655:
1652:
1649:
1646:
1622:
1619:
1616:
1613:
1610:
1607:
1587:
1584:
1440:
1437:
1434:
1431:
1401:
1398:
1395:
1390:
1386:
1288:
1285:
1282:
1277:
1274:
1270:
1266:
1043:
1040:
1037:
1034:
972:
929:
928:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
857:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
774:
771:
768:
765:
762:
734:
731:
728:
725:
722:
702:
699:
696:
693:
690:
675:
672:
645:
644:
631:
628:
625:
622:
619:
616:
588:
585:
582:
579:
576:
573:
525:invariant sets
521:
520:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
449:in the subset
409:
406:
332:is defined by
287:
275:
262:
231:holds for the
193:least fixpoint
155:
152:
93:of a set, the
75:
74:
35:, named after
29:lattice theory
15:
9:
6:
4:
3:
2:
3248:
3237:
3234:
3232:
3229:
3227:
3224:
3222:
3219:
3218:
3216:
3206:
3203:
3200:
3199:
3194:
3193:
3183:
3179:
3175:
3171:
3167:
3166:
3160:
3156:
3152:
3148:
3144:
3139:
3134:
3129:
3125:
3121:
3117:
3112:
3108:
3104:
3099:
3094:
3090:
3086:
3081:
3076:
3071:
3067:
3063:
3059:
3054:
3049:
3044:
3040:
3036:
3032:
3027:
3026:
3016:
3010:
3006:
3001:
2997:
2991:
2987:
2983:
2979:
2974:
2973:
2960:
2956:
2952:
2948:
2944:
2940:
2936:
2929:
2921:
2917:
2913:
2909:
2905:
2901:
2897:
2890:
2882:
2878:
2874:
2870:
2866:
2862:
2858:
2851:
2843:
2839:
2835:
2829:
2825:
2821:
2816:
2811:
2807:
2803:
2796:
2788:
2784:
2780:
2776:
2772:
2768:
2763:
2758:
2754:
2750:
2746:
2739:
2731:
2727:
2723:
2717:
2712:
2707:
2703:
2699:
2695:
2688:
2680:
2673:
2671:
2669:
2660:
2656:
2652:
2648:
2644:
2640:
2636:
2629:
2621:
2619:9780521784511
2615:
2611:
2607:
2606:
2601:
2594:
2584:
2583:
2578:
2575:Uhl, Roland.
2570:
2561:
2556:
2552:
2548:
2544:
2537:
2528:
2523:
2519:
2515:
2511:
2507:
2506:Anne C. Davis
2501:
2492:
2489:
2488:
2480:
2471:
2466:
2462:
2458:
2454:
2447:
2443:
2433:
2430:
2429:
2423:
2419:
2417:
2414:
2413:pure-strategy
2409:
2407:
2403:
2399:
2394:
2393:best response
2390:
2386:
2383:in which the
2382:
2378:
2374:
2370:
2342:
2339:
2331:
2327:
2320:
2317:
2314:
2304:
2297:
2289:
2271:
2268:
2263:
2259:
2252:
2244:
2225:
2222:
2214:
2210:
2206:
2200:
2196:
2189:
2181:
2180:
2179:
2177:
2158:
2155:
2150:
2146:
2139:
2131:
2107:
2094:
2092:
2091:coNP-complete
2089:
2086:
2085:
2065:
2061:
2057:
2054:
2051:
2046:
2042:
2028:
2026:
2025:coNP-complete
2023:
2020:
2019:
2016:Value oracle
2015:
2012:
2009:
2008:
2005:
2003:
1999:
1998:binary search
1975:
1972:
1969:
1963:
1956:
1939:
1936:
1933:
1930:
1924:
1921:
1918:
1912:
1909:
1903:
1896:
1893:
1892:
1874:
1871:
1866:
1862:
1855:
1852:
1844:
1840:
1836:
1833:
1830:
1825:
1821:
1817:
1814:
1808:
1801:
1782:
1778:
1774:
1771:
1768:
1763:
1759:
1755:
1752:
1749:
1743:
1740:
1737:
1731:
1728:
1722:
1715:
1712:
1711:
1708:Value oracle
1707:
1704:
1701:
1700:
1697:
1695:
1691:
1684:
1680:
1676:
1672:
1667:
1650:
1636:
1617:
1614:
1611:
1605:
1597:
1593:
1583:
1581:
1577:
1573:
1569:
1563:
1556:
1552:
1545:
1541:
1537:
1533:
1529:
1525:follows that
1522:
1515:
1511:
1507:
1500:
1496:
1492:
1487:
1483:
1479:
1475:
1471:
1466:
1462:
1455:
1438:
1435:
1432:
1429:
1420:
1416:
1399:
1396:
1393:
1388:
1384:
1375:
1370:
1364:
1360:
1354:
1350:
1346:
1342:
1338:
1334:
1329:
1325:
1321:
1317:
1313:
1308:
1306:
1302:
1283:
1280:
1275:
1272:
1268:
1256:
1253:The function
1251:
1249:
1245:
1242:we have that
1241:
1237:
1233:
1229:
1224:
1220:
1216:
1209:
1205:
1201:
1197:
1193:
1187:
1183:
1179:
1173:
1169:
1162:
1158:
1154:
1149:
1145:
1141:
1137:
1134:. Therefore,
1131:
1127:
1123:
1119:
1115:
1108:
1104:
1100:
1096:
1090:
1086:
1080:
1076:
1071:
1066:
1062:
1057:
1041:
1038:
1035:
1032:
1023:
1020:
1016:
1012:
1005:
1001:
997:
993:
989:
984:
980:
975:
969:
965:
958:
954:
950:
946:
942:
937:
933:
926:
904:
898:
895:
892:
889:
886:
883:
880:
874:
871:
868:
865:
858:
856:
834:
828:
825:
822:
819:
816:
813:
810:
804:
801:
798:
795:
788:
787:
786:
769:
766:
763:
752:
748:
732:
726:
723:
720:
697:
694:
691:
679:
671:
669:
665:
661:
656:
654:
650:
643:
626:
620:
617:
614:
604:
600:
583:
577:
574:
571:
561:
557:
555:
549:
545:
541:
537:
533:
530:
529:
528:
526:
519:
517:
498:
495:
492:
489:
483:
477:
474:
471:
468:
465:
462:
459:
448:
442:
438:
436:
430:
426:
424:
423:least element
420:
415:
414:
413:
405:
403:
398:
396:
392:
388:
384:
380:
379:
374:
370:
366:
361:
359:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
311:
307:
303:
302:least element
299:
295:
290:
286:
283:
278:
274:
270:
265:
261:
257:
252:
250:
246:
242:
238:
234:
230:
226:
222:
218:
214:
210:
206:
202:
198:
194:
189:
187:
185:
180:
178:
173:
169:
165:
161:
151:
149:
145:
142:on a lattice
141:
137:
133:
130:
126:
125:Anne C. Davis
122:
118:
113:
111:
107:
103:
98:
96:
92:
88:
84:
80:
73:
71:
67:
63:
59:
53:
49:
46:
45:
44:
42:
41:Alfred Tarski
38:
34:
30:
26:
22:
3221:Order theory
3197:
3163:
3146:
3142:
3123:
3119:
3088:
3084:
3065:
3061:
3038:
3034:
3004:
2988:, New York.
2981:
2942:
2938:
2928:
2903:
2899:
2889:
2864:
2860:
2850:
2805:
2795:
2752:
2748:
2738:
2701:
2697:
2687:
2642:
2638:
2628:
2604:
2593:
2580:
2569:
2550:
2546:
2536:
2517:
2513:
2500:
2490:
2485:
2479:
2460:
2456:
2446:
2420:
2410:
2376:
2372:
2366:
2242:
2175:
2129:
2127:
2001:
1995:
1693:
1686:
1682:
1679:value oracle
1674:
1668:
1634:
1596:value oracle
1589:
1579:
1575:
1571:
1567:
1561:
1554:
1550:
1543:
1539:
1535:
1531:
1527:
1520:
1518:. Then from
1513:
1509:
1505:
1498:
1494:
1490:
1485:
1481:
1480:) and since
1477:
1473:
1469:
1464:
1460:
1453:
1418:
1414:
1373:
1371:
1362:
1358:
1352:
1348:
1344:
1340:
1336:
1332:
1327:
1326:with bounds
1319:
1315:
1311:
1309:
1304:
1300:
1254:
1252:
1247:
1243:
1239:
1235:
1231:
1227:
1222:
1218:
1214:
1207:
1203:
1199:
1195:
1191:
1185:
1181:
1177:
1171:
1167:
1160:
1156:
1152:
1147:
1143:
1139:
1135:
1129:
1125:
1121:
1117:
1113:
1106:
1102:
1098:
1094:
1088:
1084:
1078:
1074:
1069:
1064:
1060:
1055:
1024:
1018:
1014:
1010:
1003:
999:
995:
991:
987:
982:
978:
973:
967:
963:
956:
952:
948:
944:
940:
935:
931:
930:
924:
854:
750:
746:
680:
677:
660:differential
657:
646:
606:
602:
563:
559:
551:
547:
543:
539:
535:
531:
522:
444:
440:
432:
428:
416:
411:
399:
390:
382:
376:
362:
357:
349:
345:
341:
337:
329:
321:
317:
313:
305:
297:
293:
288:
284:
276:
272:
268:
263:
259:
255:
253:
248:
244:
240:
236:
224:
220:
216:
212:
208:
204:
200:
196:
190:
183:
176:
171:
157:
147:
143:
139:
135:
131:
114:
99:
82:
78:
76:
70:fixed points
55:
51:
47:
32:
21:mathematical
18:
977:belongs to
670:equations.
542: ) →
417:Let L be a
186:fixed point
179:fixed point
127:: If every
110:game theory
3215:Categories
2970:References
2815:2202.05913
2762:2010.02618
2588:Example 3.
2493:: 133–134.
1559:or simply
1008:, that is
239:such that
203:such that
115:A kind of
3182:120679842
3093:CiteSeerX
2959:0022-0531
2920:0363-0129
2881:0304-4068
2842:246823965
2787:222141645
2779:1549-6325
2730:202538977
2659:0304-3975
2582:MathWorld
2553:: 43–57.
2391:, so the
2340:
2335:⌉
2309:⌈
2269:
2245:=3, only
2223:
2218:⌉
2204:⌈
2156:
2102:Θ
2055:⋯
2036:Θ
1973:
1937:
1931:⋅
1922:
1913:
1872:
1853:≈
1837:
1831:⋯
1818:
1775:
1769:⋯
1756:
1750:⋅
1741:
1732:
1666:queries.
1645:Ω
1615:
1548:, giving
1436:⋁
1397:⋁
1287:⟩
1284:≥
1265:⟨
1189:(because
1039:⋁
896:≥
890:∣
884:∈
875:⋀
866:⋀
826:≤
820:∣
814:∈
805:⋁
796:⋁
773:⟩
770:≤
761:⟨
730:→
724::
701:⟩
698:≤
689:⟨
605: )
575:⊆
562: )
550: )
496:≤
475:≤
469:∣
463:∈
282:sequences
97:lattice.
95:power set
23:areas of
2980:(2003).
2602:(2002).
2508:(1955).
2426:See also
2358:queries.
1468:we have
1025:Now let
785:, with:
668:operator
664:integral
534: :
433:L be an
427: :
328:, where
326:ordinals
267:) = lim
184:greatest
164:supremum
134: :
117:converse
2379:) is a
1365:, then
1212:and so
1175:. Then
1165:, i.e.
552:on the
421:with a
356:of the
296:is lim
168:infimum
91:subsets
87:lattice
85:is the
19:In the
3180:
3095:
3011:
2992:
2957:
2918:
2879:
2840:
2830:
2785:
2777:
2728:
2718:
2657:
2616:
2002:unique
1146:, but
932:Proof.
554:family
375:, see
348:) and
227:; the
121:proved
31:, the
3178:S2CID
2838:S2CID
2810:arXiv
2783:S2CID
2757:arXiv
2726:S2CID
2438:Notes
1564:() ⊆
1456:() ⊆
1357:. If
1303:, so
1111:, so
674:Proof
607:i.e.
564:s.t.
447:chain
258:(lim
177:least
160:empty
56:be a
54:, ≤)
25:order
3009:ISBN
2990:ISBN
2955:ISSN
2916:ISSN
2877:ISSN
2828:ISBN
2775:ISSN
2716:ISBN
2655:ISSN
2614:ISBN
2404:and
2381:game
2371:. A
2128:For
1910:poly
1729:poly
1696:):
1557:) ∈
1538:) ≤
1422:and
1330:and
1310:For
1234:) =
1221:) ≤
1198:) ≤
1184:) ∈
1124:) ≤
1101:) ≤
1092:and
1068:and
1017:) ∈
994:) ≤
961:and
666:and
443:) ≤
247:) =
229:dual
223:) ≤
211:) =
191:The
181:(or
166:and
104:and
39:and
27:and
3170:doi
3151:doi
3128:doi
3124:217
3103:doi
3070:doi
3043:doi
2947:doi
2943:135
2908:doi
2869:doi
2820:doi
2767:doi
2706:doi
2702:151
2647:doi
2643:401
2555:doi
2522:doi
2465:doi
2305:log
2260:log
2197:log
2147:log
1970:log
1934:log
1919:log
1863:log
1834:log
1815:log
1772:log
1753:log
1738:log
1612:log
1335:: {
1318:in
1210:)))
943:= {
745:on
304:of
254:If
195:of
123:by
89:of
68:of
66:set
48:Let
3217::
3176:.
3147:14
3145:.
3122:.
3118:.
3101:.
3089:56
3087:.
3066:61
3064:.
3060:.
3039:21
3037:.
3033:.
2984:.
2953:.
2941:.
2937:.
2914:.
2904:17
2902:.
2898:.
2875:.
2865:19
2863:.
2859:.
2836:.
2826:.
2818:.
2804:.
2781:.
2773:.
2765:.
2753:18
2751:.
2747:.
2724:.
2714:.
2696:.
2667:^
2653:.
2641:.
2637:.
2579:.
2551:82
2549:.
2545:.
2516:.
2512:.
2459:.
2455:.
2408:.
2400:,
1677::
1530:≤
1523:∈
1508:≤
1493:≤
1488:,
1472:=
1463:∈
1417:⊆
1412:,
1361:≤
1351:≤
1347:≤
1343:|
1339:∈
1314:,
1250:.
1170:∈
1155:≤
1116:≤
1087:≤
1077:∈
1063:⊆
1022:.
1006:))
966:∈
959:)}
951:≤
947:|
662:,
431:→
404:.
393:.
340:=
336::
251:.
138:→
112:.
3201:.
3184:.
3172::
3157:.
3153::
3136:.
3130::
3109:.
3105::
3078:.
3072::
3051:.
3045::
3017:.
2998:.
2961:.
2949::
2922:.
2910::
2883:.
2871::
2844:.
2822::
2812::
2789:.
2769::
2759::
2732:.
2708::
2661:.
2649::
2622:.
2585:.
2563:.
2557::
2530:.
2524::
2518:5
2491:6
2473:.
2467::
2461:5
2346:)
2343:L
2332:2
2328:/
2324:)
2321:1
2318:+
2315:d
2312:(
2301:(
2298:O
2275:)
2272:L
2264:2
2256:(
2253:O
2243:d
2229:)
2226:L
2215:3
2211:/
2207:d
2201:2
2193:(
2190:O
2176:d
2162:)
2159:L
2151:2
2143:(
2140:O
2130:d
2111:)
2108:L
2105:(
2071:)
2066:d
2062:N
2058:+
2052:+
2047:1
2043:N
2039:(
1979:)
1976:L
1967:(
1964:O
1943:)
1940:L
1928:)
1925:L
1916:(
1907:(
1904:O
1878:)
1875:L
1867:d
1859:(
1856:O
1850:)
1845:d
1841:N
1826:1
1822:N
1812:(
1809:O
1788:)
1783:d
1779:N
1764:1
1760:N
1747:)
1744:L
1735:(
1726:(
1723:O
1694:i
1689:i
1687:N
1683:d
1675:f
1654:)
1651:L
1648:(
1635:L
1621:)
1618:L
1609:(
1606:O
1580:P
1576:P
1572:W
1568:f
1562:f
1555:y
1553:(
1551:f
1546:)
1544:y
1542:(
1540:f
1536:w
1534:(
1532:f
1528:w
1521:y
1516:)
1514:w
1512:(
1510:f
1506:w
1501:)
1499:w
1497:(
1495:f
1491:x
1486:W
1482:w
1478:x
1476:(
1474:f
1470:x
1465:W
1461:x
1454:f
1439:W
1433:=
1430:w
1419:P
1415:W
1400:L
1394:=
1389:L
1385:1
1374:P
1363:b
1359:a
1355:}
1353:b
1349:x
1345:a
1341:L
1337:x
1333:b
1328:a
1320:L
1316:b
1312:a
1305:P
1301:L
1281:,
1276:p
1273:o
1269:L
1255:f
1248:f
1244:u
1240:D
1236:u
1232:u
1230:(
1228:f
1223:u
1219:u
1217:(
1215:f
1208:u
1206:(
1204:f
1202:(
1200:f
1196:u
1194:(
1192:f
1186:D
1182:u
1180:(
1178:f
1172:D
1168:u
1163:)
1161:u
1159:(
1157:f
1153:u
1148:u
1144:D
1140:u
1138:(
1136:f
1132:)
1130:u
1128:(
1126:f
1122:x
1120:(
1118:f
1114:x
1109:)
1107:u
1105:(
1103:f
1099:x
1097:(
1095:f
1089:u
1085:x
1079:D
1075:x
1070:L
1065:L
1061:D
1056:u
1054:(
1042:D
1036:=
1033:u
1019:D
1015:x
1013:(
1011:f
1004:x
1002:(
1000:f
998:(
996:f
992:x
990:(
988:f
983:f
979:D
974:L
968:D
964:x
957:x
955:(
953:f
949:x
945:x
941:D
936:P
927:.
925:f
911:}
908:)
905:x
902:(
899:f
893:x
887:L
881:x
878:{
872:=
869:P
855:f
841:}
838:)
835:x
832:(
829:f
823:x
817:L
811:x
808:{
802:=
799:P
767:,
764:P
751:f
747:L
733:L
727:L
721:f
695:,
692:L
630:)
627:A
624:(
621:F
618:=
615:A
603:X
601:(
587:)
584:A
581:(
578:F
572:A
560:X
558:(
548:X
546:(
544:P
540:X
538:(
536:P
518:.
502:}
499:u
493:x
490:,
487:)
484:x
481:(
478:f
472:x
466:L
460:x
457:{
441:u
439:(
429:L
391:f
383:L
358:f
350:f
346:f
344:(
342:f
338:f
330:f
322:f
318:f
314:f
306:L
298:f
294:f
289:n
285:x
277:n
273:x
271:(
269:f
264:n
260:x
256:f
249:x
245:x
243:(
241:f
237:x
225:x
221:x
219:(
217:f
213:x
209:x
207:(
205:f
201:x
197:f
172:f
148:L
144:L
140:L
136:L
132:f
83:L
52:L
50:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.