《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》的目的是在研究生层面提供博弈论的*新全面、严谨的结果。《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》旨在向读者介绍计算游戏均衡的优化方法和算法。作者假设读者熟悉博弈论、数学规划、优化和非凸优化的基本概念。我们打算《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》也用于研究生阶段工程、运筹学、计算机科学和数学系提供的优化、博弈论课程。由于《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》涉及了许多在早期优化教科《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》没有描述的计算平衡的新算法和想法，我们希望《RECENT ADVANCES IN GAME THEORY NEW EQUILIBRIUMS,POLYMATRIX AND BIMATRIX GAMES,AND COMPUTATIONAL METHODS（博弈论*新进展：新均衡、多矩阵博弈及计算方法）》不仅对博弈论专家有用，而且对优化研究人员也有用。除了纳什均衡、伯杰均衡、非合作博弈等**主题外，一些重要的*近的发展包括：*大*小和*小*大问题、反纳什、反伯杰均衡、多矩阵博弈、广义纳什均衡、计算方法和算法。

Chapter 1 Introduction
　　Game theory is a branch of applied mathematics that provides tools for analyzing situations in which parties， called players， make independent decisions. This independence causes each player to consider the other players’ possible decisions or strategies， when formulating their own.
　　On the other hand， game theory is the study of mathematical models of strategic interactions[1]. It has applications in many fields of social science， extensively used in economics， logic， systems science， and computer science2]. Initially game theory addressed two-person zero-sum games， when a participant’s gains or losses are exactly balanced by other participant’s losses and gains. In the 1950s， it was extended to the study of non-zero sum games and eventually applied to a wide range of behavioral relations， now serving as an umbrella term for the science of rational decision making in humans， animals， and computers.
　　Modem game theory began with the idea of mixed strategy equilibria in two-person zero-sum games and its proof by John von Neumann. Von Neumann’s original proof used the Brouwer fixed-point theorem on continuous mappings into compact convex sets， which became a standard method in game theory and mathematical economics. His paper was followed by “Theory of games and economic behavior"9 (1944)， co-written with Oskar Morgenstem， which considered cooperative games with several players.
　　In 1951，Nash proved that every finite TV-players， non-zero sum (not just two-players zero-sum) non-cooperative game has what is now known as a Nash equilibrium in mixed strategies.
　　Game theory experienced a flurry of activity in the 1950s， during which the concepts of the core， the extensive form game， fictitious play， repeated games， and the Shapley value were developed. The 1950s also saw the first applications of game theory to philosophy and political science.
　　In 1965，Reinhard Selten introduced his solution concept of subgame perfect equilibria， which further refined the Nash equilibrium. Later he introduced trembling hand perfection as well.
　　In the 1970s， game theory was extensively applied in biology， largely as a result of the work of John Maynard Smith and his evolutionarily stable strategy. In addition， the concepts of correlated equilibrium， trembling hand perfection and common knowledge[3] were introduced and analyzed.
　　In 1994，John Nash was awarded the Nobel Memorial Prize in Economic Sciences for his contribution to game theory. Nash’s most famous contribution to game theory is the concept of the Nash equilibrium which is a solution concept for non-cooperative games.
　　In 2005，game theorists Thomas Schelling and Robert Aumann followed Nash， Selten， and Harsanyi as Nobel Laureates. Schelling worked on dynamic models， early examples of evolutionary game theory. Aumann contributed more to the equilibrium school， introducing equilibrium coarsening and correlated equilibria， and developing an extensive formal analysis of the assumption of common knowledge and its consequences.
　　In 2007，Leonid Hurwicz， Eric Maskin’ and Roger Myerson were awarded the Nobel Prize in Economic Sciences “for having laid the foundations of mechanism design theory”. Myerson’s contributions include the notion of proper equilibrium and an important graduate textbook “Game Theory，Analysis of Conflicf. Hurwicz introduced and formalized the concept of incentive compatibility.
　　In 2012， Alvin E. Roth and Lloyd S. Shapley were awarded the Nobel Prize in Economic Sciences “for the theory of stable allocations and the practice of market design”. In 2014， the Nobel went to game theorist Jean Tirole.
　　A game is considered cooperative if players can form binding commitments that are externally enforced (e.g.， through contract law). A game is non-cooperative if players cannot form alliances or if all agreements need to be self-enforcing (e.g.， through credible threats)[17].
　　Cooperative games are often analyzed through the framework of cooperative game theory， which focuses on predicting which coalitions will form， the joint actions that groups take， and the resulting collective payoffs. It is different from non-cooperative game theory which focuses on predicting individual playersJ actions and payoffs by analyzing Nash equilibria[18，19].
　　Cooperative game theory provides a high-level approach as it describes only the structure and payoffs of coalitions， whereas non-cooperative game theory also looks at how strategic interaction will affect the distribution of payoffs. As non-cooperative game theory is more general， cooperative games can be analyzed through the approach of non-cooperative game theory (the converse does not hold) provided that sufficient assumptions are made to encompass all the possible strategies available to players due to the possibility of external enforcement of cooperation.
　　Zero-sum games (more generally， constant-sum games) are games in which choices by

Contents
Preface
Chapter1 Introduction 1
Chapter2 Zero-Sum Game 6
2.1 Two-person zero-sumgame 6
2.2 Minimax and maxmin 7
2.3 Saddle point 11
2.4 Matrixgamein pure strategies 13
2.5 Matrixgamein mixed strategies 15
2.6 Reductionofgame theoryto linear programming 16
Chapter3 Maxmin and MinimaxProblems 19
3.1 Maxmin problem 19
3.2 Optimality conditionsfor maxmin problem 21
3.3 Optimality conditions for minimax problem 25
Chapter4 Non-Zero Sum Game 31
4.1 Two-person non-zero sumgame 31
4.1.1 Bimatrixgame 31
4.1.2 Nash equilibrium 33
4.1.3 Berge equilibrium 38
4.2 Non-zero sum three-persongame 43
4.3 Non-zero sum four-persongame 48
4.4 Non-zero sum n-persongame 55
Chapter5 Anti-Nash and Anti-Berge Equilibriumin Bimatrix Game 59
5.1 Anti-Nash equilibriumin bimatrixgame 59
5.2 Anti-Berge equilibriumin bimatrixgame 63
Chapter6 Polymatrix Game 65
6.1 Three-sidedgame 65
6.1.1 Main propertiesof thegame Γ(A， B，C) 66
6.1.2 Optimization formulationof three-sidedgame 69
6.2 Four-players triplegame 72
6.3 Game of N-players 79
6.3.1 Nash theorem and the optimization problem 81
Chapter7 N-Players Non-Cooperative Games 85
7.1 Non-cooperativegames 85
7.2 Generalized Nash equilibrium problems 87
7.3 Someequivalent approachto generalizedNash equilibrium problems 89 89
7.3.1 Variational inequality approach
7.3.2 Nikaido-Isoda function based approach 90
7.3.3 Karush-Kuhn-Tucker conditions approach 92
7.4 Global optimization D.Capproach to quadratic nonconvex generalized Nash equilibrium problems 94
7.4.1 Generalized Nash equilibrium problem and equivalent optimization formulation 94
7.4.2 Quadratic nonconvexgame andgap function 96
7.4.3 D.Coptimization approachto non-cooperativegame 100
7.5 Generalized Nash equilibrium problem based on Malfatti’s problem 103
7.5.1 Malfatti’s problemand convex maximization 104
7.5.2 Generalized Nash equilibrium problems 105
7.6 Aglobal optimization approach to Berge equilibrium based on a regularized function 109
7.6.1 Existence of Berge equilibrium and constrained optimization reformulations 110 Chapter8 Game Theory and Hamiltonian System 116
8.1 Hamiltonian system 116
8.2 Evolutionarygames and Hamiltonian systems.119
8.3 Optimal controltheoryandthe Hamiltonian operator 121
8.4 Differentialgames and the Hamilton-Jacobi-Bellman (HJB) Principle 122
8.4.1 The relationship betweengame theoryandthe Hamiltonian operator 124
8.4.2 Two-person zero-sum differentialgames 125
8.4.3 Two-person non-zero sum differentialgames 127
Chapter9 Computational Methods and Algorithmsfor Matrix Game 132
9.1 D.Cprogramming approachtoBerge equilibrium 132
9.1.1 Local search method 133
9.1.2 Global search method 134
9.1.3 Numerical results for D.Cprogramming approach to Berge equilibrium 137
9.2 Global search method curvilinear algorithm forgame 142
9.2.1 The curvilinear global search algorithm 142
9.2.2 Numerical results for three-persongame 145
9.2.3 Numerical results for four-persongame 147
9.2.4 Numerical results N-persongame 149
9.3 The numerical approach for anti-Nash equilibrium search 152
9.3.1 The modi.ed Rosenbrock algorithm 153
9.3.2 Theunivariate global search procedure 154
9.3.3 Numerical results for anti-Nash equilibriumby Rosenbrock algorithm 156
9.4 Modi.ed parallel tangent algorithm for anti-Berge equilibrium 159
9.4.1 The modi.ed parallel tangent algorithm 160
9.4.2 Theunivariate global search procedure 161
9.4.3 Numerical results for anti-Berge equilibrium by modi.ed tangent algorithm 162
9.5 The curvilinear multistart algorithmfor polymatrixgame 166
9.5.1 Numericalexperimentof polymatrixgame 169
9.6 Numerical resultsfor non-cooperativegame 171
9.7 Numerical resultsforMalfati’s problem 175
Bibliography 182