A recursion principle, generalized iteration methods and the axiom of choice are applied to prove the existence of extremal fixed points of set-valued mappings in posets, extremal solutions of an inclusion problem, and extremal Nash equilibria for a normal-form game.
Let PP be a non-empty partially ordered set (poset). As an introductory result we show that a set-valued mapping FF from PP to the set 2P∖0̸2P∖0̸ of non-empty subsets of PP has minimal and maximal fixed points, that is, the set Fix F={x∈P∣x∈F(x)}F={x∈P∣x∈F(x)} has minimal and maximal elements, if the following conditions hold.
(c1)
sup{c,y}∈Psup{c,y}∈P for some c∈Pc∈P and for every y∈Py∈P.
(c2)
If x≤yx≤y in PP, then for every z∈F(x)z∈F(x) there exists a w∈F(y)w∈F(y) such that z≤wz≤w, and for every w∈F(y)w∈F(y) there exists a z∈F(x)z∈F(x) such that z≤wz≤w.
(c3)
Strictly monotone sequences of F[P]=⋃{F(x):x∈P}F[P]=⋃{F(x):x∈P} are finite.
As for the proof, denote x0=cx0=c, and choose y0y0 from F(x0)F(x0). If y0≰x0y0≰x0, then x0<x1≔sup{c,y0}x0<x1≔sup{c,y0}. Apply then condition (c2) to choose y1y1 from F(x1)F(x1) such that y0≤y1y0≤y1. If y0=y1y0=y1, then stop. Otherwise, y0<y1y0<y1, whence x1=sup{c,y0}≤x2≔sup{c,y1}x1=sup{c,y0}≤x2≔sup{c,y1}, and apply again condition (c2) to choose y2y2 from F(x2)F(x2) such that y1≤y2y1≤y2. Continuing in the similar way, condition (c3) ensures that after a finite number of choices we get the situation, where yn−1=yn∈F(xn)yn−1=yn∈F(xn). In view of the above construction we then have xn≔sup{c,yn−1}=sup{c,yn}xn≔sup{c,yn−1}=sup{c,yn}.Denoting z0≔xnz0≔xn and w0≔ynw0≔yn then w0∈F(z0)w0∈F(z0) and w0≤sup{c,w0}=z0w0≤sup{c,w0}=z0. If w0=z0w0=z0, then z0z0 is a fixed point of FF. Otherwise, denoting z1≔w0z1≔w0, we have z1<z0z1<z0. In view of condition (c2) there exists a w1∈F(z1)w1∈F(z1) such that w1≤w0w1≤w0. If equality holds, then z1=w0=w1∈F(z1)z1=w0=w1∈F(z1), so that z1z1 is a fixed point of FF. Otherwise, w1<w0w1<w0, denote z2≔w1z2≔w1, and choose by (c2) such a w2∈F(z2)w2∈F(z2) that w2≤w1w2≤w1, and so on. Condition (c3) implies that a finite number of steps yield the situation zm≔wm−1=wm∈F(zm)zm≔wm−1=wm∈F(zm). Thus zmzm belongs to Fix FF. Being a subset of F[P]F[P], strictly monotone sequences of Fix FF are finite by condition (c3). This property implies in turn that Fix FF has minimal and maximal elements.
The above described result will be generalized in Section 3. For instance, we show that FF has minimal and maximal fixed points when the above conditions (c1) and (c2) hold and condition (c3) is replaced by order compactness of the values of FF and relative chain completeness of its range F[P]F[P]. The obtained results are then used in Section 4 to generalize existence results derived in [5], [6] and [7] for inclusion problem Lu∈NuLu∈Nu, where LL is a single-valued mapping from a poset VV to PP, and NN is a set-valued mapping from VV to 2P∖0̸2P∖0̸. Finally, in Section 5 results of Section 3 are applied to study the existence of extremal Nash equilibria for a normal-form game. Existence proofs require several consecutive applications of a recursion principle and generalized iteration methods introduced in [4] and [8] and presented in Section 2.
