AN OBSERVATION ABOUT AUMANN CORRELATED EQUILIBRIA POINTS By Ezio Marchi and Martín Matons IMA Preprint Series #2426 (June 2014) INSTITUTE FOR MATHEMATICS AND ITS APPLICATIONS UNIVERSITY OF MINNESOTA 400 Lind Hall 207 Church Street S.E. Minneapolis, Minnesota 55455-0436 Phone: 612-624-6066 Fax: 612-626-7370 URL: http://www.ima.umn.edu An Observation About Aumann Correlated Equilibria Points by Ezio Marchi IMASL - Universidad Nacional de San Luis San Luis, Argentina emarchi@speedy.com.ar Martín Matons Universidad Tecnológica Nacional, Facultad Regional Mendoza Mendoza, Argentina mmatons@unsl.edu.ar Abstract: in this paper we study the conditions for which an Aumann equilibrium point is also a Nash point in the original game. Key words: Aumann equilibrium point, Nash equilibrium point, fiber. Comments with related topics The correlated strategies have been used in some earliest contributions as for example in Luce and all. On the other hand Marchi in [3] in the year 1969 consider and study the generalization of the minimax theorem in zero sum two person game. This was obtained in successful way by studying exhaustly the fiber bundle that appeared in the relation of the product of probabilities and the joint probability set. This is performed with a natural embedding. In this paper the mathematics is rather complicated for the requirements of the equations. Hence we use the term cooperative strategy rather than the correlated strategies. The paper with the only example of two strategies of 221  with different payoff or the two players is more simple that the just remarked. Here we found a very important feature without the concrete study of the fiber bundle and its study the fiber in each point. This is summarized in the fundamental inequalities (3). The dimension of the fiber is just the number of free sz´ . The paper just mentioned was generalized only for the probability aspect in Marchi [4] in the year 1972. No relation with the game is considered. Introduction In this note we are concerning with same aspects of game theory of n-players. As it is very well know in the non cooperative games the main concept introduced as solution is the equilibrium point of Nash [6]. In two elegant proofs besides the introduction he proved the existence of an equilibrium points in the mixed extension of a finite n-person games. After some years Aumann introduced the strong equilibria for correlated points, but he was very successful with the correlated equilibrium n-person non-cooperative games. We need the following concepts in order to present the new correlated equilibria. Let  2,1N  be the set of players and for each player  2,1i , i is the set non empty set of pure strategies that for our purpose 2i  . Consider the set   j1221 j,i,j,iz/z  and the set of all joint probability             j,i 4 21 1j,iz,0j,iz/z This set has a very strong relation with the set of product probabilities of the finite sets 1 and 2 :               21 ji 4 21 1jy,1ix,0jy,0ix/y,x This relationship might be viewed in the paper by Marchi [] where is exhaustive studied such subject for low dimension. For completeness and help for the reader we remember the Nash equilibrium concept. For completeness and help for the reader we remember the Nash equilibrium concept. We indicate the game by  Ni,A, ii  , where 1A and 2A  21: are the pure payoff functions, then the mixed extension is given by  Ni,E, ii  , where iE , for each I, is the simple expectation function defined as          2 1j,i kk jyixj,iAy,xE for 2,1k  . A Nash point is a 2-tupla of vectors y,x such that     111 xy,xEy,xE  (1)     222 yy,xEy,xE  Now in general an Aumann correlated equilibria point is a point llz  such that             0,A,A,z iiNiiiNiiiN liliN       , iii ,  , where i and i are pure strategies of player Ni . This was introduced by Aumann in 1974. The meaning of it was also given by Aumann as a recommendation by a referee to each player obtaining an optimum without to abide by it. A first formal proof was provided by Hart-Smeidlher [2] in 1989, with an elegant proof using new results in two person zero sum game. At this point we must to emphasize that an Aumann correlated equilibrium is Nash in pure strategies in the following game  Ni,B, 2ii2  where          iiNiiiNi2i ,A,zB iN       which is not the original. We now wish to compute in general the Aumann correlated equilibrium. The set of all correlated equilibria is a non-empty compact and convex polyhedron. Consider  2,1N  then the equations defining the Aumann correlated equilibrium with  j,iAa 1ij  ,  j,iAb 2ij  and   ijzj,iz  are     0aazaaz 221212211111  1i      0aazaaz 122222112121  2i      0bbzbbz 222121121111  1j  (2)     0bbzbbz 212222111212  2j  Now we will consider a rather important feature: when a correlated equilibrium of Aumann projects in a natural way in a Nash point in the original game. The first case that we analyze is when the Nash equilibrium is in both players completely mixed. Then from (1) and a standard form:        y,xEy,2Ey,1Ey,xE 1111  x        y,xE2,xE1,xEy,xE 1222  y or    y1ayay1aya 22122111  from here we obtain A 2212 21122211 2212 aa aaaa aa y       On the other hand the z´s, x´s and y´s are related by a natural projection, namely yzz 1211  y1zz 2221  xzz 2111  (3) x1zz 1222  or 1112 zyz  1121 zxz  1122 zyx1z  Now since  22211211 z,z,z,zz  ,  x1,x  and  y1,y  are probability vectors then 1zyz0 1112  1zxz0 1121  1zyx1z0 1122  which implies yz11  xz11  1yxz11  or  y,xminz1yx 11  (4) From (2) we obtain the four inequalities 11 2212 1221 12 z aa aa z    and the numerators and the denominators both positives or both negative 11 2221 1112 1222 2111 21 1222 2111 22 z bb bb aa aa z aa aa z         11 2212 1221 2122 1221 12 2122 1221 22 z aa aa bb bb z bb bb z         We realize that the last inequalities are the same. Now replacing from the first and the second term of (3) into the first and third inequalities of (2) we obtain 11 2221 1112 21 z bb bb z       2 A 21221222 A 1222 11 aaaa y aa z       and for the remaining equations    2 B 21221222 11 bbbb z    or summarizing                       1 bbaa , bbbb , aaaa max B 1222 A 2122 2 B 21221222 2 A 21221222  11z           A 2122 B 1222 aa, bb min . And in this way we obtain the following important result: if we have a completely mixed Nash and it comes from any Aumann correlated equilibrium fulfilling (5) then it projects to the given Nash. Now we present an example fulfilling all the requirements. Take A and B positive then 0aaaa 21122211A  , then 2122 aa  has to be non negative. The same for 0bbbb 21122211B  , therefore it must be 0bb 1222  . From the previous considerations, we have 12122 aa  with 01  . Then 22122111 aaaa  112a  . From (5) one of the terms A 2122 B 1222 aa, bb     must be less to one since they are assumed mixed equilibrium points. For simplicity we take both terms less than one. From this remark besides we must have that    A 2122 2 A 21221222 aaaaaa      then 1 aa A 1222    or 12111 aa  with 01  . Similarly for the second player we obtain 0bbbb 21122211  , 21222 bb  with 02  , 21211 bb  and finally 21211 bb  with 02  . It is important to realize that in (5) we have considered the comparison among the analogous terms in the minimum and maximum. On the other hand, we must to consider the cross inequalities as follows    A 2122 2 B 21221222 aabbbb      and    B 1222 2 A 21221222 bbaaaa      operating from the previous one, we gets    BA21221222 bbaa  or   2 1 B2212 aa    and from the second inequality we get    BA21221222 bbaa  or   1 2 A2212 bb    . As a numerical example we present the following payoff matrices        3,15,1 21 A and        15,1 31 B then we get 07,0A  , 05,2B  , 1aa 2122  , 2bb 1222  , 2,0aa 1211  , 5,0bb 2111  , 5,0aa 2111  and 5,0bb 1211  . In order to give an exhaustive explanation of the whole topics we present the computation of the completely mixed Nash equilibrium, considering    y,2Ey,1E 11  and    2,xE1,xE 22  from here we get 5 4x  and 6 5y  , then  y,xminz1yx 11         6 5 , 5 4 minz1 6 5 5 4 11 8,0z63,0 11  and therefore for the extreme 30 1963,0z11  we get 6 1z21  , 5 1z12  and 0z22  , when we consider 5 4z11  we get 0z21  , 30 1z12  and 6 1z22  . In this way we have proved that for all 11z such that 8,0z63,0 11  the Aumann correlated equilibrium points project to the Nash   6 5, 5 4 . The case where the Nash point is not completely mixed is much easier that the just study. Comments As we have mention in the text, we point out that the first exact introduction explicit computations of correlated point were presented by Marchi in [3]. Here it was extended the minimax theorem when we take into account correlated strategies. In such a contribution besides of the minimax theory it was studied the natural fiber bundle of the relationships among the product of mixed probabilities with the joint strategies. In the way that we found in this contribution, the need of study the faces and extreme points of the fibers is immediately given by considering the inequality  y,xminz1yx 11  . In general in Marchi [3] it was extended the just fiber bundle for arbitrary dimension and axes and in Marchi and Morillas [5] in functional analysis. We make very clear that the notion of correlated equilibrium points in general was first introduced in the literature by Aumann in [1] and proved rigorously mathematically by Hart – Schmeidler in [2]. In similar way as we studied here it is possible to analyse the posteriorly introduced coarse equilibrium points. Acknowledgments We thank the Facultad de Ciencias Físico, Matemáticas y Naturales de la Universidad Nacional de San Luis for financial support. The first author thanks the National Science Foundation for supporting him in a stay at the IMA. Bibliography [1] Aumann, R. J. (1974), “Subjectivity and Correlation in Randomized Strategies”, Journal of Mathematical Economics 1, 67-95. [2] Hart, S. and Schmeidler, D. (1986), “Correlated Equilibria: an elementary proof existence”, [3] Marchi, E. (1969), “On the possibility of an unusual extension of the minimax Theorem”. Zeitschr Wahrscheinlichkeitstheorie Wrw. Gebiete. Vol. 12, 223-230. [4] Marchi, E. (1972), “The natural vector bundle of the set of product probability”. [5] Marchi, E. and Morillas P. (2005), “The natural vector bundle of the set of multivariate density function”. Journal of Math. Proyecciones, Vol 24 nº 3, 239-255 [6] Luce, R. D. and Raiffa H. (1957), “Games and Decision”. New York. [7] Luce, R. D. (1954), “A definition of stability for n-person games”. Annals of Mathematics 59, 357-366. [8] Nash, J. F. (1951), “Non-cooperative games”. Ann. Math. 54, 286-295.