Fixed-point computation: Difference between revisions

Revision as of 15:10, 16 April 2023

Revision as of 16:10, 17 April 2023

Line 1:

{{Short description|Computing the fixed point of a function}}

'''Fixed-point computation''' refers to the process of computing an exact or approximate [[Fixed point (mathematics)|fixed point]] of a given function.<ref name=":1">{{cite book |doi=10.1007/978-3-642-50327-6 |title=The Computation of Fixed Points and Applications |series=Lecture Notes in Economics and Mathematical Systems |year=1976 |volume=124 |isbn=978-3-540-07685-8 }}{{pn|date=April 2023}}</ref> In its most common form, we are given a function ''f'' that satisfies the condition to the [[Brouwer fixed-point theorem]], that is: ''f'' is continuous and maps the unit [[N-cube|''d''-cube]] to itself. The [[Brouwer fixed-point theorem]] guarantees that ''f'' has a fixed point, but the proof is not constructive. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in economics for computing a [[market equilibrium]], in game theory for computing a [[Nash equilibrium]], and in [[dynamic system]] analysis.

== Definitions ==

[[File:Fixed point example.svg|alt=an example function with three fixed points|thumb|The graph of an example function with three fixed points]]

The unit interval is denoted by ''<math>E'' := [0, 1]</math>, and the unit [[N-cube|''d''-dimensional cube]] is denoted by ''E^d''. A [[continuous function]] ''f'' is defined on ''E^d'' (from ''E^d'' to itself)''.'' Often, it is assumed that ''f'' is not only continuous but also [[Lipschitz continuous]], that is, for some constant ''L'', <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> for all ''x,y'' in ''E^d''.

A '''fixed point''' of ''f'' is a point ''x'' in ''E^d'' such that ''f''(''x'') = ''x''. By the [[Brouwer fixed-point theorem]], any contiuouscontinuous function from ''E^d'' to itself has a fixed point. But for general functions, it is impossible to compute a fixed point precisely, since it can be an arbitrary real number. Fixed-point computation algorithms look for ''approximate'' fixed points. There are several criteria for an approximate fixed point. Several common criteria are:<ref name=":3">{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A recursive algorithm for the infinity-norm fixed point problem |journal=Journal of Complexity |date=December 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 }}</ref>

* The '''residual criterion''': given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-residual fixed-point of''' '''''f''''' is a point ''x'' in ''E^d'' such that <math>|f(x)-x|\leq \varepsilon</math>, where here ''|.|'' denotes the [[maximum norm]]. That is, all ''d'' coordinates of the difference <math>f(x)-x</math> should be at most {{mvar|ε}}.<ref name=":0" />{{Rp|page=4}}

Line 12 ⟶ 15:

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If ''f'' is Lipschitz-continuous with constant ''L'', then <math>|x-x_0|\leq \delta</math> implies <math>|f(x)-f(x_0)|\leq L\cdot \delta</math>. Since <math>x_0</math> is a fixed-point of ''f'', this implies <math>|f(x)-x_0|\leq L\cdot \delta</math>, so <math>|f(x)-x|\leq (1+L)\cdot \delta</math>. Therefore, a δ-absolute fixed-point is also an {{mvar|ε}}-residual fixed-point with <math>\varepsilon = (1+L)\cdot \delta</math>.

The most basic step of a fixed-point computation algorithm is a '''value query''': given any ''x'' in ''E^d'', the{{Sentence fragment|date=April 2023}}

The function ''f'' is accessible via '''evaluation''' queries: for any ''x'', the algorithm can evaluate ''f''(''x''). The run-time complexity of an algorithm is usually given by the number of required evaluations.

== Contractive functions ==

A Lipschitz-continuous function with constant ''L'' is called [[Contractive|'''contractive''']] if ''L'' < 1; it is called [[Weakly-contractive|'''weakly-contractive''']] if ''L≤L ≤'' 1.Every contractive function satisfying Brouwer's condisions has a ''unique'' fixed point. Moreover, fixed-point computation for contractive functions is easier than for general functions.

[[File:Fixed point anime.gif|alt=computing a fixed point using function iteration|thumb|Computing a fixed point using function iteration]]

The first algorithm for fixed-point computation was the [[fixed-point iteration|'''fixed-point iteration''']] algorithm of Banach. [[Banach fixed point theorem|Banach's fixed-point theorem]] implies that, when fixed-point iteration is applied to a contraction mapping, the error after ''t'' iterations is in <math>O(L^t)</math>. Therefore, the number of evaluations required for a ''δ''-relative fixed-point is approximately <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. Sikorski and Wozniakowski<ref name=":5">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=Complexity of fixed points, I |journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 }}</ref> showed that Banach's algorithm is optimal when the dimension is large. Specifically, when <math>d\geq \log(1/\delta)/\log(1/L) </math>, the number of required evaluations of ''any'' algorithm for ''δ''-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ''L'' approaches 1, the number of evaluations approaches infinity. In fact, no finite algorithm can compute a ''δ''-absolute fixed point for all functions with L=1.<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=Optimal Solution of Nonlinear Equations |date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{pn|date=April 2023}}</ref>

When ''L'' < 1 and ''d'' = 1, the optimal algorithm is the '''Fixed Point Envelope''' (FPE) algorithm of Sikorski and Wozniakowski.<ref name=":5" /> It finds a ''δ''-relative fixed point using <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> queries, and a ''δ''-absolute fixed point using <math>O(\log(1/\delta)) </math> queries. This is much faster than the fixed-point iteration algorithm.<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=Robustness in Identification and Control |year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</ref>

The first algorithm for fixed-point computation was the [[fixed-point iteration]] algorithm of Banach. [[Banach fixed point theorem|Banach's fixed-point theorem]] implies that, when fixed-point iteration is applied to a contraction mapping, the error after ''t'' iterations is in <math>O(L^t)</math>. Therefore, the number of evaluations required for a ''δ''-relative fixed-point is approximately <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. Sikorski and Wozniakowski<ref name=":5">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=Complexity of fixed points, I |journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 }}</ref> showed that Banach's algorithm is optimal when the dimension is large. Specifically, when <math>d\geq \log(1/\delta)/\log(1/L) </math>, the number of required evaluations of ''any'' algorithm for ''δ''-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ''L'' approaches 1, the number of evaluations approaches infinity. In fact, no finite algorithm can compute a ''δ''-absolute fixed point for all functions with L=1.<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=Optimal Solution of Nonlinear Equations |date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{pn|date=April 2023}}</ref>

When L<1 and ''d''=1, the optimal algorithm is the Fixed Point Envelope (FPE) algorithm of Sikorski and Wozniakowski.<ref name=":5" /> It finds a ''δ''-relative fixed point using <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> queries, and a ''δ''-absolute fixed point using <math>O(\log(1/\delta)) </math> queries. This is much faster than the fixed-point iteration algorithm.<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=Robustness in Identification and Control |year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</ref>

When ''d''>1 but not too large, and ''L ≤'' 1, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).<ref>{{cite journal |last1=Huang |first1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |title=Approximating Fixed Points of Weakly Contracting Mappings |journal=Journal of Complexity |date=June 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 }}</ref> It finds an {{mvar|ε}}-residual fixed-point is using <math>O(d\cdot \log(1/\varepsilon)) </math> evaluations. When ''L''<1, it finds a ''δ''-absolute fixed point using <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> evaluations.

Shellman and Sikorski<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 }}</ref> presented an algorithm called '''BEFix''' (Bisection Envelope Fixed-point) for computing an {{mvar|ε}}-residual fixed-point of a two-dimensional function with ''L ≤'' 1, using only <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> queries. They later<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</ref> presented an improvement called '''BEDFix''' (Bisection Envelope Deep-cut Fixed-point), with the same worst-case guarantee but better empirical performance. When ''L''<1, BEDFix can also compute a δ-absolute fixed-point, using <math>O(\log(1/\varepsilon)+\log(1/(1-L)))</math> queries.

Shellman and Sikorski<ref name=":3" /> presented an algorithm called '''PFix''' for computing an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function with ''L ≤'' 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L'' < 1, PFix can be executed with <math>\varepsilon = (1-L)\cdot \delta</math>, and in that case, it computes a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> queries. It is more efficient than the iteration algorithm when ''L'' is close to 1. The algorithm is recursive: it handles a ''d''-dimensional function by recursive calls on (''d''-1)-dimensional functions.

=== Algorithms for differentiable functions ===

Line 32 ⟶ 35:

== General functions ==

For functions with Lipschitz constant ''L'' > 1, computing a fixed-point is much harder.

=== One dimension ===

For a 1-dimensional function (''d'' = 1), a δ-absolute fixed-point can be found using <math>O(\log(1/\delta))</math> queries using the [[bisection method]]: start with the interval <math>E := [0, 1]</math>; at each iteration, let ''x'' be the center of the current interval, and compute ''f''(''x''); if ''f''(''x'') > ''x'' then recurse on the sub-interval to the right of ''x''; otherwise, recurse on the interval to the left of ''x''. Note that the current interval always contains a fixed point, so after <math>O(\log(1/\delta))</math> queries, any point in the remaining interval is a δ-absolute fixed-point of ''f.'' Setting <math>\delta := \varepsilon/(L+1)</math>, where ''L'' is the Lipschitz constant, gives an {{mvar|ε}}-residual fixed-point, using <math>O(\log(L/\varepsilon) = \log(L) + \log(1/\varepsilon))</math> queries.<ref name=":0" />

=== Two or more dimensions: algorithms ===

For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski<ref name=":3" /> proved that, for any integers ''d''≥2 ≥ 2 and ''L'' > 1, finding a δ-absolute fixed-point of ''d''-dimensional ''L''-Lipschitz functions might require infinitely-many evaluations. The proof idea is as follows. For any integer ''T'' > 1, and for any sequence of ''T'' of evaluation queries (possibly adaptive), one can construct two functions that are Lipschitz-continuous with constant ''L'', and yield the same answer to all these queries, but one of them has a unique fixed-point at (''x'', 0) and the other has a unique fixed-point at (''x'', 1). Any algorithm using ''T'' evaluations cannot differentiate between these functions, so cannot find a δ-absolute fixed-point. This is true for any finite integer ''T''.

Several algorithms based on function evaluations have been developed for finding an {{mvar|ε}}-residual fixed-point

Line 47 ⟶ 50:

* B. Curtis Eaves<ref>{{cite journal |last1=Eaves |first1=B. Curtis |title=Homotopies for computation of fixed points |journal=Mathematical Programming |date=December 1972 |volume=3-3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |s2cid=39504380 }}</ref> presented the ''[[homotopy]] algorithm''. The algorithm works by starting with an affine function that approximates ''f'', and deforming it towards ''f'', while following the fixed point''.'' A book by Michael Todd<ref name=":1" /> surveys various algorithms developed until 1976.

* [[David Gale]]<ref>{{cite journal |first1=David |last1=Gale |year=1979 |title=The Game of Hex and Brouwer Fixed-Point Theorem |journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> showed that computing a fixed point of an ''n''-dimensional function (on the unit ''d''-dimensional cube) is equivalent to deciding who is the winner in an ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of an ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

** Construct a Hex board of size ''kd'', where ''<math>k'' > 1/''{{mvar|ε}}''\varepsilon</math>. Each vertex ''z'' corresponds to a point ''z''/''k'' in the unit ''n''-cube.

** Compute the difference ''f''(''z''/''k'') - ''z''/''k''; note that the difference is an ''n''-vector.

** Label the vertex ''z'' by a label in 1, ..., ''d'', denoting the largest coordinate in the difference vector.

** The resulting labeling corresponds to a possible play of the ''d''-dimensional Hex game among ''d'' players. This game must have a winner, and Gale presents an algorithm for constructing the winning path.

** In the winning path, there must be a point in which ''f_i''(''z''/''k'') - ''z''/''k'' is positive, and an adjacent point in which ''f_i''(''z''/''k'') - ''z''/''k'' is negative. This means that there is a fixed point of ''f'' between these two points.

In the worst case, the number of function evaluations required by all these algorithms is exponential in the binary representation of the accuracy, that is, in <math>\Omega(1/\varepsilon)</math>.

==== Two or more dimensions: queryQuery complexity ====

Hirsch, [[Christos Papadimitriou|Papadimitriou]] and Vavasis proved that<ref name=":0">{{cite journal |last1=Hirsch |first1=Michael D |last2=Papadimitriou |first2=Christos H |last3=Vavasis |first3=Stephen A |title=Exponential lower bounds for finding Brouwer fix points |journal=Journal of Complexity |date=December 1989 |volume=5 |issue=4 |pages=379–416 |doi=10.1016/0885-064X(89)90017-4 |s2cid=1727254 }}</ref> ''any'' algorithm based on function evaluations, that finds an {{mvar|ε}}-residual fixed-point of ''f,'' requires <math>\Omega(L'/\varepsilon)</math> function evaluations, where <math>L'</math> is the Lipschitz constant of the function <math>f(x)-x</math> (note that <math>L-1 \leq L' \leq L+1</math>). More precisely:

* For a 2-dimensional function (''d''=2), they prove a tight bound <math>\Theta(L'/\varepsilon)</math>.

* For any d ≥ 3, finding an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function requires <math>\Omega((L'/\varepsilon)^{d-2})</math> queries and <math>O((L'/\varepsilon)^{d})</math> queries.

The latter result leaves a gap in the exponent. Chen and Deng<ref name=":2" /> closed the gap. They proved that, for any ''d'' ≥ 2 and <math>1/\varepsilon > 4 d</math> and <math>L'/\varepsilon > 192 d^3</math>, the number of queries required for computing an {{mvar|ε}}-residual fixed-point is in <math>\Theta((L'/\varepsilon)^{d-1})</math>.

== Discrete fixed-point computation ==

A '''discrete function''' is a function defined on a subset of ''<math>\mathbb{Z}^d</math>'' (the ''d''-dimensional integer grid). There are several [[Discrete fixed-point theorem|discrete fixed-point theorems]], stating conditions under which a discrete function has a fixed point. For example, the '''Iimura-Murota-Tamura theorem''' states that (in particular) if ''f'' is a function from a rectangle subset of ''Z<supmath>\mathbb{Z}^d</supmath>'' to itself, and ''f'' is ''hypercubic [[Direction-preserving function|direction-preserving]]'', then ''f'' has a fixed point.

Let ''f'' be a direction-preserving function from the integer cube <math>\{1,... \dots,'' n''\}<sup>''^d''</supmath> to itself. Chen and Deng<ref name=":2" /> prove that, for any ''d'' ≥ 2 and ''n'' > 48 ''d'', computing such a fixed point requires <math>\Theta(n^{d-1})</math> function evaluations.

Chen and Deng<ref>{{cite journal |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |title=On the complexity of 2D discrete fixed point problem |journal=Theoretical Computer Science |date=October 2009 |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 }}</ref> define a different discrete-fixed-point problem, which they call '''2D-BROUWER'''. It considers a discrete function ''f'' on <math>\{0,...\dots,'' n''\}''<sup>^2</supmath>'' such that, for every ''x'' on the grid, ''f''(''x'') - ''x'' is either (0, 1) or (1, 0) or (-1, -1). The goal is to find a square in the grid, in which all three labels occur. The function ''f'' must map the square <math>\{0,...\dots,'' n''\}<sup>''^2''</supmath> to itself, so it must map the lines ''x'' = 0 and ''y'' = 0 to either (0, 1) or (1, 0); the line ''x'' = ''n'' to either (-1, -1) or (0, 1); and the line ''y'' = ''n'' to either (-1, -1) or (1,0). The problem can be reduced to '''2D-SPERNER''' (computing a fully-labeled triangle in a triangulation satisfying the conditions to [[Sperner's lemma]]), and therefore it is [[PPAD-complete]]. This implies that computing an approximate fixed-point is PPAD-complete even for very simple functions.

== Relation between fixed-point computation and root-finding algorithms ==

Line 74 ⟶ 77:

Fixed-point computation is a special case of root-finding: given a function ''f'' on ''E^d'', define <math>g(x) := |f(x)-x|</math>. Clearly, ''x'' is a fixed-point of ''f'' if and only if ''x'' is a root of ''g'', and ''x'' is an {{mvar|ε}}-residual fixed-point of ''f'' if and only if ''x'' is an {{mvar|ε}}-root of ''g''. Therefore, any [[root-finding algorithm]] (an algorithm that computes an approximate root of a function) can be used to find an approximate fixed-point.

The opposite is not true: finding an approximate root of a general function may be harder than finding an approximate fixed point. In particular, Sikorski<ref>{{cite journal |last1=Sikorski |first1=K. |title=Optimal solution of nonlinear equations satisfying a Lipschitz condition |journal=Numerische Mathematik |date=June 1984 |volume=43 |issue=2 |pages=225–240 |doi=10.1007/BF01390124 |s2cid=120937024 }}</ref> proved that finding an {{mvar|ε}}-root requires <math>\Omega(1/\varepsilon^d)</math> function evaluations. This gives an exponential lower bound even for a one-dimensional function (in contrast, an {{mvar|ε}}-residual fixed-point of a one-dimensional function can be found using <math>O(\log(1/\varepsilon))</math> queries using the [[bisection method]]). Here is a proof sketch.<ref name=":0" />{{Rp|page=35}} Construct a function ''g'' that is slightly larger than {{mvar|ε}} everywhere in ''E^d'' except in some small cube around some point ''x''₀, where ''x''₀ is the unique root of ''g''. If ''g'' is [[Lipschitz continuous]] with constant ''L'', then the cube around ''x''₀ can have a side-length of {{mvar|ε}}<math>\varepsilon/''L''</math>. Any algorithm that finds an {{mvar|ε}}-root of ''g'' must check a set of cubes that covers the entire ''E^d''; the number of such cubes is at least <math>(L/\varepsilon)^d</math>.

However, there are classes of functions for which finding an approximate root is equivalent to finding an approximate fixed point. One example<ref name=":2">{{cite book |doi=10.1145/1060590.1060638 |chapter=On algorithms for discrete and approximate brouwer fixed points |title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |year=2005 |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |pages=323–330 |isbn=1581139608 |s2cid=16942881 }}</ref> is the class of functions ''g'' such that <math>g(x)+x</math> maps ''E^d'' to itself (that is: ''<math>g''(x)+x</math> is in ''E^d'' for all x in ''E^d''). This is because, for every such function, the function <math>f(x) := g(x)+x</math> satisfies the conditions to Brouwer's fixed-point theorem. Clearly, ''x'' is a fixed-point of ''f'' if and only if ''x'' is a root of ''g'', and ''x'' is an {{mvar|ε}}-residual fixed-point of ''f'' if and only if ''x'' is an {{mvar|ε}}-root of ''g''. Chen and Deng<ref name=":2" /> show that the discrete variants of these problems are computationally equivalent: both problems require <math>\Theta(n^{d-1})</math> function evaluations.

== Communication complexity ==

Roughgarden and Weinstein<ref>{{cite book |doi=10.1109/FOCS.2016.32 |chapter=On the Communication Complexity of Approximate Fixed Points |title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |year=2016 |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |pages=229–238 |isbn=978-1-5090-3933-3 |s2cid=87553 }}</ref> studied the [[communication complexity]] of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function ''f'' and the other knows a function ''g''. Both functions are Lipschitz continuous and satisfy Brouwer's conditions. The goal is to compute an approximate fixed point of the [[composite function]] <math>g\circ f</math>. They show that the deterministic communication complexity is in <math>\Omega(2^d)</math>.

== Further reading ==

* Equilibria, fixed points, and complexity classes: a survey.<ref>{{cite journal |last1=Yannakakis |first1=Mihalis |title=Equilibria, fixed points, and complexity classes |journal=Computer Science Review |date=May 2009 |volume=3 |issue=2 |pages=71–85 |doi=10.1016/j.cosrev.2009.03.004 |url=https://drops.dagstuhl.de/opus/volltexte/2008/1311/ }}</ref>

== References ==

{{reflist}}

== Further reading ==

* Equilibria, fixed points, and complexity classes: a survey.<ref>{{cite journal |last1=Yannakakis |first1=Mihalis |title=Equilibria, fixed points, and complexity classes |journal=Computer Science Review |date=May 2009 |volume=3 |issue=2 |pages=71–85 |doi=10.1016/j.cosrev.2009.03.004 |url=https://drops.dagstuhl.de/opus/volltexte/2008/1311/ }}</ref>

[[Category:Fixed-point theorems]]