FIXED POINTS AS NASH EQUILIBRIA

FIXED POINTS AS NASH EQUILIBRIA

JUAN PABLO TORRES-MART´INEZ

Received 27 March 2006; Revised 19 September 2006; Accepted 1 October 2006

The existence of fixed points for single or multivalued mappings is obtained as a corollary of Nash equilibrium existence in finitely many players games.

Copyright © 2006 Juan Pablo Torres-Mart´ınez. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, dis- tribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In game theory, the existence of equilibrium was uniformly obtained by the application of a fixed point theorem. In fact, Nash [3,4] shows the existence of equilibria for nonco- operative static games as a direct consequence of Brouwer [1] or Kakutani [2] theorems.

More precisely, under some regularity conditions, given a game, there always exists a cor- respondence whose fixed points coincide with the equilibrium points of the game.

However, it is natural to ask whether fixed points arguments are in fact necessary tools to guarantee the Nash equilibrium existence. (In this direction, Zhao [5] shows the equivalence between Nash equilibrium existence theorem and Kakutani (or Brouwer) fixed point theorem in an indirect way. However, as he points out, a constructive proof is preferable. In fact, any pair of logical sentencesAandBthat are true will be equivalent (in an indirect way). For instance, to show thatAimpliesBit is sufficient to repeat the proof ofB.) For this reason, we study conditions to assure that fixed points of a continu- ous function, or of a closed-graph correspondence, can be attained as Nash equilibria of a noncooperative game.

2. Definitions

LetY⊂Rⁿbe a convex set. A functionv:Y →Ris quasiconcave if, for eachλ∈(0, 1), we havev(λy1+ (1−λ)y2)≥min{v(y1),v(y2)}, for all (y1,y2)∈Y×Y. Moreover, if for each pair (y1,y2)∈Y×Y such thaty1=y2the inequality above is strict, independently of the value ofλ∈(0, 1), we say thatvis strictly quasiconcave.

Hindawi Publishing Corporation Fixed Point Theory and Applications Volume 2006, Article ID 36135, Pages1–4 DOI 10.1155/FPTA/2006/36135

2 Fixed points as Nash equilibria

A mapping f :X⊂R^m→Xhas a fixed point if there isx∈Xsuch that f(x)=x. A vectorx∈Xis a fixed point of a correspondenceΦ:XXifx∈Φ(x).

Given a gameᏳ= {I,S_i,vⁱ}, in which each playeri∈I= {1, 2,...,n}is characterized by a set of strategiesSi⊂Rⁿⁱ, and by an objective functionvⁱ:ⁿ_j=1Sj→R, a Nash equi- librium is a vectors=(s1,s2,...,sn)∈Πⁿ_i=1Si, such thatvⁱ(s)≥vⁱ(si,s−i), for allsi∈Si, for alli∈I, wheres−i=(s1,...,s_i−1,s_i+1,...,s_n).

Finally, letᏴ= {S:∃n∈N,S⊂Rⁿis nonempty, convex, and compact}. 3. Main Results

Consider the following statements.

[Nash-1]. GivenᏳ= {I,S_i,vⁱ}, suppose that each setS_i∈Ᏼand that objective functions are continuous in its domains and strictly quasiconcave in its own strategy. Then there is a Nash equilibrium forᏳ.

[Nash-2]. GivenᏳ= {I,Si,vⁱ}, suppose that each setSi∈Ᏼand that objective functions are continuous in its domains and quasiconcave in its own strategy. Then there is a Nash equilibrium forᏳ.

[Brouwer]. GivenX∈Ᏼ, every continuous functionf :X→Xhas a fixed point.

[Kakutani^∗]. GivenX∈Ᏼ, every closed-graph correspondenceΦ:XX, withΦ(x)∈ Ᏼfor allx∈X, has a fixed point, provided thatΦ(x)=_m

j=1π^m_j(Φ(x)) for eachx∈X⊂ R^m. (For each j∈ {1,...,m}, the projectionsπ^m_j :R^m→Rare defined byπ^m_j (x)=x_j, wherex=(x1,...,xm)∈R^m.) (The last property,Φ(x)=_m

j=1π^m_j (Φ(x)), is not necessary to assure the existence of a fixed point, provided that the other assumptions hold. How- ever, when objective functions are quasiconcave, [Kakutani^∗] is sufficient to assure the existence of a Nash equilibrium.)

Our results are [Nash-1]→[Brouwer].

Proof. Given a nonempty, convex, and compact setX⊂R^m and a continuous function f :X→X, consider a gameᏳwith two playersI= {A,B}, which are characterized by the sets of strategiesSA=SB=X and by the objective functions:v^A(xA,xB)= − xA−xB 2

andv^B(xA,xB)= − f(xA)−xB 2, where · denotes the Euclidean norm inR^m. As objective functions are continuous inS_A×S_B and strictly quasiconcave in own strategy, there exists a Nash equilibrium (xA,xB). Moreover, xA=xB andxB= f(xA), that assure the existence of a fixed point of f :X→X.

In fact, ifx^A=x^B, thenv^A(x^A,x^B)<0. Thus, playerAcan improve his gains choosing a responsex^A=x^B∈X, asv^A(x^B,x^B)=0, a contradiction. Analogous arguments prove thatx^B=f(x^A) becausef(x^A)∈X.

We have [Nash-2]→[Kakutani^∗].

Proof. Fix a setX⊂Ᏼand a correspondenceΦ:XXthat satisfies the assumptions of [Kakutani^∗]. Define, for each 1≤i≤m, the functionsκ^m_i :R^m×R^m→R^m×Rby κ_i^m(x,y)=(x,yi), wherey=(y1,...,ym)∈R^m.

Juan Pablo Torres-Mart´ınez 3 Consider a gameᏳwithm+ 1 players,{0, 1,...,m}, characterized by the sets of strate- gies (S0, (Si; i >0)) :=(X, (π_i^m(X); i >0)) and by the objective functions:v⁰(x0,x−0)=

− x0−x−0 2,vⁱ(x0,x1,...,x_m)= −min(r,si)∈κ^mi(Gr[Φ]) (x0,x_i)−(r,s_i) max, whereGr[Φ]

denotes the graph ofΦ, · maxis the max-norm, andx−0:=(x1,...,xm).

As hypotheses of [Nash-2] hold (see the appendix), there is an equilibrium (x0; (x1,...,x_m)) for Ᏻ. It follows that x_i∈π_i^m(Φ(x0))(If x_i∈/ π_i^m(Φ(x0)) then, by defini- tion, (x0,xi)∈/ κ^m_i (Gr[Φ]). Thus, playeri’s utility,vⁱ(x0,x1,...,xm)<0. However, choos- ing anyxi∈π_i^m(Φ(x0))= ∅, the playerican improve his gains, as (x0,xi)∈κ^m_i (Gr[Φ]) and, therefore, his utility will be equal to zero, a contradiction.) Therefore, by Assump- tion [Kakutani^∗], (x1,...,xm)∈Φ(x0). Finally,x0=(x1,...,xm)∈Φ(x0)(Ifx0=x−0:= (x1,...,xn), we have thatv⁰(x0,x−0) := − x0−x−0 2<0. Thus, player 0 can improve his position choosingx0=x−0∈X.) That concludes the proof.

Appendix

It follows from definitions above that the sets of strategies satisfy the assumptions of [Nash-2], objective functions are continuous andv⁰is quasiconcave in it own strategy.

Thus, rest to assure that functionsvⁱ, with i≥1, are quasiconcave in its own strategy.

This will be a direct consequence of the following lemma, takingZ=κ^m_i (Gr[Φ]).

Givenx∈R^m+1and a nonempty setZ⊂R^m+1, the distance fromxtoZ isd(x,Z)= inf_z∈Z x−z max. Note that the functionx→d(x,Z) is continuous, because|d(x1,Z)− d(x2,Z)| ≤ x1−x2 max. For convenience of notations, letπ:R^m×R→R^mbe the pro- jection defined byπ(x,y)=x.

Lemma A.1. Suppose thatZ⊂R^m+1 is a nonempty and compact set such that, for each x∈R^m, bothπ(Z) and Z∩π⁻¹(x) are convex sets. Then the function f :R^m×R→R defined by f(x,t)=d((x,t),Z) is quasiconvex int.

Proof. Fix a vector x0∈R^m. We have to show thatL_c= {t∈R; d((x0,t),Z)≤c}is a convex set for everyc≥0. Assume by contradiction that, givenc≥0, there are scalars t1< t∗< t2 such thatt1,t2∈Lc andt∗∈Lc. LetA:= {x∈π(Z); x−x0 max≤c}and consider the following sets:

A1= {x∈A;∃t∈Rs.t. (x,t)∈Z,t≤t∗−c};

A2= {x∈A;∃t∈Rs.t. (x,t)∈Z,t≥t∗+c}. (A.1)

Sinced((x0,t∗),Z)> c, we haveA=A1∪A2. Moreover,A1∩A2= ∅. (If there exists a vectorx∈A1∩A2, then x−x0 max≤cand, by the convexity ofZ∩π⁻¹(x), (x,t∗)∈Z, contradictingd((x0,t∗),Z)> c.) SinceZis compact,A1andA2are compact as well. And sinceπ(Z) is convex, so isA. In particular,Ais connected. Therefore,A1= ∅orA2= ∅. On the other hand, d((x0,t1),Z)≤c, so there exists a point (x,t)∈Z c-close to (x0,t1). Then x−x0 max≤candt≤t1+c < t∗+c, thereforex∈A\A2, proving that A1= ∅. Analogously, it follows fromd((x0,t2),Z)≤cthatA2= ∅. We have obtained a

contradiction.

4 Fixed points as Nash equilibria Acknowledgments

I am indebted with Jairo Bochi for useful suggestions and comments. I also would like to thank the suggestions of Carlos Herv´es-Beloso, Alexandre Belloni, and Eduardo Loyo.

References

[1] L. E. J. Brouwer, ¨Uber Abbildung von Mannigfaltigkeiten, Mathematische Annalen 71 (1912), no. 4, 598.

[2] S. Kakutani, A generalization of Brouwer’s fixed point theorem, Duke Mathematical Journal 8 (1941), no. 3, 457–459.

[3] J. F. Nash, Equilibrium points inn-person games, Proceedings of the National Academy of Sci- ences of the United States of America 36 (1950), no. 1, 48–49.

[4] , Non-cooperative games, Annals of Mathematics. Second Series 54 (1951), 286–295.

[5] J. Zhao, The equivalence between four economic theorems and Brouwer’s fixed point theorem, Working Paper, Departament of Economics, Iowa State University, Iowa, 2002.

Juan Pablo Torres-Mart´ınez: Department of Economics, Pontif´ıcia Universidade Cat ´olica do Rio de Janeiro (PUC-Rio), Marquˆes de S˜ao Vicente 225, Rio de Janeiro 22453-900, Brazil

E-mail address:jptorres [email protected]