(1区)(2015) Fixed point theorems in locally convex

A Simplicial Approach for DiscreteFixed Point Theorems(Extended Abstract)Xi Chen1and Xiaotie Deng2⋆1Department of Computer Science,Tsinghua Universityxichen00@2Department of Computer Science,City University of Hong Kongdeng@.hkAbstract.We present a new discretefixed point theorem based on anovel definition of direction-preserving maps over simplicial structures.We show that the result is more general and simpler than the two re-cent discretefixed point theorems by deriving both of them from ours.The simplicial approach applied in the development of the new theoremreveals a clear structural comparison with the classical approach for thecontinuous case.1IntroductionThere has recently been a sequence of works related tofixed point theorems in a discrete disguise,started with the seminal work of Iimura[12]which introduced a crucial concept of direction-preserving maps.Iimura,Murota and Tamura[13] corrected the proof of Iimura for the definition domains of the maps.With a different technique,Chen and Deng introduced another discretefixed point the-orem in order to achieve the optimal algorithmic bound forfinding a discrete fixed point for allfinite dimensions[1].In[14],Laan,Talman and Yang designed an iterative algorithm for the discrete zero point problem.Based on Sperner’s lemma which is fundamental for deriving Brouwer’sfixed point theorem,Friedl, Ivanyosy,Santha and Verhoeven defined the black-box Sperner problems.They √also obtained aon the simplicial structure in the study of the discrete version will help us gain a full and clear understanding of the mathematical structures and properties related to discretefixed point theorems.Furthermore,even for continuousfixed point theorems,discrete structural propositions are needed to derive them.Our study would provide a unified view of thefixed point theorem,both discrete and continuous,instead of treating them with ad hoc techniques.Our simplicial ap-proach unveils the mystery behind the recent results on discretefixed points and settles them under the same mathematical foundation as the classical continuous fixed point theorems.The discrete nature of thefixed point theorem has been noticed previously, mainly due to the proof techniques of Sperner’s lemma[15].The recent effort in direct formulation of the discrete version of thefixed point theorem would be especially useful in the complexity analysis of related problems.The recent work in characterizing the complexity of Nash Equilibria,by Daskalakis,Goldberg, Papadimitriou[8],Chen and Deng[2],Daskalakis and Papadimitriou[9],Chen and Deng[3],has been based on another innovative formulation of the2D(or 3D)discretefixed point problem,where afixed point is a collection of four[6] (or eight[8])corners of a unit square(or cube).It’s difficult to generalize such a formulation to high dimensional spaces,since a hypercube has an exponential number of corners,which is computationally infeasible.Instead,a simplicial de-finition has been necessary in extending those results to a non-approximability work obtained recently[9].Wefirst introduce notations and definitions with a review of previous works of Murota,Iimura and Tamura[13],as well as Chen and Deng[1].The simplicial model is then introduced in section3and the fundamental discretefixed point theorem is proved in section4.In section5,we present the discrete Brouwer’s fixed point theorem for simplicial direction-preserving maps,with the theorem of Murota,Iimura and Tamura[13]derived as a simple corollary.In Section6, we give an explicit explanation for the definition of bad cubes in[1]and show that,the theorem of Chen and Deng is a special case of the fundamentalfixed point theorem.Finally,we conclude in section7.2Preliminaries2.1Notations and DefinitionsInformally speaking,map F(or function f)is hypercubic direction-preserving on afinite set X⊂Z d if for every two neighboring points in X,their directions given by F(or f)are not opposite.The neighborhood relation considered here is defined by the infinity norm.Definition1(Hypercubic Direction-Preserving Maps)Let X be afinite subset of Z d.Map F from X to R d is said to be hypercubic direction-preserving on X if for every two points r1,r2∈X with||r1−r2||∞≤1,we have(F i(r1)−r1i)(F i(r2)−r2i)≥0,for all i:1≤i≤d.2Definition2(Hypercubic Direction-Preserving Functions)Let X be a finite subset of Z d.Function f from set X to{0,±e1,±e2...±e d−1,±e d}is said to be hypercubic direction-preserving if for every two points r1,r2∈X such that ||r1−r2||∞≤1,we have||f(r1)−f(r2)||∞≤1.Point r∈X is called afixed point of F(or f)if F(r)=r(or f(r)=0). 2.2The Fixed Point Theorem of Murota,Iimura and TamuraMurota,Iimura and Tamura proved in[13]that every hypercubic direction-pre-serving map from an integrally convex set X toX to denote the convex hull offinite set X⊂Z d.Definition3(Integrally Convex Sets)Finite set X⊂Z d is integrally con-vex if for all x∈X∩N(x)where N(x)={r∈Z d|||r−x||∞<1}.Theorem1([13])Let X be an integrally convex set in Z d,then every hyper-cubic direction-preserving map F from X to3Simplicial Direction-Preserving Maps and FunctionsIn this section,we introduce simplicial direction-preserving maps and functions based on simplicial structures.Let X be afinite set in R d.Here we only con-sider nondegenerate cases whereX such that for every S∈S,V S⊂X,where V S is the vertex set of simplex S.Given a simplicial decomposition S of X,we use F S to denote the set of (d−1)-simplices on the boundary ofX:F S={(d−1)-simplex S∈S|S⊂F and F is a facet ofX}.Definition8(Simplicial Direction-Preserving Maps)A simplicial direc-tion-preserving map is a triple M=(F,X,S).Here X is afinite set in R d and S is a simplicial decomposition of X.Map F from X to R d satisfies for every two points r1,r2∈X,if there exists a simplex S∈S such that r1,r2∈V S,then (F i(r1)−r1i)(F i(r2)−r2i)≥0,for all i:1≤i≤d.Definition9(Simplicial Direction-Preserving Functions)A triple G= (f,X,S)is said to be a simplicial direction-preserving function if X is afinite set in R d,S is a simplicial decomposition of X,and function f from set X to {0,±e1,...±e d}satisfies for every two points r1,r2∈X,if there exists S∈S such that r1,r2∈V S,then||f(r1)−f(r2)||∞≤1.In other words,for every two neighboring points in X,their directions given by map F(or function f)can’t be opposite.The only difference with the hy-percubic model is that the neighborhood relation is now defined by simplices in the simplicial decomposition S instead of unit d-cubes in Z d.4The Fundamental Discrete Fixed Point TheoremIn this section,we present the fundamental discretefixed point theorem which is both simple and powerful.Any simplicial direction-preserving function which satisfies the boundary condition of the theorem must have afixed point.Definition10(Bad Simplices)Let G=(f,X,S)be a simplicial direction-preserving function,where X⊂Z d.A t-simplex S∈S where0≤t≤d is said to be bad(relative to function G)if f(V S)={e1,e2,...e t+1},where V S is the vertex set of S.We use N G to denote the number of bad(d−1)-simplices in F S.4Lemma1For any simplicial direction-preserving function G=(f,X,S),if there exists nofixed point in X,then N G is even.Proof.Firstly,one can show that for every(d−1)-simplex S∈S,if S∈F S, then there exists exactly one d-simplex in S containing S.Otherwise,there are exactly two such ing this property,the parity of N G is same as the one of the following summation:d-simplex S d∈Sbad(d−1)-simplices in S d.As G is direction-preserving and has nofixed point,the number of bad(d−1)-simplices in S d is either0or2.Therefore,the summation above must be even.We now get the fundamental theorem as a simple corollary of Lemma1. Theorem3(The Fundamental Discrete Fixed Point Theorem)Let G=(f,X,S)be a simplicial direction-preserving function.If N G,i.e.the number of bad(d−1)-simplices on the boundary is odd,then G must have afixed point r∈X such that f(r)=0.5The Discrete Brouwer’s Fixed Point TheoremIn this section,the fundamental discretefixed point theorem will be employed to prove afixed point theorem concerning simplicial direction-preserving maps. It can be recognized as a discrete version of Brouwer’sfixed point theorem.It states that for any simplicial direction-preserving map from somefinite set to its convex hull,there must exist afixed point in the definition domain.We will also derive the theorem of Murota,Iimura and Tamura as a simple corollary.Actually,the one derived here is much stronger than theirs.5.1PreliminariesWe use e k to denote the k th unit vector of Z d where e k k=1and e k i=0for all i:1≤i=k≤d.Definition11For every(d−1)-simplex S∈F S,we let e S be the unit vector which is outgoing and perpendicular to S.For all r∈X if e S·(r−r S)>0for some r S∈S. Construction1(Extension of Simplicial Decomposition)Let X⊂R d be afinite set and S be a simplicial decomposition of X.For every point r/∈Given a simplicial direction-preserving map M=(F,X,S),we can convert it into a direction-preserving function G=(f,X,S)as follows.Construction2Given a simplicial direction-preserving map M=(F,X,S), we can build a simplicial direction-preserving function G=(f,X,S)as follows. For every r∈X,if F(r)=r,then f(r)=0.Otherwise,let i:1≤i≤d be the smallest integer such that F i(r)−r i=0,then f(r)=sign(F i(r)−r i)e i.5.2The Key LemmaLemma2Let M=(F,X,S)be a simplicial direction-preserving map where F is from X toX′where F′(r)=F((n+1)r) n+1.Let G′be the function constructed from map M′=(F′,X′,S′),then it is easy to check that N G=N G′.Therefore,we only need to prove the lemma for maps M=(F,X,S)with X⊂(−1,1)d.From now on,we always assume that X⊂(−1,1)d.If f has afixed point in set B X,then the lemma is proven.Otherwise,we extend(by applying Construction1for d times)G=(f,X,S)to be a new function G∗=(f∗,X∗,S∗)such that X⊂X∗,Lemma3guarantees the existence of G′.Lemma3For every triple G=(f,X,S)which satisfies all the conditions inDefinition12,there exists a triple G′=(f′,X′,S′)which is an extension of G along the k th coordinate.Proof.We only need to prove that there exists a simplicial decomposition S′ofX′satisfies S⊂S′.Actually,it can be constructed as follows.We list all the points in X′−X using the lexicographic order,add them into X one by one,and extend the original decomposition S step by step using the method described inDefinition1.Definition13G∗is said to be an extension of G if there exists a sequence G d+1...G2,G1such that G d+1=G,G∗=G1and G i is an extension of G i+1along the i th coordinate.The existence of G∗is guaranteed by Lemma3.Let G k=(f k,X k,S k).The following lemma is easy to check.Lemma4If r∈X k,r′∈[−1,1]d and r i=r′i for all1≤i<k,then r′∈X k.The following two corollaries can be derived from Lemma4.Corollary1X. Corollary2If v=e k−1or−e k−1is an outgoing vector at r∈X k,thenr+ǫv+di=kc i e i/∈X.If G is the function constructed from M using the method in Definition2,then any extension G∗of G is also simplicial direction-preserving.7Proof.We will use induction on k to prove that triple G k=(f k,X k,S k)is a simplicial direction-preserving function.The case for k=d+1is trivial.For case k≤d,if G k is not direction-preserving,then there must exist S∈S k−S k+1 and r1,r2∈V S such that f k(r1)and f k(r2)are opposite.As G k+1is direction-preserving,one of these two points belongs to X k+1,and the other is added into X k when G k+1is extended along the k th coordinate.Without loss of generality,we assume r1∈X k+1and r2k=1.As a result, f k(r2)=−e k and f k(r1)=+e k,as f k(r1)is opposite to f k(r2).The value of f k(r1)implies r1∈X and f(r1)=+e k.The way we construct G from map M guarantees F i(r1)=r1i for any1≤i<k and F k(r1)>ing Corollary2, we see that+e k is not an outgoing vector at r1∈X k+1,as F(r1)∈X k+1. Hence lemma5asserts that no pair(r2,S)where r2∈X k−X k+1and S∈S k−S k+1can satisfy that r2k=+1and r1,r2∈V S,which contradicts with our assumption in thefirst paragraph.Property1is a simple corollary of Lemma7.Lemma7For every triple G=(f,X,S)wherefinite set X⊂(−1,1)d,S is a simplicial decomposition of X and f is a direction function on X,if G∗= (f∗,X∗,S∗)is an extension of G,then N G∗is odd.Proof.We will use induction on d.The base case for d=1is trivial.For case d≥2,wefirst prove that every bad(d−1)-simplex S∈S∗on the boundary of [−1,1]d satisfies r d=−1for any r∈V S.Let S∈F S∗be such a simplex,then there exists r∈V S satisfies f∗(r)=+e d according to the definition of badness. Thus r is added into X when it is extended along the d th coordinate.We have r d=−1and−1<r i<1for any1≤i<d.This shows that S is covered by the hyperplane H which passes0[d→−1]and is perpendicular to+e d.Assume N is the number of bad(d−1)-simplices in H,then we only need to prove N is odd.Let X′=P(X)and X′′=P(H∩X∗)where projection P(r)=(r1,r2,...r d−1)∈R d−1,then S′and S′′are simplicial decompositions of X′and X′′respectively whereS′= P(S)S∈S∗and V S⊂X[d→−1] ,S′′= P(S)S∈S∗and S⊂H .Let f′be an arbitrary direction function on X′,then we extend it to be direc-tion function f′′on X′′as follows.For any r∈X′,f′′(r)=f′(r).Otherwise, f′′(r)=f∗((r1,r2,...r d−1,−1)).It’s easy to check that G′′=(f′′,X′′,S′′)is an extension of triple G′=(f′,X′,S′)in the(d−1)-dimensional space.Using arguments which are similar to those in the proof of Lemma1,the parity of N is same as the number of bad(d−2)-simplices on the boundary of8G′′.We know that the latter is odd according to the induction hypothesis,and Property1is proven.Property2.Let M=(F,X,S)be a simplicial direction-preserving map where F maps X toX, there must exist afixed point in X.Now we prove thefixed point theorem of Murota,Iimura and Tamura[13] as a direct corollary of Theorem4.Lemma8(Property of Integrally Convex Sets[13])For every integrally convex set X,there exists a simplicial decomposition S ofX,letting S x∈S be the smallest simplex containing x,then all of its vertices belong to N(x)={r∈Z d|||r−x||∞<1}.Let F be a hypercubic direction-preserving map from integrally convex set X⊂Z d todirection-preserving map from X toC a,b=X=∪P∈P P,and for every polytope P∈P, all of its vertices are drawn from X;2).For every two polytopes P1,P2∈P,if P1∩P2=∅,then P1∩P2is a face of both P1and P2.Definition16Let P be a convex t-polytope in R d and V P be its vertex set.The center point c P of polytope P is defined as c P= r∈V P(r/|V P|).Obviously,we have c P∈P and c P/∈V P.For example,let C⊂Z d be a t-cube centered at r∈Z d and perpendicular to T,then the center point c ofX into X and construct a simplicial decomposition S′for the new set X′. Details of the construction are described by the algorithm in Figure1. Every lattice set C a,b⊂R d has a natural convex subdivision P where P= {Fig.1.The Construction of S′and X′6.2Extension of Hypercubic Direction-Preserving FunctionsLet f be a hypercubic direction-preserving function on C a,b,we now extend it onto set D a,b as follows.For every r∈D a,b−C a,b,assume it is the center point of t-cube C⊂C a,b.If0∈f(C),then f(r)=0.Otherwise,let1≤t≤d be the largest integer such that f(C)∩{±e t}=∅,then f(r)=e t if e t∈f(C)and f(r)=−e t if−e t∈f(C).One can prove the following two properties.Property1Let f be a hypercubic direction-preserving function on C a,b⊂Z d, then G=(f,D a,b,S)is a simplicial direction-preserving function.Property2If the extended function G=(f,D a,b,S)has afixed point in D a,b, then the original function must have afixed point in C a,b.6.3The Nature of Bad CubesWe are ready to give an explicit explanation for the definition of bad cubes. Lemma9Let f be a hypercubic direction-preserving function on C a,b⊂Z d and G=(f,D a,b,S)be the extend function.For every t-cube C t in C a,b where 0≤t≤d−1,it is bad relative to f iffthe cardinality of the following set is odd:S C t= t-simplex S∈S is bad relative to G S⊂C t,then the way we build simplicial decomposition S implies that t-simplex S t⊂C t where S t−1is used to denote(t−1)-simplices in S.Firstly,we prove that,if t-cube C t⊂Z d is not bad,then|S C t|is even.If 0∈f(C t),then f(c)=0.As each t-simplex inC t,e k/∈f(V S),and thus,S C t=∅.Otherwise,we have f(C t)= {e1,...,e t+1},and thus f(c)=e t+1.Because C t is not bad,the number of bad11(t−1)-cubes on the boundary of C t is ing the induction hypothesis on t−1,a(t−1)-cube is bad iffthe number of bad(t−1)-simplices in it is odd. As a result,the number of bad(t−1)-simplices on the boundary of C t is even. Using the equation in thefirst paragraph,we know|S C t|is even too.On the other hand,we prove if C t is bad,then|S C t|is odd.Since f(C t)= {e1,...,e t+1},we have f(c)=e t+1.As the number of bad(t−1)-cubes on the boundary of C t is odd,the number of bad(t−1)-simplices on the boundary of C t is also odd,according to the induction hypothesis on case t−ing the equation in thefirst paragraph again,we know|S C t|is odd.We now get Lemma10as a direct corollary of Lemma9.Lemma10The parity of N B(the number of bad(d−1)-cubes on the boundary of C a,b)is same as the one of N G(the number of bad(d−1)-simplices on the boundary of D a,b).With Property1,2and Lemma10above,Chen and Deng’s theorem can be immediately derived from the fundamental discretefixed point theorem.7Concluding RemarksIn this paper,we generalize the concept of direction-preserving maps and char-acterize a new class of discrete maps over simplicial structures.The fundamental discretefixed point theorem is then proposed,which is based on the counting of bad(d−1)-simplices on the boundary.The power of this theorem is demon-strated in two ways.First,it is applied to prove the discrete Brouwer’sfixed point theorem which is much more general than the one of Murota,Iimura and Tamura.Second,we resolve the puzzle of bad cubes,and show that the bound-ary condition of Chen and Deng’s theorem is exactly equivalent to the one of the fundamental theorem.Our work would immediately imply the corresponding discrete concept of degree.It would be an especially interesting problem to study the case when the fixed point is defined in the recent model of a set of points.An immediate follow-up research direction is to understand other concepts and theorems related to degree.A clear understanding would definitely advance the state of art of the numerical computation of related problems,such as the case of discretefixed points versus approximatefixed points[1].References1.X.Chen and X.Deng.On Algorithms for Discrete and Approximate BrouwerFixed Points.In STOC2005,pages323–330.2.X.Chen and X.Deng.3-Nash is PPAD-complete.ECCC,TR05-134,2005.3.X.Chen and X.Deng.Settling the Complexity of Two-Player Nash-Equilibrium.FOCS,2006.124.X.Chen,X.Deng,and S-H puting Nash Equilibria:Approximationand Smoothed Complexity.FOCS,2006.5.X.Chen and ttice Embedding of Direction-Preserving CorrespondenceOver Integrally Convex Set.AAIM2006,2006,pp.53–63.6.X.Chen and X.Deng.On the Complexity of2D Discrete Fixed Point Problem.ICALP2006,pp.489–5007.P.Crescenzi and R.Silvestri.Sperner’s lemma and robust put.Complexity,7(2):163–173,1998.8. C.Daskalakis,P.W.Goldberg,and C.H.Papadimitriou.The Complexity of Com-puting a Nash Equilibrium.STOC,2005.9. C.Daskalakis and C.H.Papadimitriou.Three-player games are hard.ECCC,TR05-139.10.K.Friedl,G.Ivanyos,M.Santha,and F.Verhoeven.On the black-box complexityof Sperner’s Lemma.In FCT2005.11.M.D.Hirsch,C.H.Papadimitriou,and S.Vavasis.Exponential lower bounds forfinding Brouwerfixed plexity,5:379–416,1989.12.T.Iimura.A discretefixed point theorem and its applications.Journal of Mathe-matical Economics,39(7):725–742,2003.13.T.Iimura,K.Murota,and A.Tamura.Discrete Fixed Point Theorem Reconsid-ered.Journal of Mathematical Economics,to appear.an,D.Talman,and Z.Yang.Solving discrete zero point problems.TinbergenInstitute Discussion Papers,2004.15. E.Sperner.Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes.16.G.M.Ziegler.Lectures on Polytopes.Springer-Verlag,New York,1982.13。

机器学习题库一、 极大似然1、 ML estimation of exponential model (10)A Gaussian distribution is often used to model data on the real line, but is sometimesinappropriate when the data are often close to zero but constrained to be nonnegative. In such cases one can fit an exponential distribution, whose probability density function is given by()1xb p x e b-=Given N observations x i drawn from such a distribution:(a) Write down the likelihood as a function of the scale parameter b.(b) Write down the derivative of the log likelihood.(c) Give a simple expression for the ML estimate for b.2、换成Poisson 分布：()|,0,1,2,...!x e p x y x θθθ-==()()()()()1111log |log log !log log !N Ni i i i N N i i i i l p x x x x N x θθθθθθ======--⎡⎤=--⎢⎥⎣⎦∑∑∑∑3、二、 贝叶斯假设在考试的多项选择中，考生知道正确答案的概率为p ，猜测答案的概率为1-p ，并且假设考生知道正确答案答对题的概率为1，猜中正确答案的概率为1，其中m 为多选项的数目。

Game-Theoretic Artificial Intelligence1Spring2007 Professor Amy Greenwald Topic#2 Matrix Games and Nash EquilibriumThis lecture is concerned with the Nobel Prize winning work of John Nash. In particular,we define the notion of mixed strategies in matrix games,and we present Nash’s argument on the existence of mixed strategy(Nash)equilibrium. 1Examples of GamesThe most well-known game-theoretic scenario is the paradoxical situation known as the Prisoners’Dilemma,which was popularized by Axelrod[1]in his popular science book.The following is one(uncommon)variant of the story.2A crime has been committed for which two prisoners are held incommunicado. The district attorney is assigned to question the prisoners.He designs the following incentive structure to induce the prisoners to talk.If neither prisoner talks,both prisoners automatically receive mild sentences(payoff4).But if exactly one prisoner squeals on the other,the squealer is let offscot free(payoff5),while the“squealee”is subject to a severe sentence(payoff0).Finally,if both prisoners squeal,they share the severe punishment(payoff1).The Prisoners’Dilemma is a two player a matrix—or strategic,or normal form—game.Such games are easily described by payoffmatrices,where the strategies of player1and player2serve as row and column labels,respectively,and the corresponding payoffs are listed as pairs in matrix cells such that thefirst(sec-ond)number is the payoffto player1(2).The payoffmatrix which describes the Prisoners’Dilemma is depicted in Figure1,with C denoting“cooperate”or“confess”,and D denoting“defect”or“don’t cooperate.”This game is known as the Prisoners’Dilemma because the only rational out-come is(D,D),which yields suboptimal payoffs of(1,1).The reasoning is as follows.If player1plays C,then player2is better offplaying D,since D yields a payoffof5,whereas C yields only4;but if player1plays D,then player2is again better offplaying D,since D yields a payoffof1,whereas C yields only 0.Hence,regardless of the strategy of player1,a rational player2plays D. By a symmetric argument,a rational player1also plays D.Thus,the unique outcome of the game,assuming the players are rational,is(D,D).C D 4,40,51,1 5,0D C12Figure1:The Prisoners’DilemmaAnother popular two-player game is called the Battle of the Sexes.A man and a woman would like to spend an evening out together;however,the man prefers to go to a football game(strategy F),while the woman prefers to go to the ballet(strategy B).Both the man and the woman prefer to be together,even at the event that is not to their liking,rather than go out alone.The payoffs of this coordination game are shown in Figure2;the woman is player1and the man is player2.In this game,there are two coordination equilibria,one which is preferred by the woman,and another which is preferred by the man.12BB2,10,01,20,0FFFigure2:Battle of the SexesThe stag hunt game(see Figure3)is a prototypical social contract.Rousseau tells an early version of the story in A Discourse on Inequality.:If it was a matter of hunting a deer,everyone realized that he mustremain well faithful to his post;but if a hare happened to pass withinreach of one of them,we cannot doubt that he would have gone offin pursuit of it without scruple...This game has two equilibria,one of which Pareto dominates the other:i.e., all players are simultaneously better offat one equilibrium than the other.But action H risk-dominates action D,since action H is safer for each player,given his/her uncertainty about the other player’s action.212DD 2,20,11,0HH 1+ε,1+εFigure 3:Stag HuntOur final example is an ecological game which was studied by Maynard Smith [6]in his analysis of the theory of evolution in terms of games (see Figure 4).The game is played between animals of the same size who live in the wilderness and encounter one another in their search for prey.During an encounter between two animals,each animal has a choice between behaving as a hawk:i.e.,fighting for the prey;or as a dove:i.e.,sharing the prey peacefully.If both animals decide to play like hawks,then each animal has an equal chance of winning the value v of the prey or of losing the fight at cost c ,where 0<v <c ;thus,the expected payoffto both players is (v −c )/2.Alternatively,if both animals act as doves,then the prey is shared with equal payoffs v/2.Finally,if one animal behaves like a hawk and the other behaves like a dove,then the hawk gets a payoffworth the full value of the prey and the other gets nothing.In this game,the animals prefer to choose opposing strategies:if one animal plays hawk,then it is in the best interest of the other to play dove;and inversely,if one animal plays dove,then it is in the best interest of the other to play hawk.D D H12Hv,0(v-c)/2(v-c)/2,0,v v/2,v/2Figure 4:Hawks and Doves32Nash EquilibriumA Nash equilibrium is a strategy profile from which none of the players has any incentive to deviate.In particular,no player can achieve strictly greater payoffs by choosing any strategy other than the one prescribed by the profile,given that all other players choose their prescribed strategies.In this sense,a Nash equilibrium specifies optimal strategic choices for all players.Let us examine the Nash equilibria in the aforementioned examples:•In the Prisoners’Dilemma,(D,D)is a Nash equilibrium:given that player 1plays D,the best response of player2is to play D;given that player2 plays D,the best response of player1is to play D.•The Battle of the Sexes has two pure strategy Nash equilibria,namely (B,B),and(F,F):If the woman plays B,then the best response of the man is B;if the man plays B,then the best response of the woman is B.Analogously,if the woman plays F,the best response of the man is F;if the man plays F,the best response of the woman is F.•The game of Hawks and Doves also has two pure strategy Nash equilibria, only this time,the players seek to miscoordinate their actions,rather than coordinate.If one player plays the hawk,then the other player prefers to play the dove,achieving payoffs of0,rather than(v−c)/2<0.On the other hand,if one player plays the dove,then the other player prefers to play the hawk,achieving payoffs of v,rather than v/2.•Finally,in the Stag Hunt,both(D,D)and(H,H)are Nash equilibria: hunting for deer is Pareto-optimal,but hunting for hare is risk-dominant. Matching Pennies is another well-known example of a two player,zero-sum game.In this game,each of the players,the matcher and the mismatcher,3flips a coin,and the payoffs are determined as follows.If the coins come up matching (i.e.,both heads or both tails),then the matcher wins,so the mismatcher pays the matcher$1.If the coins do not match(i.e.,one head and one tail),then the mismatcher wins,so the matcher pays the mismatcher$1.In Figure5,player 1is the mismatcher and player2is the matcher.This game is called zero-sum because the payoffs in each cell of the matrix sum to zero.In the game of Matching Pennies,there is no pure strategy Nash equilibrium. If player1plays H,then the best response of player2is T;but if player2plays T,the best response of player1is not H,but T.Moreover,if player1plays T, then the best response of player2is H;but if player2plays H,then the best response of player1is not T,but H.This game,however,does have a mixed strategy Nash equilibrium.A mixed strategy is a randomization over a set of12H TH T 1,-1-1,1 -1,11,-1Figure5:Hawks and Dovespure strategies.In particular,the probabilistic strategy profile in which bothplayers choose H with probability12is the unique(mixed strategy)Nash equilibrium in the game of Matching Pennies.A matrix game is a3-tupleΓ=(N,(A i,R i)1≤i≤n),where•N is a set of n players•A i is afinite strategy(or action)set(a i∈A i)•R i:A→R is a payofffunction,where A=A1×...×A nMatrix games are also sometimes called games in strategic,or normal,form.In this formalism,the Prisoners’Dilemma consists of a set of players N={1,2}, with strategy(action)sets A1=A2={C,D},and payoffs as follows:R1(C,C)=R2(C,C)=4R1(C,D)=R2(D,C)=0R1(D,D)=R2(D,D)=1R1(D,C)=R2(C,D)=5A mixed strategy set for player i is the set of probability distributions over the action set A i,which can be described by the simplex operator∆:∆(A i)= q i:A i→[0,1]| a i∈A i q i(a i)=1For convenience,let Q i≡∆(A i).The usual notational conventions extend to mixed strategies: e.g.,Q= i Q i and q=(q i,q−i)∈Q.In the context of mixed strategies,the expected payoffs to player i from strategy profile q are:E a∼q[R i(a)]= a∈A q(a)R i(a)whereq(a)=N j=1q j(a j) 5As usual,the payoffs to player i depend on the mixed strategies of all players. An implication of the assumption of rationality is that a rational player always plays an optimizing strategy,or a best response to the strategies of the other players.A strategy q∗i∈Q i is a best response for player i to opposing strategy q−i∈Q−i iff∀q i∈Q i,E[R i(q∗i,q−i)]≥E[R i(q i,q−i)].The best response set for player i to strategy profile q−i is:br i(q−i)={q∗i∈Q i|∀q i∈Q i,E[R i(q∗i,q−i)]≥E[R i(q i,q−i)]} The set br i(q−i)is often abbreviated br i(q).Let br(q)= i br i(q).A Nash equilibrium is a strategy profile in which all players choose strategies that are best responses to the strategic choices of the other players.Characterized in terms of best response sets,a Nash equilibrium is a strategy profile q∗s.t. q∗∈br(q∗).It is apparent from this definition that a Nash equilibrium is a fixed point of the best response relation.In1951,Nash proved that everyfinite strategic form game has(at least)one mixed strategy Nash equilibrium[4].The existence proof relies on a fundamental result in topology,namely Kakutani’s fixed point theorem,a generalization of Brouwer’sfixed point theorem[2].2.1Digression:Fixed Point TheoremsA closed set X contains all its limit points:i.e.,for all sequences{x n}in X,if x n→x,then x∈X.A set is open if its complement is closed.For example, the interval[0,1]is a closed subset of R and the interval(0,1)is an open subset of R;but the intervals(0,1]and[0,1)are neither open nor closed subsets of R.A subsequence of the sequence{x n}is a restriction of the mapping from N to X to a mapping from N′⊆N to X.A subsequence is a sequence in its own right.A set X is called compact iffevery sequence in X has a convergent subsequence that converges to a point in X.Note that every compact set is closed.Heine-Borel Theorem A set X⊆R n is compact iffit is closed and bounded. Weierstrass’Theorem A real-valued continuous function on a compact set attains a maximum and a minimum.A correspondence f:X⇒Y is a mapping from X to subsets of Y:i.e., f(x)⊆Y.A function is a special case of a correspondence in which f(x) is a singleton for all x∈X.Just as functions can be associated with their graphs,correspondences can be associated with their graphs.The graph of the correspondence f is the set of pairs{(x,y)|x∈X,y∈f(x)}.A set X is called convex iff∀λ∈[0,1],∀x,y∈X,λx+(1−λ)y∈X.The correspondence f is nonempty and convex-valued ifff(x)is nonempty and convex for all x∈X. Kakutani’s Fixed Point Theorem.Let X⊂R n be nonempty,compact, and convex.If f:X⇒X is a nonempty,convex-valued correspondence with a closed graph,then f has afixed point:i.e.,there exists x∗∈X s.t.x∗∈f(x∗).6Brouwer’s Fixed Point Theorem.Let X⊂R n be nonempty,compact, and convex.If f:X→X is a continuous function,then f has afixed point:i.e.,there exists x∗∈X s.t.x∗=f(x∗).2.2Proof of ExistenceThe proof of existence of Nash equilibrium is a direct application of Kakutani’s fixed point theorem.It suffices to show that the set of mixed strategies Q is nonempty,compact,and convex,and that the best-response correspondence (i.e.,br:Q⇒Q)is nonempty and convex-valued,with a closed graph.Lemma The set of mixed strategies Q is nonempty,compact,and convex. Proof Recall that Q= i Q i,where Q i is the set of probability over distri-butions player i’s the action set A i.The set Q is nonempty(assuming A i is nonempty,for all players i).Given a sequence{(q m1,...,q m n)}of mixed strategies.that converges to(q∗1,...,q∗n). This limit point is indeed a mixed strategy:i.e.,q∗i≥0and i q∗i=1.The former claim follows from the fact that the limit of a sequence of non-negative points is itself non-negative.The latter claim follows from the fact that the sumof the limits equals the limit of the sum.Thus,Q is closed.Moreover,Q is bounded in each component by0and1.Therefore,Q is compact.The set of mixed strategies Q i for each player i is convex:i.e.,for all q i,p i∈Q i, for allλ∈[0,1],the convex combinationλq i+(1−λ)p i∈Q i.thus,given two elements(q1,...,q n),(p1,...,p n)∈Q,the convex combinationλ(q1,...,q n)+ (1−λ)(p1,...,p n)=(λq1+(1−λ)p1,...,λq n+(1−λ)p n)∈Q,for allλ∈[0,1]. Thus,the set of mixed strategies Q is nonempty,compact,and convex.Lemma The best-response correspondence is nonempty.Proof By Weierstrass’theorem,any real-valued continuous function on a compact set attains a maximum.Recall that the set Q i is compact.Since R i isa linear function of Q i,R i is continuous.Thus,br i:Q→Q i is nonempty,for all players i,from which it follows that br is nonempty.Lemma The best-response correspondence is convex-valued.Proof If q∗i,p∗i∈br i(q−i)are best replies of player i to q−i,then R i(q∗i,q−i)=R i(p∗i,q−i)=λR i(q∗i,q∗−i)+(1−λ)R i(p∗i,q∗−i).Now,by the linearity of R i,λR i(q∗i,q∗−i)+(1−λ)R i(p∗i,q∗−i)=R i(λq∗i+(1−λ)p∗i,q∗−i).Thus,the convex combinationλq∗i+(1−λ)p∗i∈br i(q−i).Since q−i was arbitrary,br i is convex-valued.Since i was arbitrary,br is convex-valued.Lemma The graph of the best-response correspondence is closed.7Proof Must show p ∈br (q ),given the sequences q m ,p m ∈Q s.t.q m →q and p m →p ,with p m ∈br (q m )for all m .Suppose not:i.e.,suppose there exists player i s.t.p i ∈br i (q −i ).It follows that there exists q i ∈Q i s.t.R i (q i ,q −i )>R i (p i ,q −i ).Now let δ≡R i (q i ,q −i )−R i (p i ,q −i )>0.Since R i is linear,and therefore continuous,for all ǫ>0,there exists M ǫ∈N s.t.for all m ≥M ǫ,|R i (p m i ,q m −i )−R i (p i ,q −i )|<ǫand |R i (q i ,q m −i )−R i (q i ,q −i )|<ǫ.NowR i (q i ,q m −i )>R i (q i ,q −i )−ǫ=R i (p i ,q −i )+R i (q i ,q −i )−R i (p i ,q −i )−ǫ=R i (p i ,q −i )+δ−ǫ>R i (p m i ,q m −i )+δ−2ǫIf ǫ=δ/2,then R i (q i ,q m −i )>R i (p m i ,q m −i ),for all m ≥M δ/2.But then p m i ∈br i (q m −i )for all m .Contradiction.Therefore,the graph of br is closed.Exercise Compute the best-response correspondences for the game depicted in Figure 6,a version of Hawks and Doves.Plot these correspondences,and compute all Nash equilibria.12H H 1,1D D2,00,2−1,−1Figure 6:Hawks and Doves3SummaryIn this lecture,we defined Nash equilibrium and reproved Nash’s theorem guar-anteeing its existence in all (finite)matrix games.Although Nash equilibrium is the generally accepted solution concept in the deductive analysis of matrix games,the Nash equilibria in our examples are somewhat peculiar.In the Prisoners’Dilemma,the Nash equilibrium payoffs are sub-optimal.In the game of Matching Pennies,there is no pure strategy Nash equilibrium;the unique Nash equilibrium is probabilistic.Finally,in the coordination and miscoordination games,the Nash equilibrium is not unique.In future lectures,alternative notions of equilibria are discussed.8References[1]R.Axelrod.The Evolution of Cooperation.Basic Books,New York,1984.[2]L.Brouwer.Uber abbildungen von mannigfaltigkeiten.Mathematische An-nalen,38(71):97–115,1912.[3]S.Kakutani.A generalization of brouwer’sfixed point theorem.Duke Math-ematical Journal,8:457–458,1941.[4]J.Nash.Non-cooperative games.Annals of Mathematics,54:286–295,1951.[5]A.Rapoport.Two-Person Game Theory.University of Michigan Press,AnnArbor,1966.[6]J.M.Smith.Evolution and the Theory of Games.Cambridge UniversityPress,New York,1982.9。

1
Introduction
2
DANIEL FROHARDT AND KAY MAGAARD
apart from a few exceptions, if F (G) is a group of Lie type written over Fq , g 2 G] , and M is a maximal subgroup of G not containing F (G) then f (g; M ) < 4=3q. We re ne that here by producing element-wise bounds. We show that for every " > 0 there is an integer n such that if G has Lie rank at least n, then f (g; M ) < 1=q + " for every g 2 G n Z (G) and every maximal subgroup M under consideration here. More generally, we show that if G is a classical group of large Lie rank de ned over Fq then the only elements with non-negligible xed point ratios are elements that act linearly on the natural module with a large eigenspace. We further show that the xed point ratios for such elements are essentially q?dk where d is the codimension of the eigenspace and k is the smaller of the dimension or codimension of the subspace stabilized by the maximal subgroup. We show speci cally that if G is a classical group with natural module V of dimension n over Fq , M is a maximal subgroup of G such that M \F (G) stabilizes a subspace of V of dimension or codimension k, where k n=2, then either f (g; M ) (4000 + 150n)q?(n?6)=2 or g acts linearly on V with an eigenspace of codimension d, with dk < n=2, and f (g; M ) q?dk + 2000q?(n?6)=2.