Nash Equilibrium - Assignment Example

Task “Proving Nash Equilibrium” Introduction Nash equilibrium is a primary idea in the theory of games and the most extensively usedmethod of forecasting the result of a premeditated communication in the social sciences. A game (in strategic or normal form) has three components, which includes a set of players, a set of actions accessible to each player, and a payoff (or utility) function for each player. The payoff functions stand for each player’s favourite over action profiles. An action profile is a list of actions, one for each player (Implementation in Undominated Nash Equilibria Without Integer Games, 39). Pure-strategy Nash equilibrium is an action profile with the feature that no single player can attain a higher pay off by conflicting unilaterally from this profile Proving the existence of Nash equilibrium The essence of this process of proving is to ascertain that every game has at least Nash equilibrium. We consider the following definitions and respective explanations. Definition 1: Convexity A set C ⊂Rm is said to be convex if for every x, y ∈C and λ∈[0,1], λx+ (1−λ) y ∈ C. For the vectors x...x and the non-negative scalars λ0. . . λn satisfying Pni=0 λi= 1, the vector Pni=0λixi is called a convex combination of x0. . . xn (Implementation in Undominated Nash Equilibria Without Integer Games, 40). Definition 2: Affine Independence A finite set of vectors {x0. . . Xn} in a Eu-clidean, space is affinely independent If Sum from o to n of λixi= 0 and summation of λi =0, this implies that λi =0 =... and λi=0. On a similar regard, we can consider an equivalent condition, which is represented by {x1−x0 x2−x0. . . xn−x0}, which are linearly dependent . Intuitively, a set of points is affinely independent if no 2 points from the set lie on the same line, for four points from the set points. Definition 3: Simplex For the case of n-simplex, denoted by x0.....xn is the set of all the convex combinations of the affinely independent set of vectors.  : ∀i∈ {0 . . . n}, λ≥0; and  =1 Each xi is referred to as a vertex of the simplex xo...xn and each K simplex xio......xik is called a K-face of x0 .................xn Where i0 .......ik ∈{0,.....n}(Implementation in Undominated Nash Equilibria Without Integer Games, 45). Definition 4: Standard n-simplex The standard n-simplex n is {y∈ R n+1:  = 1, ∀i= 0 ...n, ≥0}. Similarly, the Standard n-simplex is the set of all convex combinations of n+1 units e0 ......en Definition 5: Simplicial subdivision The simplicial subdivision of an n-simplex T represents a finite set of simplexes {Ti} For which UTi∈TTi =T For any Ti, Tj ∈ T, Ti ⋂ Tj This is either equal to a common face or empty Naturally, this implies that a simplex is divided into a set of diminutive simplexes which jointly occupy exactly the same area of space and which overlap only on their confines. In addition, when two of the simplexes overlie, the intersection should be a complete face of both sub-simplexes (Implementation in Undominated Nash Equilibria Without Integer Games, 45). Let y∈x0 ......xn signify an arbitrary point in a simplex. This point can be represented as a convex combination of the apexes: y=. A function that defines a set of vertices involved in this point can be written as X(y) = {i: hi>0}. This function is applied in defining proper labeling. Definition 5: Proper labeling We let T = x0.....xn to be subdivided simplicially, and let V signify the set of all distinctive of a subdivision if L (V) ∈X(v). One effect of this definition is that the vertices of simplex should all receive diverse labels. Definition 6: Sperner’s lemma We let Tn =x0.....xn to be simplificially subdivided. We let L be a proper labelling of the subdivision. Then there exist an odd number of completely labelled sub-simplexes in the subdivision (Implementation in Undominated Nash Equilibria Without Integer Games, 43). Proof We prove this system by induction on n. The case n=0 is inconsequential. The simplex comprises of single point x0. The only probable simplicial subdivision is {x0}. This follows that, there is only one probable labelling function, L(x0) =0. It is notable that, this is a proper labeling. Hence there is one completely labeled sub simplex, x0 itself. We can presume the statement to be true for n-1 and go ahead prove it for n. The simplicial sub-division of Tn encourages a simplicial subdivision on its face x0 .....xn-1. This face is a (n-1) simplex, which is signified as Tn-1 We can say that the labeling function L restrained to Tn-1 is a proper labeling of Tn-1. This Implies that by induction hypothesis, an odd number of (n-1) sub-simplexes in Tn-1 exist. It bears the labels. At this point, the rules of walking across the subdivided labeled simplex Tn are defined as follows. The walk commences at an (n-1) sub-simplex with labels (0 ...n-1) on the face Tn-1: which we call sub simplex b. This follows that a unique n-sub simplex d, which has b as a face, exists. On equal measure the ds’ vertices comprises of the vertices of b and the apex z. In case, z is labeled n, then a completely labeled sub simplex and the walk ends (Implementation in Undominated Nash Equilibria Without Integer Games, 44). If not, d has the labels (0...n-1), where one of the labels (say j) is repeated, and the label n is missing. In this case, there exists precisely one other (n-1) sub simplex, which is a face of d and bears the labels (0...n-1). The reason for this is that all except one of d’s apexes define each (n-1) face of d, because only apex j is repeated, and label n is absent. In this scenario, another perfectly (n-1) sub-simplex which is a face of d and bears the labels (0,....n-1) on condition that one of the two apexes bearing j is avoided. Since we are aware that b is one such face, then we also understand that a perfectly one other face called e exists. This follows that the lebeling is either complete or has exactly one other apex with labels (0, 1). The walk continues from e. The following property is applied For an (n-1) face of an n- sub-simplex in a simplicialy sub-divided simplex Tn is either on an (n-1) face of Tn, or the intersection of the 2 n-sub-simplexes. If e is on an (n-1) face of Tn, the walk should stop. If not, the walk should continue into the unique other n-sub-simplex with e as a face. We realize that, this simplex is either completely labeled or it has one recurring label, hence the walk continues the same way as in sub-simplex d (Implementation in Undominated Nash Equilibria Without Integer Games, 44). It is notable that the walk is completely established by the starting (n-1) sub-simplex. The walk comes to an end either completely labeled n-sub-simplex, or an (n-1) sub-simplex with attributed labels of (0,....n-1) on the face Tn-1. It is imperative to note that the walk cannot end on any other face, since L is a proper labeling. If we commence from the end of the walk by using the above-described guideline we will end up at the beginning point. This means that if a walk begins at t on Tn-1 and ends at t’ on Tn-1, however it should be noted that, t and t’ are different. On other hand, if the t and t’ are the same, the walk will be reversed and a different path with the same commencing point will exist and this will contradict the uniqueness of the walk (Implementation in Undominated Nash Equilibria Without Integer Games, 45). It should be noted that, not all completely labeled sub-simplexes, because there is precisely one (n-1) simplex face labeled (0 ...n-1) for a walk to come in from a completely labeled sub-simplex. This follows that, the sum of the completely labeled sub simplexes is odd. Definition 7: Compactness A sub set of R is compact on condition that the set is closed and bounded. It is easy to verify that m is compact. A compact set has each of its sequence having a convergent subsequence (Nash, 54). Definition 8: Centroid The centroid of a simplex xo.... xm is given by the average of its centroid apexes. Consider the Following formula 1/M+1  0xi At this point, the sperner’s lemma can be used to prove Brouwer’s fixed-point theorem Theorem: Brouwer’s fixed-point theorem We let f: m m to be continuous. This implies that f has a fixed point and this we can conclude that a point z exists, z ∈ m such that f (z) =z. It is imperative to note that the Brouwer’s fixed-point theorem cannot be applied to prove the existence of Nash equilibrium in a direct way, because Nash equilibrium is a point in the set of assorted strategy profiles of S. The set is simlotope and not simplex. It represents a Cartesian plane of simplexes. Notably, the Brouwer theorem can be adjusted to fit into the simplotopes (Nash, 54). The reason for this adjustment is each simplotope’s topological similarity with the simplex. This brings us to the Brouwer’s fixed-point theorem, simplotopes. Corollary 9: Brouwer’s fixed point theorem, simplotopes We let K=  mj be a simplotope Then let f: K K be continuous We show that K is homeomorphic to Then we have a fixed point at f. mj. The process of adjusting the Brouwer’s fixed-point theorem is called radial projection from the square simplotope to a triangle. This process is shown in the diagram below Simplex simplex x1 Simplotope hhhhh x1 The above illustration indicates the process of the converting a simplex into a simplotope. The square represents a product of two standard 1-simplexes, then the square undergoes scaling and then inserted into the triangle, which represents a 2-simplex. This is an example of radial projection h (Nash, 51). The final process is to show that h is homeomorphism. Verification of h as being continuous is easy and straightforward. We know that h (x) lies on the ray which begins at a and passes through x, provided h(x) we can build up a similar ray by drawing a ray that begins at a and passes through h(x). Recovering of x’ and x” follows and then finding of x through scaling h(x) along the same ray by using a factor of x” –a/x’-1 Thus h is injective and given any point y ∈ m’ a ray can be constructed and the value of x found. This follows that h is homeomorphism. This far brings us to the fundamental prove of the existence of Nash equilibrium. With corollary 9 and relevant notations for discussing mixed strategies, the proof proceeds to the constructing of a continuous f: S S so that each fixed point of f is a Nash equilibrium. Corollary 9 is applied to argue that f has at least one fixed point consequently existence of the Nash equilibrium (Nash, 52). Definition 10: Nash 1951 There is at least one Nash equilibrium in every game with a finite number of players and action profiles. We consider the following proof Proof Given a strategy profile s S, for all i ∈ N and ai, we can define  = Max {0, ui (ai, S-i) – ui (S)} This follos the definition of the function f: S S by f (s) =s’, where S’i (ai) = si (ai) +   + = Si (ai) + 1+ Instinctively, this function mirrors a strategy profile s to a new strategy profile s’. In this case, each agent’s actions, which are enhanced rejoinder to s, receive increased likelihood mass. Since, is continuous, it follows that the function f is continuous. f must have at least one fixed point since S is convex and compact and f: S S, by corollary 10 (Nash, 56). Hence, we show that the fixed points of f are Nash equilibrium. If s is a Nash equilibrium then all. This makes s a fixed point of f. Equally, considering the an arbitrary fixed point f in the support of s, take for instance, ai, for which ui ai ‘(s) ≤ ui (s) From the definition of   =0 S is fixed point of f, si’ (a’i) We consider the expression defining si’ (a’i) We find the numerator simplifies down to si’ (a’i), which is positive due to a’i’s dependence on i. This follows that the denominator is 1. This implies that for any i and bi ∈ Ai,  =0 Considering the definition of  , this process can only happen when no single player can enhance his anticipated payoff by moving to a pure strategy. Hence, s is Nash equilibrium (Nash, 58) Work cited The Income Tax Treatment of Married Couples and Single Persons: A Report. Washington: U.S. Govt. Print Off, 1980. Print. Read More