The consistency principle for games in strategic form

We start with giving an axiomatic characterization of the Nash equilibrium (NE) correspondence in terms of consistency, converse consistency, and one-person rationality. Then axiomatizations are given of the strong NE correspondence, the coalition-proof NE correspondence and the semi-strong NE. In all these characterizations consistency and suitable variants of converse consistency play a role. Finally, the dominant NE correspondence is characterized. We also indicate how to generalize our results to Bayesian and extensive games.     

多选择NTU对策核心的一个非空条件及公理化

提出了\pi-均衡多选择NTU对策的概念,证明了\pi-均衡多选择NTU对策的核心非空, 定义了多选择NTU对策的非水平性质和缩减对策,给出了相容性和逆相容性等概念. 用个体合理性、单人合理性、相容性和逆相容性对非水平多选择NTU对策的核心进行了公理化.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.     

The consistency principle and an axiomatization of the α-core

This paper examines the α-core of strategic games by means of the consistency principle. I provide a new definition of a reduced game for strategic games. And I define consistency (CONS) and two forms of converse consistency (COCONS and COCONS^*) under this definition of reduced games. Then I axiomatize the α-core for families of strategic games with bounded payoff functions by the axioms CONS, COCONS^*, weak Pareto optimality (WPO) and one person rationality (OPR). Furthermore, I show that these four axioms are logically independent. In proving this, I also axiomatize the α-individually rational solution by CONS, COCONS and OPR for the same families of games. Here the α-individually rational solution is a natural extension of the classical `maximin' solution. Received: June 1998/Final version: 6 July 2001     

A Globally Convergent Algorithm to Compute All Nash Equilibria for <Emphasis Type="Italic">n</Emphasis>-Person Games

In this paper we present an algorithm to compute all Nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.     

Characterization of the core in full domain marriage problems

In this paper, we study the core of two-sided, one-to-one matching problems. First, in a model in which agents have strict preferences over their potential mates and are allowed to remain single, we characterize the core as the unique solution that satisfies individual rationality, Pareto optimality, gender fairness, consistency, and converse consistency. Next, in a model that relaxes the constraint that agents have strict preferences over their potential mates, we show that no solution exists that satisfies Pareto optimality, anonymity, and converse consistency. In this full domain, we characterize the core by individual rationality, weak Pareto optimality, monotonicity, gender fairness, consistency, and converse consistency.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

Dynamic Game Model of Endogenous Growth with Consumption Externalities

This paper introduces consumption externalities into an endogenous growth model of common capital accumulation and characterizes balanced growth equilibria. Contrary to the standard argument in previous studies, we show that the growth rate in a feedback Nash equilibrium can be higher than that in an open-loop Nash equilibrium if agents strongly admire the consumption of others. This result is irrelevant to whether preferences exhibit “keeping up with the Joneses” or “running away from the Joneses”.     

Computing equilibria of Cournot oligopoly models with mixed-integer quantities

We consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method.     

0-1对策的完全混合Nash均衡的代数求解法

将求解一般0-1策略对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程组的问题.作为一种特殊而重要的情形,利用Pascal矩阵,Newton矩阵(对角元素为Newton二项式系数的对角矩阵)和Pascal-Newton矩阵(Pascal矩阵和Newton矩阵的逆阵的乘积)将求解对称0-1对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程的问题,并给出第二问题的反问题(由完全混合Nash均衡求解对称0-1对策族)的求解方法.同时,给出了一些算例来说明对应问题的算法.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Equilibrium selection and altruistic behavior in noncooperative social networks

Given their importance in determining the outcome of many economic interactions, different models have been proposed to determine how social networks form and which structures are stable. In Bala and Goyal (Econometrica 68, 1181–1229, 2000), the one-sided link formation model has been considered, which is based on a noncooperative game of network formation. They found that the empty networks, the wheel in the one-way flow of benefits case and the center-sponsored star in the two-way flow case play a fundamental role since they are strict Nash equilibria of the corresponding games for a certain class of payoff functions. In this paper, we first prove that all these network structures are in weakly dominated strategies whenever there are no strict Nash equilibria. Then, we exhibit a more accurate selection device between these network architectures by considering “altruistic behavior” refinements. Such refinements that we investigate here in the framework of finite strategy sets games have been introduced by the authors in previous papers.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

Stochastic Variational Inequality Approaches to the Stochastic Generalized Nash Equilibrium with Shared Constraints

In this paper, we consider the generalized Nash equilibrium with shared constraints in the stochastic environment, and we call it the stochastic generalized Nash equilibrium. The stochastic variational inequalities are employed to solve this kind of problems, and the expected residual minimization model and the conditional value-at-risk formulations defined by the residual function for the stochastic variational inequalities are discussed. We show the risk for different kinds of solutions for the stochastic generalized Nash equilibrium by the conditional value-at-risk formulations. The properties of the stochastic quadratic generalized Nash equilibrium are shown. The smoothing approximations for the expected residual minimization formulation and the conditional value-at-risk formulation are employed. Moreover, we establish the gradient consistency for the measurable smoothing functions and the integrable functions under some suitable conditions, and we also analyze the properties of the formulations. Numerical results for the applications arising from the electricity market model illustrate that the solutions for the stochastic generalized Nash equilibrium given by the ERM model have good properties, such as robustness, low risk and so on.     

Weak equilibrium in a spatial model

Spatial models of two-player competition in spaces with more than one dimension almost never have pure-strategy Nash equilibria, and the study of the equilibrium positions, if they exist, yields a disappointing result: the two players must choose the same position to achieve equilibrium. In this work, a discrete game is proposed in which the existence of Nash equilibria is studied using a geometric argument. This includes a definition of equilibrium which is weaker than the classical one to avoid the uniqueness of the equilibrium position. As a result, a “region of equilibrium” appears, which can be located by geometric methods. In this area, the players can move around in an “almost-equilibrium” situation and do not necessarily have to adopt the same position.     

Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic, and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give some numerical example to illustrate the behavior of robust Nash equilibria.     

Iterative computation of noncooperative equilibria in nonzero-sum differential games with weakly coupled players

We study the Nash equilibria of a class of two-person nonlinear, deterministic differential games where the players are weakly coupled through the state equation and their objective functionals. The weak coupling is characterized in terms of a small perturbation parameter . With =0, the problem decomposes into two independent standard optimal control problems, while for 0, even though it is possible to derive the necessary and sufficient conditions to be satisfied by a Nash equilibrium solution, it is not always possible to construct such a solution. In this paper, we develop an iterative scheme to obtain an approximate Nash solution when lies in a small interval around zero. Further, after requiring strong time consistency and/or robustness of the Nash equilibrium solution when at least one of the players uses dynamic information, we address the issues of existence and uniqueness of these solutions for the cases when both players use the same information, either closed loop or open loop, and when one player uses open-loop information and the other player uses closed-loop information. We also show that, even though the original problem is nonlinear, the higher (than zero) order terms in the Nash equilibria can be obtained as solutions to LQ optimal control problems or static quadratic optimization problems.This research was supported in part by the US Department of Energy under Grant DE-FG-02-88-ER-13939.Paper presented at the 29th IEEE Conference on Decision and Control, Honolulu, Hawaii, 1990.     

Mutation rates and equilibrium selection under stochastic evolutionary dynamics

We examine an evolutionary model in which the mutation rate varies with the strategy. Bergin and Lipman (Econometrica 64:943–956, 1996) show that equilibrium selection using stochastic evolutionary processes depends on the specification of mutation rates. We offer a characterization of how mutation rates determine the selection of Nash equilibria in 2 × 2 symmetric coordination games for single and double limits of the small mutation rate and the large population size. We prove that the restrictions on mutation rates which ensure that the risk-dominated equilibrium is selected are the same for both orders of limits.     

Some interesting properties of maximin strategies

Since the seminal paper of Nash (1950) game theoretic literature has focused mostly on equilibrium and not on maximin (minimax) strategies. We study the properties of these strategies in non-zero-sum strategic games that possess (completely) mixed Nash equilibria. We find that under certain conditions maximin strategies have several interesting properties, some of which extend beyond 2-person strategic games. In particular, for n-person games we specify necessary and sufficient conditions for maximin strategies to yield the same expected payoffs as Nash equilibrium strategies. We also show how maximin strategies may facilitate payoff comparison across Nash equilibria as well as refine some Nash equilibrium strategies.