# Brouwer fixed point theorem and applications.

Introduction

Definition:

Let X be a non-empty set, R be a set of real numbers, a metric on X is real-valued functions: d: X x X R--

Such for all x, y [member of] X, the following axioms are satisfied.

Axiom 1: d(x, y) [greater than or equal to] 0

Axiom 2:d(x,y) = 0 iffx=y

Axiom 3:d(x, y) = d(y, x)

Axiom 4:d(x, y) [less than or equal to] d(x, z)+d(z, y)

Brouwer Fixed Point Theorem

Introduction

Having defined the concept of metrics, we will now consider its special application; Brouwer Fixed Point Theorem. But firstly, let's give a brief definition of fixed point and fixed point property.

Fixed Point

If f: X [right arrow] X is a mapping from X into X, then X is called a fixed point of f if and only if f(X) =X. Another definition of fixed point says that if g is a continuous function, g(x) [member of] [a, b] for all x [member of] [a, b], then g has a fixed point in [a, b]. This can be proven by supposing that g (a) [greater than or equal to] a and g(b) [less than or equal to] b

that is (a [greater than or equal to] [a, b] [less than or equal to] b )

= g (a) - a [greater than or equal to] a and g(b) - b [greater than or equal to] 0

Since g is continuous, the intermediate value theorem guarantees that there exist c [member of] [a, b] such that

g(c) - c =0

so there must exist a 'c' such that g(c) = c

This means that there must exist a fixed point [member of] [a, b]

Example 2.1

Let T(y) = [y.sup.11] + 2[y.sup.1] - 7y be an ordinary differential equation. We will simply obtain the fixed point of this operator by solving the Equation above.

Let T(y) = [y.sup.11]+ 2[y.sup.1] - 7y

Therefore T(y) =y is the fixed point.

[Y.sup.11]+2[y.sup.1] - 7y = y

[Y.sup.11]+2[y.sup.1]-8y = 0

This is a homogenous Second order differential Equation, hence the characteristic equation is

[M.sup.2] + 2M - 8 =0

Where m = characteristic root

[M.sup.2] + 4M -2M - 8 = 0

M (M +4) - 2 (M + 4) =0

(M + 4) (M -2) = 0

Therefore M = -4 or M = 2

Assuming that y = [e.sup.mx]

[y.sub.1] = [e.sup.-4x], [y.sub.2] = [e.sup.2x]

Where T([y.sub.1]) = [e.sup.-4x] T([y.sub.2]) = [e.sup.2x]

Hence, the fixed point of the operator is Y = [e.sup.2x] and [e.sup.-4x] where x [member of] [a,b].

Fixed Piont Property

A topological space X has the fixed point property if all continuous mappings from X to X has a fixed point.

Example 2.2

The Closed interval [0, 1] has the fixed point property. Lat F: [0, 1] [0, 1] be a mapping. If f (0) = 0 or f (1) = 1, then our mapping has a fixed point at 0 or 1. If not, then f (0) > 0 and f (1) - 1<0. Thus, the function g(x) = f(x) - x is a continuous real--valued function which is positive at x =0 and negative at x = 1. By the Intermediate value theorem, there is some point [x.sub.0] with g ([x.sub.0]) = 0, which is to say that f ([x.sub.0] ) - [x.sub.0] = 0 and so, [x.sub.0] is a fixed point. Also, the open interval does not have the fixed point property.

Brouwer Fixed Point Theorem

Every Continuous function from the closed unit ball [D.sup.n] to itself has at least one fixed point.

Proof of Brouwer Fixed Piont Theorem

The proof uses the observation that the boundary of [D.sup.n] is [S.sup.n-1] and (n-1) is a sphere.

[ILLUSTRATION OMITTED]

The argument proceeds by Contradiction, supposing that a continuous function; f : [D.sup.n] [right arrow] [D.sup.n]

has no fixed point and then attempting to derive an inconsistency which proves that the function must infact have a fixed point.

For each x in [D.sup.n], there is only one straight line that passes through f(x) and x, because it must be the case that f(x) and x are distinct. By hypothesis (recall that f has no fixed point means f(x) # x)

Following this line from f (x) through x leads to a point on [S.sup.n-1] denoted by F(x). This defines a continuous function as Retraction: Every point of the co-domain (in this case [S.sup.n-1] ) is a fixed point of the function.

Intuitively, it seems unlikely that there could be a Retraction of [D.sup.n] onto [S.sup.n-1] and in this case n=1, it is

obviously impossible because [S.sup.0] (that is the endpoints of the closed interval [D.sup.1] ) is not evenly connected. The case n = 2 can also be proven by contradiction based on a theorem about non-vanishing vector fields.

Example 2.3

Suppose f is a continuous function f: [0,1] [right arrow] [0,1]. Then f has a fixed point; that is a 'x' such that f(x)=x,

Proof

We can assume that f (-1) > -1 and f (+1) < 1, since otherwise, there is nothing to prove. Then, consider the function g: [-1, 1] [right arrow] R, defined by g(x) = f(x) - x.

g ( 1 ) < 0, g( -1) >0 from g:[-1,1] [right arrow] RSo,

by Intermediate Value theorem, there is a point 'x' such that g(x)=0 that is f(x) =x.

Application of Brouwer Fixed Piont Theorem

Proof of Existence of Nash Equilibrium

In Economics, where there two Corporations selling the same product, there is an Equilibrium, if each player's strategy is the best he or she can choose, given the other player's chosen strategy. This definition of Equilibrium is called a Nash Equilibrium after the noble Laureate, John Nash. A more elaborate example can be made using a case called the prisoner's Dilemma. The Prisoner's Dilemma is a class of situations in which there are potential gains from Co-operation and yet it is in the private interest of each party to behave selfishly. But, where the parties know one another's identity and may be engaging in repeated interaction or plays of the game, they may be able to achieve a more co-operative outcome.

B'S CHOICE OF STRATEGY ( IN YEARS ) Confess Do not confess

A'S CHOICE OF STRATEGY Confess Do not confess

Formal Definition

Let (S, f) be a game, where [S.sub.i] is the strategy [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] set for player i, S=[S.sub.i] X [S.sub.2] ... X [S.sub.n] is the set of

strategy profiles and f= (f1(x) ... [f.sub.n](x)) is the payoff function. Let x i be a strategy profile of all players except for player i. When each player i [member of] {1 ... n} chooses strategy [x.sub.i] resulting in strategy profile x = ([x.sub.1] ... [x.sub.n]) then player i obtains payoff [f.sub.i](x). Note that the payoff depends on the strategy profile chosen, i.e. on the strategy chosen by player i as well as the strategies chosen by all the other players. A strategy profile [x.sup.*] [member of] S is a Nash equilibrium (NE) if no unilateral deviation in strategy by any single player is profitable for that player, that is

[for all]i, [x.sub.i] [member of][S.sub.i], [x.sub.i] [not equal to] [x.sup.*.sub.i]: [f.sub.i]([x.sup.*.sub.i], [x.sup.*.sub.-i] [greater than or equal to] [f.sub.i]([x.sub.i], [x.sup.*.sub.-i]).

We have a game G = {N,A,u) where N is the number of players and A = [A.sub.1] x ... x [A.sub.N] is the action set for the

players. All of the actions sets [A.sub.i] are finite. Let [DELTA] = [[DELTA].sub.1] x ... x [A.sub.N] denote the set of mixed strategies for the players. The finiteness of the [A.sub.i]s insures the compactness of [DELTA].

We can now define the gain functions. For a mixed strategy [sigma] [member of] [DELTA], we let the gain for player i on action [alpha] [member of] [A.sub.i] be

[Gain.sub.i]([sigma],a) = max{0,[u.sub.i]([a.sub.i],[[sigma].sub.-i]) - [[mu].sub.i]([[sigma].sub.i],[[sigma].sub.-i])}

The gain function represents the benefit a player gets by unilaterally changing his strategy. We now define g = ([g.sub.1], ..., [g.sub.N]) where

[g.sub.i]([sigma])(a) = [[sigma].sub.i](a) + [Gain.sub.i]([sigma],a)

for [sigma] [member of] [DELTA], a [member of] [A.sub.i]. We see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We now use g to define f : [DELTA] [right arrow] [DELTA] as follows. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for [alpha] [member of] [A.sub.i], We can see that each [f.sub.i] is a continuous function of [sigma], and hence f is a continuous function. Now [DELTA]

is the cross product of a finite number of compact convex sets, and so we get that [DELTA] is also compact and convex. Therefore we may apply the Brouwer fixed point theorem to f. So f has a fixed point in [DELTA], call it [[sigma].sup.*].

I claim that [[sigma].sup.*] is a Nash Equilibrium in G. For this purpose, it suffices to show that

[for all]1 [less than or equal to] i [less than or equal to] N, [for all]a [member of] [A.sub.i], [Gain.sub.i]([[sigma].sup.*], a) = 0.

This simply states the each player gains no benefit by unilaterally changing his strategy which is exactly the necessary condition for being a Nash Equilibrium.

Now assume that the gains are not all zero. Therefore, [there exists]i, 1 < i < N, and a [member of] [A.sub.i], such that [Gain.sub.i]([[sigma].sup.*],a) > 0. Note then that

[summation over (a [member of] [A.sub.i])] [g.sub.i]([[sigma].sup*], a) = 1 + [summation over (a [member of] [A.sub.i])] [Gain.sub.i] ([[sigma].sup.*], a) > 1

So let C = [summation over (a [member of] [A.sub.i] [g.sub.i]([[sigma].sup.*], a))]. Also we shall denote Gain{i,x) as the gain vector indexed by actions in

[A.sub.i]. Since f([[sigma].sup.*] ) = [[sigma].sup.*] we clearly have that fi([[sigma].sup.*] = [[sigma].sup.*.sub.i]. Therefore we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since C > 1 we have [[sigma].sup.*.sub.i] that is some positive scaling of the vector [Gain.sub.i]([[sigma].sup.*], x). now I claim that

[[sigma].sup.*.sub.i](a)([u.sub.i]([a.sub.i],[[sigma].sup.*.sub.-i) - [u.sub.i]([[sigma].sup.*.sub.i], [[sigma]*.sub.- i])) = [[sigma].sup*.sub.i](a)[Gain.sub.i]([[sigma].sup.*],a)

[for all]a [member of] [A.sub.i]. To see this, we first note that if [Gain.sub.i]([[sigma].sup.*],a) > 0 then this is true by definition of the gain function.

Now assume that [Gain.sub.i]([[sigma].sup.*],a) = 0. By our previous statements we have that

[[sigma].sup.*.sub.i](a) = (1/C - 1)[Gain.sub.i]([[sigma].sup.*],a) = 0

and so the left term is zero, giving us that the entire expression is 0 as needed. So we finally have that

= ([summation over (a [member of] [A.sub.i])][[sigma].sup.*.sub.i](a)[u.sub.i]([a.sub.i], [[sigma].sup.*.sub.-i])) - [u.sub.i]([[sigma].sup.*.sub.i], [[sigma].sup.*.sub.-i])

= ([summation over (a [member of] [A.sub.i])][[sigma].sup.*.sub.i](a)[u.sub.i]([a.sub.i], [[sigma].sup.*.sub.-i])) - [u.sub.i]([[sigma].sup.*.sub.i], [[sigma].sup.*.sub.-i]))

= [summation over (a [member of] [A.sub.i])] [[sigma].sup.*.sub.i] (a)[Gain.sub.i]([[sigma].sup.*]a) by the previous statements

= [summation over (a [member of] [A.sub.i])](C - 1)[[sigma].sup.*.sub.i][(a).sup.2] > 0

Where the last inequality follows since [[sigma].sub.i.sup.*] is a non- zero vector. But this is a clear contradiction, so all the gains must indeed be zero.

Therefore [[sigma].sup.*.sub.is] a Nash Equilibrium for G as needed.

Application to Linear Equations

Suppose that we have a system of n equations of n unknowns:

[g.sub.1]([x.sub.1], [x.sub.2], [x.sub.3],....,[x.sub.n]) = 0

[g.sub.2]([x.sub.1], [x.sub.2], [x.sub.3],...., [x.sub.n]) = 0

[g.sub.3]([x.sub.1], [x.sub.2], [x.sub.3],.... [x.sub.n]) = 0

[g.sub.n]([x.sub.1], [x.sub.2], [x.sub.3],.... [x.sub.n]) = 0

We also suppose that [g.sub.i], i = 1... n are continuous real-valued functions of the real variables [x.sub.1], [x.sub.2],...., [x.sub.n] An important problem is how solve the above system (if a such solution exists). To see how we can transform this problem into a fixed-point problem, we consider the following equations:

[k.sub.1]([x.sub.1], [x.sub.2], [x.sub.3] ... [x.sub.n]) = [g.sub.1]([x.sub.1], [x.sub.2], [x.sub.3] ... [x.sub.n]) + [x.sub.1]

[k.sub.2]([x.sub.1], [x.sub.2], [x.sub.3] ... [x.sub.n]) = [g.sub.2]([x.sub.1], [x.sub.2], [x.sub.3] ... [x.sub.n]) + [x.sub.2]

[k.sub.3]([x.sub.1], [x.sub.2], [x.sub.3]... [x.sub.n]) = [g.sub.3]([x.sub.1], [x.sub.2], [x.sub.3] ... [x.sub.n]) + [x.sub.3]

.

.

.

[K.sub.n]([x.sub.1], [x.sub.2], [x.sub.3],... ..., [x.sub.n]) = [g.sub.n]([x.sub.1], [x.sub.2], [x.sub.3],... ..., [x.sub.n]) + [x.sub.n]

Now, for any point x = ([x.sub.1], [x.sub.2], [x.sub.3],...., [sub.x][x.sub.n]), we define k(x) = ([k.sub.1](x) [k.sub.2](x),... ...,[k.sub.n](x)): n

The problem is to find a subset X of [E.sup.n] such that k(X) X. Indeed, if the above relation holds, then we can conclude the following:

By applying Brouwer's Theorem we can immediately speculate about the existence of a point x such that k(x) = x: (2)

Relation 2 is equivalent to the existence of x [member of] [E.sup.n] such that

k(x) = ([k.sub.1](x), [k.sub.2](x),...., [k.sub.n](x)) = ([x.sub.1], [x.sub.2], [x.sub.3], [x.sub.n]) (3)

Relation 3 is equivalent to the following relation:

([g.sub.1] (x) + [x.sub.1] [g.sub.2](x) +[x.sub.2],... ..., [g.sub.n](x) + [x.sub.n]) = ([x.sub.1], [x.sub.2], [x.sub.3], [x.sub.n]) (4)

But 4 is equivalent to:

[g.sub.1](x) = 0

[g.sub.2](x) = 0

[g.sub.3](x) = 0

.

.

[g.sub.n](x) = 0

or equivalently that the above system, 1 has a solution.

References

Dedron and Itard, 1974. Mathematics and Mathematicians I Transworld Publishers Ltd.

Franz, W., 1965. General Topology. George Harrap and Coy Ltd, London

Jameson, G.J.O., 1974. Topology and Normed Spaces. Chapman and hall, London

Kasriez, R.H., 1971. Undergraduate Topology. W.B.Saunders and coy, London

Kolmogorov and Fomin, 1967. Functional Analysis. Graylock Press, Rochester New York

Mendelson, B., 1975. Introduction to Topology. Allyn and Bacon, New York

Pervin, W.J., 1964. Foundations of General Topology. Academic Press, New York

Sinmons, G.F., 1963. Fundamentals of Topology. Macmillan Publishing coy. Inc., New York

Charles, E. Chidiume. (Functional Analysis (Fundamental Theorem with Applications) Longman Nigeria Limited, Lagos

Okereke, C. Emmanuel

Department of Mathematics/Statistics/Computer Science Michael Okpara University of Agriculture, Umudike, Abia State Nigeria.

Corresponding Author: Okereke, C. Emmanuel, Department of Mathematics/Statistics/Computer Science Michael Okpara University of Agriculture, Umudike, Abia State Nigeria.

E-mail: okereemm@yahoo.com
COPYRIGHT 2009 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Title Annotation: Printer friendly Cite/link Email Feedback Original Article Okereke, C. Emmanuel Advances in Natural and Applied Sciences Report 6NIGR Sep 1, 2009 2736 Minimizing the cost of hiring and training of stewardesses in the Nigerian airways using the simplex method of optimization. Ethnomedicinal applications of plants by the traditional healers of the Marma tribe of Naikhongchhari, Bandarban district, Bangladesh. Fixed point theory Metric spaces Nash equilibrium Systems of equations