FOR CONSTRAINED GENERALIZED GAMES

(1)

FOR CONSTRAINED GENERALIZED GAMES

P. S. SRINIVASAN AND P. VEERAMANI

Received 28 August 2003 and in revised form 11 November 2003

We obtain suﬃcient conditions for the existence of an equilibrium pair for a particular constrained generalized game as an application of a best proximity pair theorem.

1. Introduction

Consider the following game involvingnplayers. For theith player a pair (Xi,Yi) of strategy sets is associated. Knowing the choice of strategiesxⁱ∈Xⁱ=_n

j=1,j=iX_j of all other players, theith-player choice is restricted toAi(xⁱ)⊆Yi. Otherwise the choice will be made from Xi. According to these preferences, let fi:Yi×Xⁱ→Rbe the payoﬀfunc- tion associated with theith player for eachi=1,. . .,n. In this situation, it is natural to expect an optimal approximate solution which will fulfill the requirement to some ex- tent. Therefore, it should be contemplated to find a pair (x,y) wherex∈X=_n

i=1Xiand y∈Y=_n

i=1Yiwhich will behave like an equilibrium point of a generalized game, that is,y_i∈A_i(xⁱ) and max_z_∈_A_i_(xⁱ)f_i(z,xⁱ)= f_i(y_i,xⁱ) for eachi=1,. . .,n, and satisfy the opti- mization constraint, namely, the distance betweenxandyis minimum with respect to XandY. In this case, the pair (x,y) is called anequilibrium pairand the game is termed asconstrained generalized game. Indeed, in this paper, suﬃcient conditions for the existence of an equilibrium pair for this constrained generalized game are obtained as an application of a best proximity pair theorem.

The entire edifice of game theory expounds with a mathematical search to strike an optimal balance between persons generally having conflicting interests. Each player has to select one from his fixed range of strategies so as to bring the best outcome according to his own preferences.

Following the pioneering work of Debreu [1], the generalized game is one in which the choice of each player is restricted to a subset of strategies determined by the choice of other players. Mathematically, the situation is described as follows.

Let there benplayers. LetX1,. . .,Xnbe nonempty compact convex sets in a normed linear spaceF. LetXibe the strategy set and letfi:X=_n

i=1Xi→Rbe the payoﬀfunction for theith player, for eachi=1,. . .,n. Given the strategiesxⁱof all other players, the choice

Copyright©2004 Hindawi Publishing Corporation Fixed Point Theory and Applications 2004:1 (2004) 21–29 2000 Mathematics Subject Classification: 47H10, 47H04, 54H25 URL:http://dx.doi.org/10.1155/S1687182004308132

(2)

of theith player is restricted to the setA_i(xⁱ)⊆X_i. An equilibrium point in a generalized game is an elementx∈Xsuch that for eachi=1,. . .,n,x_i∈A_i(xⁱ) and

y∈maxAi(xⁱ)f_iy,xⁱ=f_ix_i,xⁱ=f_i(x), (1.1) where the following convenient notations are used.

Notation 1.1. Denote

X= n i=1

Xi, Xⁱ= n

j=1 j=i

Xj. (1.2)

A pointxofXwhoseith coordinate isxiandxⁱ∈Xⁱis written as (xi,xⁱ).

The above definition of the equilibrium point is a natural extension of the Nash equilibrium point introduced by Nash in [6].

Since then a number of generalizations for the existence of an equilibrium point have been given in various directions. For instance, the existence results of equilibria of generalized games were given by Ding and Tan [2], Tan and Yuan [13], Ionescu Tulcea [4], Lassonde [5], and so forth. For a unified treatment on the study of the existence of equilibria of generalized games in various settings, we refer to Yuan [15].

On the other hand, consider the following economic situation. Suppose that goods are manufactured and sold in different locations. Each location can be both a manufacturing as well as a selling unit. It is agreed that the ultimate place where the goods get sold would be determining the payofffor the goods. Let there bensuch locations. For each location, two strategiesX_iandY_iare associated, one to that of manufacturing unit and other to that of selling unit. Knowing the manufacturing strategyxⁱof all other locations, the choice of selling strategy at theith location is restricted toAi(xⁱ)⊆Yi. Also, let fi:Yi×Xⁱ→R be the payoffassociated with theith location. Moreover, the cost involved in the travel of goods to different places should also be taken into account. In this situation, one cannot expect an equilibrium point as the strategy setsXiandYimay be quite different. In view of this stand point, it is natural to expect a pair of points (x,y), wherex∈X=_n

i=1X_iand y∈Y=_n

i=1Yi, which will fulfill the requirement as in the case of equilibrium point of a generalized game and also minimize the traveling cost where the traveling cost is denoted byx−y. Therefore, it is contemplated to find a pair of points (x,y) wherex∈Xand y∈Ysuch that fori=1,. . .,n,yi∈Ai(xⁱ),

z∈maxAi(xⁱ)f_iz,xⁱ= f_iy_i,xⁱ (1.3) andx−y =d(X,Y), where

d(X,Y)=Infa−b:a∈X,b∈Y. (1.4) In this case, the pair (x,y) is called anequilibrium pairfor this economic situation which is newly termed asconstrained generalized game.

(3)

If the setsY_i coincide with X_i for i=1,. . .,n, thenY =X and it is easy to see that the equilibrium pair boils down to a single pointxwhich is an equilibrium point for a generalized game in the sense of Debreu [1].

In this paper, an existence of an equilibrium pair for this constrained generalized game is obtained. For this, a best proximity pair theorem exploring the suﬃcient conditions which ensure the existence of an elementx∈Asuch that

d(x,Tx)=d(A,B) (1.5)

is obtained inSection 3for the given nonempty subsetsAandBof a normed linear space Fand a Kakutani multifunctionT:A→2^B. This result is applied to obtain the existence of an equilibrium pair of the constrained game inSection 4. Indeed, an existence theorem for equilibrium point of a generalized game due to Debreu [1] is obtained as a corollary.

2. Preliminaries

This section covers the preliminaries and the results that are required in the sequel.

LetX andY be nonempty sets. Amultivalued mapormultifunctionT fromX toY denoted byT:X→2^Yis defined to be a function which assigns to each element ofx∈X a nonempty subsetTxof Y. Fixed points of the multifunctionT:X→2^X will be the pointsx∈Xsuch thatx∈Tx.

Let X andY be any two topological spaces. LetT :X→2^Y be a multivalued map.

The mapT is said to beupper semicontinuous(resp.,lower semicontinuous) ifT⁻¹(A) := {x∈X:T(x)∩A= ∅}is closed (resp., open) inXwheneverAis a closed (resp., open) subset ofY. AlsoTis said to be continuous if it is both lower semicontinuous and upper semicontinuous.

A multifunctionT:X→Y is said to have compact values if for eachx∈X,T(x) is compact subset ofY. Also,Tis said to be acompact multifunctionifT(X) is a compact subset ofY.

It is known that ifTis an upper semicontinuous multifunction with compact values, thenT(K) is compact wheneverKis a compact subset ofXifXis Hausdorﬀ.

A multifunctionT:X→2^Yis said to be aKakutani multifunction[5] if the following conditions are satisfied:

(1)Tis upper semicontinuous;

(2) eitherTxis a singleton for eachx∈X(in which caseY is required to be a Haus- dorﬀtopological vector space) or for eachx∈X,Txis a nonempty, compact, and convex subset ofY (in which caseY is required to be a convex subset of a Hausdorﬀtopological vector space).

The collection of all Kakutani multifunctions fromXtoYis denoted by᏷(X,Y).

A multifunctionT:X→2^Yfrom a topological spaceXto another topological spaceY is said to be aKakutani factorizable multifunctionif it can be expressed as a composition of finitely many Kakutani multifunctions.

The collection of all Kakutani factorizable multifunctions fromXtoY is denoted by

᏷C(X,Y).

(4)

IfT=T1T2···T_n is a Kakutani factorizable multifunction, then the functionsT1, T2,. . .,T_nare known as thefactorsofT. It is a noteworthy fact thatTneed not be convex valued even though its factors are convex valued.

LetAbe any nonempty subset of a normed linear spaceX. ThenPA:X→2^Adefined by

PA(x)=

a∈A:a−x =d(x,A) (2.1)

is the set of all best approximations inAto any elementx∈X.

It is known that ifAis compact and convex subset ofX,PA(x) is a nonempty compact convex subset ofAand the multivalued mapP_Ais upper semicontinuous onX.

A single-valued function f :X→Ris said to be quasiconcave if the set

x∈X:f(x)≥t (2.2)

is convex for eacht∈R. 3. Best proximity pair theorem

Consider the fixed point equationTx=x whereT is a nonself operator. If this operator equation does not have a solution, then the next attempt is to find an elementxin a suitable space such thatxis close toTxin some sense. In fact, a classical best approximation theorem, due to Fan [3], states that ifKis a nonempty compact convex subset of a Hausdorﬀlocally convex topological vector spaceEwith a continuous seminormpand T:K_→Eis a single-valued continuous map, then there exists an elementx0∈K such that

px0−Tx0

=dTx0,K. (3.1)

Later, this result has been generalized by Sehgal and Singh [10,11] to the one for continuous multifunctions. It is remarked that they have also proved the following generalization of the result due to Prolla [7].

IfKis a nonempty approximately compact convex subset of a normed linear spaceX, T:K→Xa multivalued continuous map withT(K) relatively compact, andg:K→Kan aﬃne, continuous, and surjective single-valued map such thatg⁻¹sends compact subsets ofKonto compact sets, then there exists an elementx0inKsuch that

dgx0,Tx0

=dTx0,K. (3.2)

In the setting of Hausdorﬀ locally convex topological vector spaces, Vetrivel et al.

[14] have established existential theorems that guarantee the existence of a best approx- imant for continuous Kakutani factorizable multifunctions which unify and generalize the known results on best approximations.

The known example [11] shows that the requirement of continuity assumption of the involved multifunction in Sehgal and Singh’s result [11] cannot be relaxed.

(5)

Example 3.1. LetX=R²,K=[0, 1]× {0}, andg=I, the identity map. LetT:K→2^Xbe defined by

T(a, 0)=





(0, 1) ifa=0,

the line segment joining (0, 1) and (1, 0) ifa=0. (3.3) ThenTis upper semicontinuous but not lower semicontinuous. Also it is clear that there is nox∈Ksuch that

d(x,Tx)=d(Tx,K). (3.4)

Remark 3.2. In [12], the above known example has not been quoted correctly. Example 1.1 of [12] should be replaced by the above example.

On the other hand, even though a best approximation theorem guarantees the existence of an approximate solution, it is contemplated to find an approximate solution which is optimal. The best proximity pair theorem (see [9]) sheds light in this direction.

Indeed a best proximity pair theorem due to Sadiq Basha and Veeramani [8] provides suﬃcient conditions that ensure the existence of elementx0∈Asuch thatd(x0,Tx0)= d(A,B) where the givenT:A→2^B is a Kakutani factorizable multifunction defined on the suitable subsetsAandBof a topological vector spaceE. The pair (x0,Tx0) is called a best proximity pairofT. The best proximity pair theorem seeks an approximate solution which is optimal.

The following fixed point theorem, due to Lassonde [5], for Kakutani factorizable multifunctions will be invoked to establish the main result of this section.

Theorem3.3 (Lassonde [5]). IfSis a nonempty convex subset of a Hausdorﬀlocally convex topological vector space, then any compact Kakutani factorizable multifunctionT:S→2^S (i.e., any compact multifunction in the family᏷C(S,S)) has a fixed point.

LetAandBbe any two nonempty subsets of a normed linear space. Before stating the principal result of this section, the following notions are recalled:

d(A,B) :=Infd(a,b) :a∈A,b∈B, Prox(A,B) :=

(a,b)∈A×B:d(a,b)=d(A,B), A0:=

a∈A:d(a,b)=d(A,B) for someb∈B, B0:=

b∈B:d(a,b)=d(A,B) for somea∈A.

(3.5)

IfA= {x}, thend(A,B) is written asd(x,B). Also, ifA= {x}andB= {y}, thend(x,y) denotesd(A,B) which is preciselyx−y.

The following best proximity pair theorem [8] which will be used to prove the existence of an equilibrium pair is included for the sake of completeness.

Theorem3.4. LetAandBbe nonempty compact convex subsets of a normed linear spaceX and letT:A→2^Bbe an upper semicontinuous multifunction. Further assume that for each xinA,Txis a nonempty closed convex subset ofBandT(A0)⊆B0.

(6)

Then there exists an elementx∈Asuch that

d(x,Tx)=d(A,B). (3.6)

Proof. Consider the metric projection mapP_A:X→2^Adefined as P_A(x)=

a∈A:a−x =d(x,A). (3.7) AsAis a nonempty compact convex set,P_A(x) is a nonempty closed, convex subset of A, for eachxinA. Also it is well known thatPAis an upper semicontinuous multivalued map.

Now, it is claimed thatP_A(Tx)⊆A0, for eachxinA0.

Lety∈PA(Tx). Theny∈PA(z), for somez∈Tx. This implies thatx−y =d(z,A).

But it is given thatT(A0)⊂B0. Hencez∈B0. Butz∈B0implies that there existsa∈A such thata−z =d(z,A). Now

z−y =d(z,A)≤ z−a =d(A,B). (3.8) This implies thatz−y =d(A,B). Hencey∈A0. Consequently,PA(Tx)⊆A0, for each xinA0.

SinceAandBare compact sets,A0= ∅. Also it is easy to prove thatA0is compact and convex. Now, forxinA0,PA(Tx) need not be a convex set. Here, the fixed point theorem of Lassonde [5] is invoked. ThoughPA◦Tis not a convex-valued multifunction,PA◦T: A0→2^A⁰is a Kakutani factorizable multifunction. Hence, by the fixed point theorem of Lassonde, there existsx∈A0such thatx∈PA(Tx).

Now,x∈PA(Tx) implies thatx−y =d(y,A), for somey∈Tx. ThenTx⊆B0im- plies that there existsa∈Asuch thata−y =d(A,B). Hence

x−y =d(y,A)≤ y−a =d(A,B). (3.9) Thereforex−y =d(A,B). Asd(x,Tx)≤ x−y =d(A,B), henced(x,Tx)=d(A,B).

This proves the theorem.

Remark 3.5. In [8], the above theorem is proved in more general setup where the setAis approximately compact andTis a Kakutani factorizable multifunction.

4. Constrained generalized game

This section is devoted to principal results on game theory.

The following lemma is an important tool in the proof ofTheorem 4.4. For the proof, we refer to [12].

Lemma4.1. LetAandBbe nonempty compact subsets in a normed linear spaceFand let f :A×B→Rbe a continuous function. Given a continuous multifunctionT:A→2^Bwith compact values, the functiong:A→Rdefined byg(x)=δ(Tx,x) :=maxz∈T(x)f(z,x)is a continuous function.

The proof of the principal theorem of this section invokes the best proximity pair theorem (Theorem 3.4). Before that, the following definitions are introduced.

(7)

Let X1,. . .,X_n and Y1,. . .,Y_n be nonempty compact convex sets in a normed linear spaceF. Also, letX=_n

i=1X_i,Y=_n

i=1Y_i, and X0=

x∈X:x−y =d(X,Y) for somey∈Y. (4.1) Definition 4.2. Let f_i:Y_i×Xⁱ→R, fori=1,. . .,n, bensingle-valued functions. These nfunctions are said to satisfy a condition (A) with respect to the given multifunctions Ai:Xⁱ→2^Yⁱif for eachx∈X0and for ally∈Ysuch that

yi∈Ai xⁱ, δ_iA_ixⁱ,xⁱ:= max

z∈Ai(xⁱ)f_iz,xⁱ=f_iy_i,xⁱ for eachi=1,. . .,n, (4.2) there existsa∈Xsuch thata−y ≤d(X,Y).

Definition 4.3. Let the single-valued functionsf_i:Y_i×Xⁱ→Rand the multifunctionsA_i: Xⁱ→2^Yⁱ, fori=1,. . .,n, be given. Letx∈Xandy∈Y be such that, for eachi=1,. . .,n,

(a) yi∈Ai(xⁱ),

(b)δ_i(A_i(xⁱ),xⁱ) :=max_z_∈_A_i_(xⁱ)f_i(z,xⁱ)=f_i(y_i,xⁱ), (c)x−y =d(X,Y).

Then the pair (x,y) is called anequilibrium pairfor the game which is termed ascon- strained generalized game.

Theorem4.4. LetX1,. . .,X_nandY1,. . .,Y_nbe nonempty compact convex sets in a normed linear space F. Fori=1,. . .,n, let fi:Yi×Xⁱ→R be continuous functions satisfying a condition (A) with respect to the given lower semicontinuous multifunctionsAi:Xⁱ→2^Yⁱ, i=1,. . .,n, in᏷(Xⁱ,Y_i), and are such that for any fixedxⁱ∈X_i, the functiony_i→ f_i(y_i,xⁱ) is quasiconcave onXifor eachi=1,. . .,n. Then there exist an equilibrium pair for the con- strained generalized game.

Proof. For eachi=1,. . .,n, let the multifunctionEi:Xⁱ→2^Yⁱbe defined as follows:

E_ixⁱ=

y_i∈A_ixⁱ:f_iy_i,xⁱ=δ_iA_ixⁱ,xⁱ (4.3) andE:X→2^Yas

E(x)= n i=1

Ei

xⁱ. (4.4)

It is shown thatEsatisfies all the conditions ofTheorem 3.4. For this, it is claimed that Ei∈᏷(Xⁱ,Yi), fori=1,. . .,n.

Leti∈ {1,. . .,n}be fixed. For any fixedxⁱ∈Xⁱ,E_i(xⁱ) is nonempty and compact be- cause the functionyi→ fi(yi,xⁱ) is continuous on the compact setAi(xⁱ). Now, it is shown thatEi(xⁱ) is convex.

Letz1,z2∈E_i(xⁱ). This implies fi

z1,xⁱ≥δi

Ai

xⁱ,xⁱ, fi

z2,xⁱ≥δi

Ai

xⁱ,xⁱ. (4.5)

(8)

Sincey_i→ f_i(y_i,xⁱ) is quasi concave onX_i,

f_iλz1+ (1−λ)z2,xⁱ≥δ_iA_ixⁱ,xⁱ. (4.6) But,Ai(xⁱ) is a convex set. So,

f_iλz1+ (1−λ)z2,xⁱ≤δ_iA_ixⁱ,xⁱ. (4.7) Therefore,

f_iλz1+ (1−λ)z2,xⁱ=δ_iA_ixⁱ,xⁱ. (4.8) Henceλz1+ (1−λ)z2∈E_i(xⁱ). Therefore,E_i(xⁱ) is convex for eachi₌1,. . .,n.

Next, it is shown thatE_i:Xⁱ→2^Yⁱ is upper semicontinuous multifunction onX_i, for everyi=1,. . .,n.

Letzn∈Xⁱwithzn→zandwn∈Ei(zn) withwn→w.

The factw_n∈E_i(z_n) implies the fact that f_i(w_n,z_n)=δ_i(A_i(z_n),z_n). ByLemma 4.1, xⁱ→δi(Ai(xⁱ),xⁱ) is a continuous function. Therefore,δi(Ai(zn),zn)→δi(Ai(z),z). More- over, since fi is a continuous function, fi(wn,zn)→ fi(w,z). This implies that fi(w,z)= δ_i(A_i(z),z). Hencew∈E_i(z). ThereforeE_iis upper semicontinuous onX_ifor everyi= 1,. . .,n. Hence this establishes the claim thatEi∈᏷(Xⁱ,Yi), fori=1,. . .,n. Further from the above claim, it follows thatE∈᏷(X,Y).

Now, letx∈X0 and y∈E(x). This implies that f_i(y_i,xⁱ)=δ(A_i(xⁱ),xⁱ), i=1,. . .,n.

Since fifori=1,. . .,nsatisfy condition (A) with respect to the multifunctionsAi, there existsa∈Xsuch thata−y =d(X,Y). This illustrates the facty∈Y0. ThereforeE(X0)

⊆Y0. HenceEsatisfies all the conditions ofTheorem 3.4. Therefore, there existsx∈X such that

d(x,Ex)=d(X,Y). (4.9)

SinceExis compact, there existsy∈Exsuch that

d(x,y)=d(X,Y). (4.10)

This establishes the theorem.

If the setsYi’s coincides withXi’s fori=1,. . .,n, thenY=Xand the following corollary is immediate.

Corollary4.5. LetX1,. . .,X_nbe nonempty compact convex sets in a normed linear spaceF.

LetAi:Xⁱ→2^Xⁱ,i=1,. . .,n, be lower semicontinuous multifunctions in᏷(Xⁱ,Xi). Fori= 1,. . .,n, let fi:X→Rbe continuous functions such that, for any fixedxⁱ∈Xi, the function y_i→ f_i(y_i,xⁱ)is quasiconcave onX_ifor eachi=1,. . .,n. Then there exists an equilibrium point for the game in the sense of Debreu[1].

Remark 4.6. It is remarked thatTheorem 4.4does not strictly generalize Debreu’s theorem [1] or [5, Theorem 6]. In [5] the setsXi’s are convex sets with all the multifunctions A_i’s compact except possibly one in addition to the conditions forA_i’s given in the above corollary.

(9)

References

[1] G. Debreu,A social equilibrium existence theorem, Proc. Nat. Acad. Sci. USA38(1952), 886–

893.

[2] X. P. Ding and K.-K. Tan,On equilibria of noncompact generalized games, J. Math. Anal. Appl.

177(1993), no. 1, 226–238.

[3] K. Fan,Extensions of two fixed point theorems of F. E. Browder, Math. Z.112(1969), 234–240.

[4] C. Ionescu Tulcea,On the approximation of upper semi-continuous correspondences and the equi- libriums of generalized games, J. Math. Anal. Appl.136(1988), no. 1, 267–289.

[5] M. Lassonde,Fixed points for Kakutani factorizable multifunctions, J. Math. Anal. Appl.152 (1990), no. 1, 46–60.

[6] J. F. Nash Jr.,Equilibrium points inn-person games, Proc. Nat. Acad. Sci. U.S.A.36(1950), 48–

49.

[7] J. B. Prolla,Fixed-point theorems for set-valued mappings and existence of best approximants, Numer. Funct. Anal. Optim.5(1982/1983), no. 4, 449–455.

[8] S. Sadiq Basha and P. Veeramani,Best proximity pairs and best approximations, Acta Sci. Math.

(Szeged)63(1997), no. 1-2, 289–300.

[9] ,Best proximity pair theorems for multifunctions with open fibres, J. Approx. Theory103 (2000), no. 1, 119–129.

[10] V. M. Sehgal and S. P. Singh,On random approximations and a random fixed point theorem for set valued mappings, Proc. Amer. Math. Soc.95(1985), no. 1, 91–94.

[11] ,A generalization to multifunctions of Fan’s best approximation theorem, Proc. Amer.

Math. Soc.102(1988), no. 3, 534–537.

[12] P. S. Srinivasan and P. Veeramani,On best proximity pair theorems and fixed-point theorems, Abstr. Appl. Anal.2003(2003), no. 1, 33–47.

[13] K.-K. Tan and X.-Z. Yuan,Approximation method and equilibria of abstract economies, Proc.

Amer. Math. Soc.122(1994), no. 2, 503–510.

[14] V. Vetrivel, P. Veeramani, and P. Bhattacharyya,Some extensions of Fan’s best approximation theorem, Numer. Funct. Anal. Optim.13(1992), no. 3-4, 397–402.

[15] G. X.-Z. Yuan,The study of minimax inequalities and applications to economies and variational inequalities, Mem. Amer. Math. Soc.132(1998), no. 625, x+140.

P. S. Srinivasan: Department of Mathematics, Indian Institute of Technology, Madras, Chennai 600 036, India

Current address: Department of Mathematics and Statistics, University of Hyderabad, Hyderabad 500 046, India

E-mail address:[email protected]

P. Veeramani: Department of Mathematics, Indian Institute of Technology, Madras, Chennai 600 036, India

E-mail address:[email protected]