# On a Fixed Point Theorem for General Multivalued Mappings on Finite Sets with Applications in Game Theory

Authors: Shravan Luckraz
Journal: Journal of Mathematics
 (2022)

---

## Abstract

We propose a new fixed point theorem that completely characterizes the existence of fixed points for multivalued maps on finite sets. Our result can be seen as a generalization of Abian’s fixed point theorem. In the context of finite games, our result can be used to characterize the existence of a Nash equilibrium in pure strategies and can therefore distinguish pure strategy equilibria from mixed strategy equilibria in the celebrated Nash theorem.


---

## Body

## 1. Introduction

The finite version of Abian’s [1] fixed point theorem states that given a function from a finite set into itself, the set cannot be partitioned into three sets so that the intersection of each of these sets with their image is empty if and only if the mapping has a fixed point. Although this result can be applied to all functions that have a finite domain, it can be shown that it does not generalize to multivalued mappings which are often referred to as correspondences (1 see [2] for a proof of this claim). As a result, Abian’s theorem cannot be applied to problems in game theory where the best response map is multivalued. In this paper, we solve this problem by providing a new fixed point theorem that can be defined over any abstract finite set and that works for multivalued maps. In its most general form, our theorem completely characterizes the fixed point problem for correspondences over finite sets.The fixed point theorem we propose, when put in the context of the widely studied class of finite games, can help fill the gap between the existence of a completely mixed strategy equilibrium and the existence of a pure strategy equilibrium as it is well known that the existence theorem of Nash (1950, 1951) [3,4] does not distinguish between the two (2 although from the Nash theorem, we know that the Prisoner’s Dilemma, the Battle of Sexes, and the game of Matching Pennies have equilibrium points, we cannot tell which of these games have pure strategy equilibria). In fact, although the Nash theorem is one of the most important results in game theory, it only guarantees that an equilibrium (pure or mixed) exists and therefore a part of the problem of existence of equilibrium points in pure strategies remains unsolved. While most of the subsequent research on the problem of existence of equilibrium points in games have generalized Nash’s theorem in more general and abstract infinite spaces, (for example, see [5–17, 19–26]), fewer studies have retained the finite strategy space assumption (3 for example, see [27–32]). (It is important to note that the generalization of the problem to infinite spaces with a richer topological structure does not solve the pure strategy equilibrium problem when the space is finite and mixed strategies are not allowed). Nevertheless, as observed by [2], the latter work do not give a complete characterization of equilibrium points in finite games as they only provide sufficient conditions and hence, there are no known characterizations of pure strategy equilibria for finite games.It was argued by [2] that it is the lack of a topological structure when the strategy space (without mixed extension) is a finite set which renders the problem at hand difficult. [2] also observes that Abian’s partitioning method does not work for multivalued maps. In this paper, we solve this problem by using an equivalent fixed point result due to the author [33] who relates the idea of cycle to Abian’s fixed point theorem. By representing the fixed point problem on a directed graph, we make use of [33]’s idea to generalize Abian’s theorem by first defining a set of all infinite walks of the mapping and second, by providing the necessary and sufficient conditions that these walks need to satisfy so that the mapping has a fixed point. In its most general form, the fixed point theorem we propose shows that a fixed point exists if and only if at least one of these walks converges in the Cauchy sense. The cyclicity of best response maps in games was also considered by the authors of [34] who show that some weak acyclicity condition is necessary for the existence of a unique Nash equilibrium in every subgame. More recently, the authors of [30] gave a related sufficient condition for the existence of pure strategy Nash equilibria for the class of finite games (with n>2 players) that satisfy some unilaterally competitive (UC) property which was first developed by the authors of [35]. (4 While the authors of [35] gave some interesting properties of the UC class of games, the authors of [28] show in the first place that all quasi-concave, symmetric UC games have a symmetric pure strategy equilibrium and more recently (in [30]) that all UC games with at least three players have a Nash equilibrium). Another class of games that have the pure strategy Nash equilibrium property was given by the authors of [36,37] who proved the existence of equilibrium for all symmetric quasi-concave finite games two-player zero-sum games.Our contribution relative to the literature is threefold. First, we propose a new fixed point theorem for mappings acting on finite domains as our results generalize Abian’s fixed point theorem for multivalued maps. Our theorem is given in terms of some “convergent” like properties on the digraph induced by the mapping. Second, by applying our fixed point theorem to the class of finite games, we are able to give a complete characterization of pure strategy Nash equilibria. Therefore, our result not only sharpens the Nash theorem (as it can pin down the exact class of finite games have pure strategy equilibria) but is also able to successfully separate the completely mixed strategy equilibria from the pure ones. Third, our results readily generalize the existing results by the authors of [27,28,30,37] who provided sufficient conditions for the existence of pure strategy Nash equilibria. Furthermore, in the context of finite games, we are able to generalize the existence theorems of potential games ([31]) and supermodular games [38–41]. Finally, it is worth noting that while the condition we propose when imposed on best response maps guarantee the existence of a pure strategy Nash equilibrium, when applied to the class of games in satisfaction form (introduced by Debreu ([42]) and developed further by the authors of[43–46]), it can guarantee the existence of a satisfaction equilibrium.The rest of this paper is organized as follows. In the next section, we briefly introduce Abian’s theorem. In Section3, we give some new fixed point theorems for general mappings, Section 4 applies these theorems in the context of finite games, Section 5 compares our results to results in some well-known classes of games, while Section 6 gives the conclusion.


## 2. Abian’s Theorem and Multivalued Maps

In this section, we introduce the fixed point theorem due to Abian and show that its generalization to multivalued mappings on finite sets fails.


### 2.1. Abian’s Theorem

LetX be a nonempty finite set and let f:X⟶X. Then, f has a fixed point if X cannot be partitioned into three sets A,B, and C such that A∩FA=B∩FB=C∩FC=∅.It was showed by [33] that when the periodicity of f is even, then two sets suffice in the statement of Abian’s theorem. We now consider the above statement when the mapping is generalized to a set-valued map. For a given nonempty finite set X, let F:X⟶PX, where PX is the power set of X, be a nonempty valued correspondence. At times, we denote the correspondence by F:X↠X. [2] recently showed, using a counterexample, that it is not possible to characterize the fixed points of F using Abian’s three set partitioning method and as a result, an Abian-like theorem cannot be given for multivalued mappings on finite sets. The authors of [2] also went one step further to show that the theorem does not generalize even if the number of partitions is increased. In fact, it was shown that only the trivial partition (singletons) always works for multivalued maps.The above negative result and the desirability of a fixed point for correspondences over finite domains that can distinguish a pure strategy equilibrium from the set of mixed strategy equilibria in Nash’s theorem are our main motivations for this paper.


## 2.1. Abian’s Theorem

LetX be a nonempty finite set and let f:X⟶X. Then, f has a fixed point if X cannot be partitioned into three sets A,B, and C such that A∩FA=B∩FB=C∩FC=∅.It was showed by [33] that when the periodicity of f is even, then two sets suffice in the statement of Abian’s theorem. We now consider the above statement when the mapping is generalized to a set-valued map. For a given nonempty finite set X, let F:X⟶PX, where PX is the power set of X, be a nonempty valued correspondence. At times, we denote the correspondence by F:X↠X. [2] recently showed, using a counterexample, that it is not possible to characterize the fixed points of F using Abian’s three set partitioning method and as a result, an Abian-like theorem cannot be given for multivalued mappings on finite sets. The authors of [2] also went one step further to show that the theorem does not generalize even if the number of partitions is increased. In fact, it was shown that only the trivial partition (singletons) always works for multivalued maps.The above negative result and the desirability of a fixed point for correspondences over finite domains that can distinguish a pure strategy equilibrium from the set of mixed strategy equilibria in Nash’s theorem are our main motivations for this paper.


## 3. Fixed Point Theorem for Multivalued Maps on Finite Sets

For finite setX, let F:X⟶PX be a nonempty valued correspondence as defined in the previous section. From F, we define digraph GF=X,E, where E⊆X×X is the set of the edges of GF, satisfying the following. (5 See [47] for more details on digraphs).(1)∀x,y∈X,x,y∈Eiffy∈Fx.We assign weights to the edges ofE through mapping λ, so that λ:E⟶0,1 is defined as follows.(2)∀e=x,y∈E,(3)λx,y=1ifx≠y0ifx=y.LetTGFX denote the set of all infinite walks of GF. For a given finite walk w=wjj=1k in GF, we denote by lw the total weight of edges it encounters, with the convention that if an edge is repeated, then the total weight of the number of its occurrences contributes to lw. Formally, for each finite walk w=wjj=1k, the length of finite walk w, denoted by lw, is defined as follows.(4)lwjj=1k=∑j=1k−1λwj,wj+1.For any verticesx,y∈X, we let Wx,y be the set of all finite walks connecting x and y. Then, we can define the distance between x and y as follows.(5)dx,y=inflww∈Wx,yifWx,y≠∅,+∞otherwise.We say that infinite walks=sjj=1∞∈TGFX is Cauchy if for every ϵ>0, there exist some natural number N such that for all m,n>N, we have dsm,sn<ϵ. We say that a graph GF is closed if every sequence s∈TGFX is Cauchy.Theorem 1.
IfGF is a closed graph, then F has a fixed point.Proof.
We prove by contradiction. Suppose thatGF is closed but F has no fixed points. Then, for all x∈X, we have x∉Fx. As a result, there exist some s=sjj=1∞∈TGFX such that for each j, Fsj∋sj+1≠sj. Let ϵ=1/2. Then, since GF is a closed graph, for every natural N, there exist m,n>N, such that m=j and n=j+1 for some j th term of s. Now, since sj+1≠sj, we have dsj,sj+1=1>1/2=ϵ. As a result, this would imply that s is not Cauchy, and hence, GF is not closed, which is a contradiction.
Theorem1 gives a sufficient condition for the existence of fixed points for multivalued mappings on finite sets. The closed graph condition can be seen as the counterpart of the upper-hemicontinuity assumption of Kakutani’s fixed point theorem (see [3]). When the relationship defined by the mapping is represented by a digraph, the closed graph condition guarantees the existence of fixed points. The next result makes this closed graph condition more transparent and relates it direct to the acyclicity of the graph. We first define cycles more formally as follows.
We say thatGF has a cycle if it has some vertex x′ and finite walk w=wjj=1k∈Wx′,x′ satisfying the following: For all m,n∈1,…,k, where k>2, m≠n imply wm≠wn, except at m=1 and n=k, where w1=wk=x′.(6 Although the graph may have longer cycles with repeated vertices, the condition used in this definition is necessary for any kind of cycles to exist).Theorem 2.
IfGF is a closed graph, then F is acyclic.Proof.
We prove by contradiction. Suppose thatGF is closed but contains some cycle. Then, GF has some vertex x′ and finite walk w=wjj=1k∈Wx′,x′ satisfying for all m,n∈1,…,k, where k>2, m≠n imply wm≠wn, except at m=1 and n=k. Concatenating w with w ad infinitum, we obtain s=w;w;…. Hence, s=sjj=1∞∈TGFX such that for each j, Fsj∋sj+1≠sj. Then, we can use an argument similar to that in the proof of Theorem 1 to show that s is not Cauchy, and therefore, GF is not closed, which is a contradiction.
Theorem2 shows that the closed graph condition relates the acyclicity of the mapping which in turn relates to Abian’s fixed point theorem ([33]). Since from the standpoint of directed graphs the acyclicity condition may be easier to verify, Theorem 2 can be useful in the development of graph theoretic fixed point search algorithms.
Since our aim is to achieve a result that is parallel to Abian’s theorem for multivalued maps, the next theorem gives a complete characterization of fixed points for multivalued maps. The following definitions will be useful in establishing this result. We first make use of the notion of distance between two vertices to define an index onGF. For any given walk w=wjj=1 in GF, let mw be defined as follows. (7 Here, w can be finite or infinite).(6)mw=1infi≠j∈ℕdwi,wjifinfi≠j∈ℕdwi,wj≠0,+∞otherwise.
We will usem to define an index on GF. We first index an element of TGFX by wj for j∈K, where K can be countable or uncountable, so that TGFX=wjj∈K. We can now define index ℳ on GF as follows:(7)ℳGF=1ifmwj≠+∞for allj∈K,whereTGFX=wjj∈K,+∞otherwise.Theorem 3.
F has a fixed point if ℳGF=+∞.Proof.
(Only if) SupposeF has a fixed point. Then, there exist some Cauchy sequence in TGFX. An example of such a sequence is s=x,x,…. For such s, we have infi≠j∈ℕdwi,wj=0 and therefore, ms=+∞, which in turn implies that ℳGF=+∞.
If We prove by contradiction. Suppose that ℳGF=+∞ but F has no fixed points. Then, we claim that there are no Cauchy sequences in TGFX. Indeed, suppose that s=skk=1∞ were some Cauchy sequence in TGFX, then for all ϵ∈0,1, there would exist some N such that for all i,j>N, dsi,sj<ϵ . However, this would have implied that for some kth (>N) term of the sequence, we would have sk=sk+1, which would contradict the fact that F has no fixed points. Therefore, all sequences of TGFX are non-Cauchy.
Now, sinceℳGF=+∞, there must exist some s∈TGFX such that ms=+∞. Hence, for such an s, infi≠j∈ℕdwi,wj=0, which implies that there exist some edge e=x,y in GF satisfying x=y. Then, we can construct Cauchy sequence x,x,…∈TGFX, which leads to a contradiction. □
The above theorem reduces the fixed point problem to the construction of an index on the digraph induced by the mapping. The index we construct gives a “measure” to each walk inTGFX and it is shown that a fixed point exists if and only if this measure is infinite. Our result can also be seen as a finite interpretation of the well-known Lefschetz fixed point theorem [48] which uses an index that counts the loops of the underlying topological space. (8 Fixed point indices for mappings on topological spaces was invented by Lefschetz (1937).
We next show that a strengthening of Theorem1 can also be given as a characterization of fixed points for multivalued maps.Theorem 4.
F has a fixed point if GF has a Cauchy sequence.
The proof is similar to the proof of Theorem1.Theorem4 shows that as long as the digraph induced by the mapping has a Cauchy sequence, the map has a fixed point. We will show that Theorem 4 can be used in a straightforward manner to prove the existence of Nash equilibria in finite games.Remark 1.
Theorems1–4 readily generalize to mappings with countable domains as the assumption of finiteness was not used in the proofs.


## 4. Characterizing Pure Strategy Nash Equilibria in Finite Games

In this section, we apply the theorems obtained in the previous section in the context of finite noncooperative games. We denote a finite noncooperative game by tripleΓ=I,Sii∈I,uii∈I, where the set of players is denoted by I=1,…,n and Si the finite strategy space available to player i. We also denote the set of all strategy profiles by S so that each s∈S is an n-tuple, where S=∏i=1nSi. Finally, payoffs are defined by the vector-valued function u:S⟶ℝ++n.(9 Note that assuming strictly positive payoffs for each player does not lead to any loss of generality). Our aim will be to use the results obtained in the previous section to derive a necessary and sufficient condition for the existence of a pure strategy Nash equilibrium (NE) in any general finite game. As remarked by [2], the lack of the topological structure of space S, which can be an abstract set, hinders the usage of the powerful toolbox of functional analysis for fixed point theorems.(10 For example, games like the Prisoner’s Dilemma, The Battle of Sexes, and the Matching Pennies have abstract strategy spaces). Moreover, since we want to be able to distinguish pure strategies NE from mixed strategies NE, we cannot rely on the topological structure of the mixed extension as is typically done in the literature.


### 4.1. Fixed Points of the Unilateral Best Response Correspondence

The following definitions will be useful in establishing our results. We define the best response map of playeri with respect to some strategy profile s by the following:(8)BRis=si∗∈Si:∀si∈Si,uisi∗,s−i≥uisi,s−i.FromBRis, we define the best response correspondence of Γ by BRs≡∏i=1nBRis. We can then define a unilateral best response correspondence UNBR:S↠S as follows:(9)UNBRs=s′=si′,s−i∈Sifsi′∈BRisanduisi′,s−i>uisi,s−ifor some i,sotherwise.While it is well known that the game has a Nash equilibrium if and only if the best response mapBR has a fixed point, it is straightforward to show that UNBR has a fixed point if and only if the game has a Nash equilibrium. Indeed, suppose that s is a NE. Then, there exists no i such that uisi′,s−i>uisi,s−i . Thus, UNBRs=s is a fixed point. Next, suppose that UNBRs has a fixed point, say s. Then, no si′,s−i∈S satisfying uisi′,s−i>uisi,s−i are in UNBRs. Hence, s∈UNBRs is a NE. (11 Our notion of UNBR is in similar veins as the concepts of better (or best) improvement paths studied by [30, 34]).For gameΓ=I,Sii∈I,uii∈I, we define function u:S⟶ℝ as follows:(10)us=∑i=1nuis.We then say that gameΓ=I,Sii∈I,uii∈I is a payoff sum separable if u is a bijection from S into Rangeu.SinceUNBRs is a correspondence from a finite set into itself, we can define the directed graph GUNBRs as in the previous section and we can let TGUNBRs be the set of all infinite walks of GUNBRs. We then have the following definition.We say that payoff sum functionu converges weakly if for some sequence t=skk=1 in TGUNBRs, sequence uskk=1 converges to some point in Rangeu.The next theorem achieves our objective of completely characterizing pure strategy NE in finite games for the class of payoff-sum separable games.Theorem 6.
Suppose thatΓ is a payoff-sum separable. Then, Γ has a pure strategy NE if u converges weakly.Proof.
If We show that if uskk=1 converges to some u∗ in the range of u for some sequence t=skk=1∞∈TGUNBRs of graph GUNBRs, then UNBRs has a fixed point. Since uskk=1 converges to u∗, for every ϵ>0, there exist integer N such that for all m>N we have the following:(11)usm−u∗<ϵ.
Sinceu∗ is in the range of u, there exist some s∗ satisfying u∗=us∗. Let(12)ϵ=mins,s′∈S,s≠s′us−us′2.
Since the game is payoff-sum separable and finite,ϵ>0. Thus, if usm−u∗s∗<ε holds for all m>N along the sequence, we must have sm=s∗ for all m>N since(13)usm−u∗s∗<ε<usm−us″for alls″≠s∗.
Therefore,t is a Cauchy sequence and by Theorem 4, UNBRs has a fixed point. Hence, Γ has a NE.
(Only If) Suppose thatΓ has a NE, say s∗. Then, some Cauchy sequence t=skk=1∞=s∗,s∗,…∈TGUNBRs exists. Along this sequence, the payoff sum function sequence uskk=1 converges to. us∗.□
While Theorem6 gives us a characterization of NE, it is restricted to the class of payoff sum separable games. We next show that the result can be generalized to all finite games. For that, we need the following definitions.
We say thatΓ=I,Sii∈I,uii∈I and Γ′=I,Sii∈I,ui′i∈I are argmax payoff equivalent to if the following condition holds:(14)For everyiands−i,si∈BRis−iinΓ⇔si∈BRi′s−iinΓ′
It is to be noted that the only difference betweenΓ and Γ′ is the payoff function. An important implication of this definition is that finding a NE in Γ is equivalent to finding a NE in Γ′. The next theorem shows that every finite game has an argmax payoff equivalent game that is payoff separable.Theorem 7.
LetΓ=I,Sii∈I,uii∈I be a finite game. Then, Γ has an argmax payoff equivalent game Γ′=I,Sii∈I,ui′i∈I that is payoff separable.Proof.
For a givenΓ, we construct an argmax payoff equivalent sum separable game Γ′=I,Sii∈I,ui′i∈I by modifying the payoff of some player in Γ each time a pair of profiles yield the same payoff sum. The construction is as follows.(i)
Step 1: FixS1 for player 1 and enumerate S−1 by s−1pp=1M. For each p, consider set S1×s−1p.(Note that Tex translation failed). For each p and every pair s1,s1′∉BR1s−1p, if us1,s−1p=us1′,s−1p, profiles s1,s−1p, and s1′,s−1p can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1′,s−1p in Γ′. Thus, by the finiteness of the strategy space, for each p, we can make for all pairs s1,s1′∉BR1s−1p satisfy u′s1,s−1p≠u′s1′,s−1p in Γ′. Since pair s1,s1′∉BR1s−1p, Γ remains equivalent to Γ′.(ii)
Step 2: Forp,q∈1,…,M and s1 satisfying s1∉BR1s−1p, s1∉BR1s−1q, if us1,s−1p=us1,s−1q, profiles s1,s−1p, and s1,s−1q can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1,s−1q in Γ′. Thus, by the finiteness of the strategy space, for each p,q∈1,…,M satisfying s1∉BR1s−1p, s1∉BR1s−1q, we can make u′s1,s−1p≠u′s1,s−1q in Γ′. Moreover, by finiteness again, we can ensure that these payoff sum are distinguished from those modified in step 1. Hence, since s1∉BR1s−1p and s1∉BR1s−1q, Γ remains equivalent to Γ′. (12 The same step can be repeated for p,q∈1,…,M and s1, s1′ satisfying s1∈BR1s−1p, s1′∉BR1s−1q, if us1,s−1p=us1′,s−1q).(iii)
Step 3: Forp,q∈1,…,M satisfying s1∈BR1s−1p, s1∈BR1s−1q, if us1,s−1p=us1,s−1q, profiles s1,s−1p, and s1,s−1q can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1,s−1q in Γ′. Furthermore, for all s1′≠s1∈BR1s−1p, the payoff sum of s1′,s−1p will be subject to the same modification of player 1’s payoff as that of s1,s−1p so that Γ′ remains equivalent to Γ. Thus, by the finiteness of the strategy space, for each p,q∈1,…,M and s1 satisfying s1∈BR1s−1p and s1∈BR1s−1q, we can make u′s1,s−1p≠u′s1,s−1q in Γ′. Moreover, by finiteness again, we can ensure that these payoffs sum are distinguished from those modified in steps 1 and 2. Hence, Γ remains equivalent to Γ′. (13 The same step can be repeated for p , q∈1,…,M and s1, s1′ satisfying s1∈BR1s−1p, s1′∈BR1s−1q, if us1,s−1p=us1′,s−1q.(iv)
Step 4: For eachp and every pair s1,s1′∈BR1s−1p, if us1,s−1p=us1′,s−1p, profiles s1,s−1p, and s1′,s−1p can be made payoff sum separable by modifying the payoffs of player 2 so that u′s1,s−1p≠u′s1′,s−1p in Γ′. Furthermore, for profile s∗=s1,s2,s−1,−2p if s2∈BR1s−2∗, then the same modification will need to be made to all other s2′∈BR1s−2∗ so that Γ remains equivalent to Γ′. Moreover, by finiteness again, we can ensure that these payoffs sum are distinguished from those modified in steps 1, 2, and 3. Thus, by the finiteness of the strategy space, for each p we can make for all pairs s1,s1′∈BR1s−1p satisfy u′s1,s−1p≠u′s1′,s−1p in Γ′. Hence, Γ remains equivalent to Γ′.(v)
Step 5: If needed, repeat steps 1–4 untilΓ′ is payoff sum separable. By the finiteness of the strategy space, Γ′ can be made payoff sum separable in a finite number of steps.Theorem 8.
LetΓ=I,Sii∈I,uii∈I be a finite game. Then, Γ has a Nash equilibrium if it has an argmax payoff equivalent game Γ′=I,Sii∈I,ui′i∈I which satisfies (i) payoff sum separability and (ii) u′ converges weakly.Proof.
The proof follows from Theorems6 and 7. □
Theorem8 is the most general existence result for finite games in the literature as it does not impose any topological structure on S and it completely characterizes NE for the original class of games studied by Nash. From Theorem 7, we know that condition (i) is met for all finite games. Condition (ii) is the minimum requirement on the payoff function along some sequence of UNBRs needed for a pure strategy NE to exist.


### 4.2. Remark on the Complexity of the Pure Strategy NE Problem

While the literature often argues that since every finite game has an NE (in either pure or mixed strategies), one cannot use the concept of NP-completeness in assessing the complexity of the problem of finding an NE in finite games (see [49,50] for instance). (14 It is also known that the symmetric case of finding an NE is as hard as the general one). The appropriate notion of complexity used for this class of problems is the polynomial parity argument (directed case) (PPAD). The Lemke–Howson algorithm (due to [51]) is a well-known example of the PPAD class which uses a graph theoretical approach (directed paths on polytopes) to compute the NE. However, the Lemke–Howson algorithm is not an efficient algorithm as the number of vertices in the graph can be exponentially large (see[50,55]). When the class of NE is restricted to pure strategies, then the authors of [30, 34] show that games that satisfy certain properties (for example, UC games with more than two players) are weakly acyclic. Then, the pure strategy NE of such games are computable in polynomial time (P). In similar veins, our fixed point result given in Theorem 1 (when applied to finite games) is computable in P. Unfortunately, the more general results given in Theorems 3, 4, and 6 are not computable in P as they involve checking walks of the graph that can be exponentially long.


## 4.1. Fixed Points of the Unilateral Best Response Correspondence

The following definitions will be useful in establishing our results. We define the best response map of playeri with respect to some strategy profile s by the following:(8)BRis=si∗∈Si:∀si∈Si,uisi∗,s−i≥uisi,s−i.FromBRis, we define the best response correspondence of Γ by BRs≡∏i=1nBRis. We can then define a unilateral best response correspondence UNBR:S↠S as follows:(9)UNBRs=s′=si′,s−i∈Sifsi′∈BRisanduisi′,s−i>uisi,s−ifor some i,sotherwise.While it is well known that the game has a Nash equilibrium if and only if the best response mapBR has a fixed point, it is straightforward to show that UNBR has a fixed point if and only if the game has a Nash equilibrium. Indeed, suppose that s is a NE. Then, there exists no i such that uisi′,s−i>uisi,s−i . Thus, UNBRs=s is a fixed point. Next, suppose that UNBRs has a fixed point, say s. Then, no si′,s−i∈S satisfying uisi′,s−i>uisi,s−i are in UNBRs. Hence, s∈UNBRs is a NE. (11 Our notion of UNBR is in similar veins as the concepts of better (or best) improvement paths studied by [30, 34]).For gameΓ=I,Sii∈I,uii∈I, we define function u:S⟶ℝ as follows:(10)us=∑i=1nuis.We then say that gameΓ=I,Sii∈I,uii∈I is a payoff sum separable if u is a bijection from S into Rangeu.SinceUNBRs is a correspondence from a finite set into itself, we can define the directed graph GUNBRs as in the previous section and we can let TGUNBRs be the set of all infinite walks of GUNBRs. We then have the following definition.We say that payoff sum functionu converges weakly if for some sequence t=skk=1 in TGUNBRs, sequence uskk=1 converges to some point in Rangeu.The next theorem achieves our objective of completely characterizing pure strategy NE in finite games for the class of payoff-sum separable games.Theorem 6.
Suppose thatΓ is a payoff-sum separable. Then, Γ has a pure strategy NE if u converges weakly.Proof.
If We show that if uskk=1 converges to some u∗ in the range of u for some sequence t=skk=1∞∈TGUNBRs of graph GUNBRs, then UNBRs has a fixed point. Since uskk=1 converges to u∗, for every ϵ>0, there exist integer N such that for all m>N we have the following:(11)usm−u∗<ϵ.
Sinceu∗ is in the range of u, there exist some s∗ satisfying u∗=us∗. Let(12)ϵ=mins,s′∈S,s≠s′us−us′2.
Since the game is payoff-sum separable and finite,ϵ>0. Thus, if usm−u∗s∗<ε holds for all m>N along the sequence, we must have sm=s∗ for all m>N since(13)usm−u∗s∗<ε<usm−us″for alls″≠s∗.
Therefore,t is a Cauchy sequence and by Theorem 4, UNBRs has a fixed point. Hence, Γ has a NE.
(Only If) Suppose thatΓ has a NE, say s∗. Then, some Cauchy sequence t=skk=1∞=s∗,s∗,…∈TGUNBRs exists. Along this sequence, the payoff sum function sequence uskk=1 converges to. us∗.□
While Theorem6 gives us a characterization of NE, it is restricted to the class of payoff sum separable games. We next show that the result can be generalized to all finite games. For that, we need the following definitions.
We say thatΓ=I,Sii∈I,uii∈I and Γ′=I,Sii∈I,ui′i∈I are argmax payoff equivalent to if the following condition holds:(14)For everyiands−i,si∈BRis−iinΓ⇔si∈BRi′s−iinΓ′
It is to be noted that the only difference betweenΓ and Γ′ is the payoff function. An important implication of this definition is that finding a NE in Γ is equivalent to finding a NE in Γ′. The next theorem shows that every finite game has an argmax payoff equivalent game that is payoff separable.Theorem 7.
LetΓ=I,Sii∈I,uii∈I be a finite game. Then, Γ has an argmax payoff equivalent game Γ′=I,Sii∈I,ui′i∈I that is payoff separable.Proof.
For a givenΓ, we construct an argmax payoff equivalent sum separable game Γ′=I,Sii∈I,ui′i∈I by modifying the payoff of some player in Γ each time a pair of profiles yield the same payoff sum. The construction is as follows.(i)
Step 1: FixS1 for player 1 and enumerate S−1 by s−1pp=1M. For each p, consider set S1×s−1p.(Note that Tex translation failed). For each p and every pair s1,s1′∉BR1s−1p, if us1,s−1p=us1′,s−1p, profiles s1,s−1p, and s1′,s−1p can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1′,s−1p in Γ′. Thus, by the finiteness of the strategy space, for each p, we can make for all pairs s1,s1′∉BR1s−1p satisfy u′s1,s−1p≠u′s1′,s−1p in Γ′. Since pair s1,s1′∉BR1s−1p, Γ remains equivalent to Γ′.(ii)
Step 2: Forp,q∈1,…,M and s1 satisfying s1∉BR1s−1p, s1∉BR1s−1q, if us1,s−1p=us1,s−1q, profiles s1,s−1p, and s1,s−1q can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1,s−1q in Γ′. Thus, by the finiteness of the strategy space, for each p,q∈1,…,M satisfying s1∉BR1s−1p, s1∉BR1s−1q, we can make u′s1,s−1p≠u′s1,s−1q in Γ′. Moreover, by finiteness again, we can ensure that these payoff sum are distinguished from those modified in step 1. Hence, since s1∉BR1s−1p and s1∉BR1s−1q, Γ remains equivalent to Γ′. (12 The same step can be repeated for p,q∈1,…,M and s1, s1′ satisfying s1∈BR1s−1p, s1′∉BR1s−1q, if us1,s−1p=us1′,s−1q).(iii)
Step 3: Forp,q∈1,…,M satisfying s1∈BR1s−1p, s1∈BR1s−1q, if us1,s−1p=us1,s−1q, profiles s1,s−1p, and s1,s−1q can be made payoff sum separable by modifying the payoffs of player 1 so that u′s1,s−1p≠u′s1,s−1q in Γ′. Furthermore, for all s1′≠s1∈BR1s−1p, the payoff sum of s1′,s−1p will be subject to the same modification of player 1’s payoff as that of s1,s−1p so that Γ′ remains equivalent to Γ. Thus, by the finiteness of the strategy space, for each p,q∈1,…,M and s1 satisfying s1∈BR1s−1p and s1∈BR1s−1q, we can make u′s1,s−1p≠u′s1,s−1q in Γ′. Moreover, by finiteness again, we can ensure that these payoffs sum are distinguished from those modified in steps 1 and 2. Hence, Γ remains equivalent to Γ′. (13 The same step can be repeated for p , q∈1,…,M and s1, s1′ satisfying s1∈BR1s−1p, s1′∈BR1s−1q, if us1,s−1p=us1′,s−1q.(iv)
Step 4: For eachp and every pair s1,s1′∈BR1s−1p, if us1,s−1p=us1′,s−1p, profiles s1,s−1p, and s1′,s−1p can be made payoff sum separable by modifying the payoffs of player 2 so that u′s1,s−1p≠u′s1′,s−1p in Γ′. Furthermore, for profile s∗=s1,s2,s−1,−2p if s2∈BR1s−2∗, then the same modification will need to be made to all other s2′∈BR1s−2∗ so that Γ remains equivalent to Γ′. Moreover, by finiteness again, we can ensure that these payoffs sum are distinguished from those modified in steps 1, 2, and 3. Thus, by the finiteness of the strategy space, for each p we can make for all pairs s1,s1′∈BR1s−1p satisfy u′s1,s−1p≠u′s1′,s−1p in Γ′. Hence, Γ remains equivalent to Γ′.(v)
Step 5: If needed, repeat steps 1–4 untilΓ′ is payoff sum separable. By the finiteness of the strategy space, Γ′ can be made payoff sum separable in a finite number of steps.Theorem 8.
LetΓ=I,Sii∈I,uii∈I be a finite game. Then, Γ has a Nash equilibrium if it has an argmax payoff equivalent game Γ′=I,Sii∈I,ui′i∈I which satisfies (i) payoff sum separability and (ii) u′ converges weakly.Proof.
The proof follows from Theorems6 and 7. □
Theorem8 is the most general existence result for finite games in the literature as it does not impose any topological structure on S and it completely characterizes NE for the original class of games studied by Nash. From Theorem 7, we know that condition (i) is met for all finite games. Condition (ii) is the minimum requirement on the payoff function along some sequence of UNBRs needed for a pure strategy NE to exist.


## 4.2. Remark on the Complexity of the Pure Strategy NE Problem

While the literature often argues that since every finite game has an NE (in either pure or mixed strategies), one cannot use the concept of NP-completeness in assessing the complexity of the problem of finding an NE in finite games (see [49,50] for instance). (14 It is also known that the symmetric case of finding an NE is as hard as the general one). The appropriate notion of complexity used for this class of problems is the polynomial parity argument (directed case) (PPAD). The Lemke–Howson algorithm (due to [51]) is a well-known example of the PPAD class which uses a graph theoretical approach (directed paths on polytopes) to compute the NE. However, the Lemke–Howson algorithm is not an efficient algorithm as the number of vertices in the graph can be exponentially large (see[50,55]). When the class of NE is restricted to pure strategies, then the authors of [30, 34] show that games that satisfy certain properties (for example, UC games with more than two players) are weakly acyclic. Then, the pure strategy NE of such games are computable in polynomial time (P). In similar veins, our fixed point result given in Theorem 1 (when applied to finite games) is computable in P. Unfortunately, the more general results given in Theorems 3, 4, and 6 are not computable in P as they involve checking walks of the graph that can be exponentially long.


## 5. Applications

In this section, we apply the results obtained in the previous sections to some widely studied classes of games like potential games (Monderer and Shapley (1996) [31]), supermodular games (Topkis (1998) [40] and Vives (1990) [41]) and satisfaction form games (Debreu (1952) [42]). We will show that the existence of equilibrium results of potential games and supermodular games are special cases of Theorem 8.


### 5.1. Potential Games

Monderer and Shapley (1996) [31] showed that if there exist some function Q:S⟶ℝ such that(15)∀i,s−i∈S−i,∀si,si′∈Si,uisi′,s−i−uisi,s−i>0,(16)⇔Qsi′,s−i−Qsi,s−i>0.Then, the game is a potential game and has a pure strategy NE. Note that the above condition implies that if uisi′,s−i−uisi,s−i>0 for some i, then the inequality holds for all i. We now show that if a game is payoff sum separable and has potential, then the hypothesis of Theorem 6 is satisfied.Theorem 9.
LetΓ=I,X,Y,uii∈I be a payoff sum separable potential game. Then, it has a Nash equilibrium.Proof.
Suppose that the game is potential, that is, inequalities (15) and (16) imply that u is always increasing along any sequence of UNBRs. By the finiteness of the strategy space and payoff sum separability, u converges weakly and therefore by Theorem 6, the game has a Nash equilibrium. □
While the above result is given in terms of a payoff separable game, a theorem analogous to Theorem8 can be given to show that if any game satisfies the potential game condition, then there exist some argmax payoff equivalent payoff sum separable potential game Γ′ such that inequalities (15) and (16) are preserved and such that u′ converges weakly.


### 5.2. Supermodular Games

It is well known that supermodular games (see (Topkis (1998) [40] and Vives (1990) [41])) have the NE property due to the results by Tokpis and Tarski. We will construct a simple proof of this theorem for finite games using Theorem 4. For the sake of illustration, we will restrict the analysis to the case of two players and thus, we assume that Γ=I,X,Y,uii∈I is a supermodular game, where I=1,2, XY is an ordered lattice strategy space of player 1 (2) and such that the following increasing differences condition is satisfied by ui for each i. For all x′≥x and y′≥y, we have the following:(17)uix′,y′−uix,y′≥uix′,y−uix,y.We will also make use of the following result due to Topkis.Ifui is supermodular in x,y, and X and Y are lattices, then x∗y≡Argmaxx∈Xu1x,y is increasing in y and y∗x=Argmaxy∈Yu2x,y is increasing in x.Theorem 10.
LetΓ=I,X,Y,uii∈I be a payoff sum separable supermodular game. Then, Γ has a Nash equilibrium.Proof.
We prove by contradiction by supposing that the game is payoff sum separable and supermodular but does not have a NE. Consider some profilex0,y0 so that both x0 and y0 are the minimum (in the lattice ordering) of X and Y respectively. Since x0,y0 is not NE, without any loss of generality, we can assume that u1x1,y0−u1x0,y0>0 for some x1∈BR1x0,y0, satisfying x1>x0. Now, either x1,y0 is a NE, or by Topkis theorem, there exist some y1>y0 such that y1∈BR2x1,y0 satisfying u2x1,y1−u2x1,y0>0. (Note that at x1,y0, there is no profitable deviation from player 1 and hence, the only deviation can come from player 2.) But since x1,y1≫x0,y0, either x1,y1 is a NE or there exist some unilateral deviation that leads to some profile x2,y2≫x1,y1. By repeating the latter argument, one can construct sequence xi,yii=1 satisfying xi+1,yi+1≫xi,yi. By the ordering of the lattice, since either xi or yi is strictly increasing along xi,yii=1, one can construct some s∈TGUNBRs that does not have any finite cyclic subsequence. Then, on the one hand, s must be eventually Cauchy as it does not have any finite cyclic subsequence and on the other hand by payoff sum separability and since the game has no NE, Theorems 6 and 4 imply that GUNBRs has no Cauchy sequences, a contradiction. □
While the above result is given in terms of a payoff separable game, a theorem analogous to Theorem8 can be given to show that if any game satisfies the supermodularity condition, then there exists some argmax payoff equivalent supermodular game which preserves inequality (17) and satisfies the condition of Theorem 4 so that it has a NE.


### 5.3. Games in a Satisfaction Form

Our fixed point theorem readily applies to games in satisfaction form as it can establish the existence of a satisfaction equilibrium (SE) when the set of actions of each player is finite. The concept of SE was first introduced by Debreu (1952 [42]) and developed further recently by [42–44, 46] to study the learning behavior of players in games where players can only observe their own payoffs. An SE is an equilibrium in the sense that a player who is satisfied with her payoff has no incentives to deviate from her current action. It is well-known that in the context of electrical engineering (15 for the analysis of quality of service (QoS) in wireless ad hoc networks), SE has proved to be particularly useful. For example, the “players” of the game are often described by radio devices (network components) which can choose among different possible operating configurations with the objective of satisfying some targeted QoS. (16 more recently, SE was used in the fifth generation of cellular communications (5G) for tackling the problem of energy efficiency, spectrum sharing, and transmitting power control (see [44,45]).More formally, a game in satisfaction form is given by the tripleΛ=I,Sii∈I,fii∈I, where I is a finite set of n players, each player i has a finite set of actions denoted by Si and preference mapping fi given by the following correspondence.(18)fi:S1×…Si−1×Si+1×…Sn⟶2Si.As usual, we denote byS=∏i=1nSi the set of strategy profiles of the game. We say that s∗∈S is a satisfaction equilibrium (SE) if si∗∈fi for all i. We show that Theorems 1, 3, and 4 can be used to prove the existence of an SE in Λ. For that, we define mapping gi:S⟶2Si which extends fi to S as follows. For each s∈S, let gisi,s−i=fis−i and let g:S⟶2S be a correspondence satisfying gs≡∏i=1ngis. Then, it is clear that correspondence g has a fixed point if Λ=I,Sii∈I,fii∈I has an SE. (17 Indeed, suppose that s∗ is an SE of Λ. Then, for each i, si∗∈fis−i=gisi,s−i. Thus, s∗∈∏i=1ngis∗≡gs∗ and hence, it is a fixed point of g. Conversely, suppose that s∗ is a fixed point of g. Then, for each i, we have si∗∈gis∗=fis−i∗ and hence, it is an SE). The following results follow from Theorems 1, 3, and 4.(i)
IfGg is a closed graph, then Λ has an SE.(ii)
Λ has an SE if ℳGg=+∞.(iii)
Λ has an SE if Gg has a Cauchy sequence.


## 5.1. Potential Games

Monderer and Shapley (1996) [31] showed that if there exist some function Q:S⟶ℝ such that(15)∀i,s−i∈S−i,∀si,si′∈Si,uisi′,s−i−uisi,s−i>0,(16)⇔Qsi′,s−i−Qsi,s−i>0.Then, the game is a potential game and has a pure strategy NE. Note that the above condition implies that if uisi′,s−i−uisi,s−i>0 for some i, then the inequality holds for all i. We now show that if a game is payoff sum separable and has potential, then the hypothesis of Theorem 6 is satisfied.Theorem 9.
LetΓ=I,X,Y,uii∈I be a payoff sum separable potential game. Then, it has a Nash equilibrium.Proof.
Suppose that the game is potential, that is, inequalities (15) and (16) imply that u is always increasing along any sequence of UNBRs. By the finiteness of the strategy space and payoff sum separability, u converges weakly and therefore by Theorem 6, the game has a Nash equilibrium. □
While the above result is given in terms of a payoff separable game, a theorem analogous to Theorem8 can be given to show that if any game satisfies the potential game condition, then there exist some argmax payoff equivalent payoff sum separable potential game Γ′ such that inequalities (15) and (16) are preserved and such that u′ converges weakly.


## 5.2. Supermodular Games

It is well known that supermodular games (see (Topkis (1998) [40] and Vives (1990) [41])) have the NE property due to the results by Tokpis and Tarski. We will construct a simple proof of this theorem for finite games using Theorem 4. For the sake of illustration, we will restrict the analysis to the case of two players and thus, we assume that Γ=I,X,Y,uii∈I is a supermodular game, where I=1,2, XY is an ordered lattice strategy space of player 1 (2) and such that the following increasing differences condition is satisfied by ui for each i. For all x′≥x and y′≥y, we have the following:(17)uix′,y′−uix,y′≥uix′,y−uix,y.We will also make use of the following result due to Topkis.Ifui is supermodular in x,y, and X and Y are lattices, then x∗y≡Argmaxx∈Xu1x,y is increasing in y and y∗x=Argmaxy∈Yu2x,y is increasing in x.Theorem 10.
LetΓ=I,X,Y,uii∈I be a payoff sum separable supermodular game. Then, Γ has a Nash equilibrium.Proof.
We prove by contradiction by supposing that the game is payoff sum separable and supermodular but does not have a NE. Consider some profilex0,y0 so that both x0 and y0 are the minimum (in the lattice ordering) of X and Y respectively. Since x0,y0 is not NE, without any loss of generality, we can assume that u1x1,y0−u1x0,y0>0 for some x1∈BR1x0,y0, satisfying x1>x0. Now, either x1,y0 is a NE, or by Topkis theorem, there exist some y1>y0 such that y1∈BR2x1,y0 satisfying u2x1,y1−u2x1,y0>0. (Note that at x1,y0, there is no profitable deviation from player 1 and hence, the only deviation can come from player 2.) But since x1,y1≫x0,y0, either x1,y1 is a NE or there exist some unilateral deviation that leads to some profile x2,y2≫x1,y1. By repeating the latter argument, one can construct sequence xi,yii=1 satisfying xi+1,yi+1≫xi,yi. By the ordering of the lattice, since either xi or yi is strictly increasing along xi,yii=1, one can construct some s∈TGUNBRs that does not have any finite cyclic subsequence. Then, on the one hand, s must be eventually Cauchy as it does not have any finite cyclic subsequence and on the other hand by payoff sum separability and since the game has no NE, Theorems 6 and 4 imply that GUNBRs has no Cauchy sequences, a contradiction. □
While the above result is given in terms of a payoff separable game, a theorem analogous to Theorem8 can be given to show that if any game satisfies the supermodularity condition, then there exists some argmax payoff equivalent supermodular game which preserves inequality (17) and satisfies the condition of Theorem 4 so that it has a NE.


## 5.3. Games in a Satisfaction Form

Our fixed point theorem readily applies to games in satisfaction form as it can establish the existence of a satisfaction equilibrium (SE) when the set of actions of each player is finite. The concept of SE was first introduced by Debreu (1952 [42]) and developed further recently by [42–44, 46] to study the learning behavior of players in games where players can only observe their own payoffs. An SE is an equilibrium in the sense that a player who is satisfied with her payoff has no incentives to deviate from her current action. It is well-known that in the context of electrical engineering (15 for the analysis of quality of service (QoS) in wireless ad hoc networks), SE has proved to be particularly useful. For example, the “players” of the game are often described by radio devices (network components) which can choose among different possible operating configurations with the objective of satisfying some targeted QoS. (16 more recently, SE was used in the fifth generation of cellular communications (5G) for tackling the problem of energy efficiency, spectrum sharing, and transmitting power control (see [44,45]).More formally, a game in satisfaction form is given by the tripleΛ=I,Sii∈I,fii∈I, where I is a finite set of n players, each player i has a finite set of actions denoted by Si and preference mapping fi given by the following correspondence.(18)fi:S1×…Si−1×Si+1×…Sn⟶2Si.As usual, we denote byS=∏i=1nSi the set of strategy profiles of the game. We say that s∗∈S is a satisfaction equilibrium (SE) if si∗∈fi for all i. We show that Theorems 1, 3, and 4 can be used to prove the existence of an SE in Λ. For that, we define mapping gi:S⟶2Si which extends fi to S as follows. For each s∈S, let gisi,s−i=fis−i and let g:S⟶2S be a correspondence satisfying gs≡∏i=1ngis. Then, it is clear that correspondence g has a fixed point if Λ=I,Sii∈I,fii∈I has an SE. (17 Indeed, suppose that s∗ is an SE of Λ. Then, for each i, si∗∈fis−i=gisi,s−i. Thus, s∗∈∏i=1ngis∗≡gs∗ and hence, it is a fixed point of g. Conversely, suppose that s∗ is a fixed point of g. Then, for each i, we have si∗∈gis∗=fis−i∗ and hence, it is an SE). The following results follow from Theorems 1, 3, and 4.(i)
IfGg is a closed graph, then Λ has an SE.(ii)
Λ has an SE if ℳGg=+∞.(iii)
Λ has an SE if Gg has a Cauchy sequence.


## 6. Conclusion

We have shown that the original problem of existence of an equilibrium in finite games can be fully characterized without the need to extend the strategy space to mixed strategies. We proceeded by generalizing Abian’s theorem for correspondences and applying it in the context of finite games. Our result sharpens the celebrated Nash theorem as it can filter out the exact class of games that have pure strategy NE from the class of finite games (for which a NE in mixed strategies always exists). We also show that the existence of equilibrium points problem studied in supermodular games, potential games, and games in satisfaction form follow as special cases of our theorem for the finite case.



---

*Source: 2477124-2022-06-02.xml*