A note on correlated equilibrium

The set of correlated equilibria for a bimatrix game is a closed, bounded, convex set containing the set of Nash equilibria. We show that every extreme point of a maximal Nash set is an extreme point of the above convex set. We also give an example to show that this result is not true in the payoff space, i.e. there are games where no Nash equilibrium payoff is an extreme point of the set of correlated equilibrium payoffs.     

Linear–quadratic stochastic two-person nonzero-sum differential games: Open-loop and closed-loop Nash equilibria

In this paper, we consider a linear–quadratic stochastic two-person nonzero-sum differential game. Open-loop and closed-loop Nash equilibria are introduced. The existence of the former is characterized by the solvability of a system of forward–backward stochastic differential equations, and that of the latter is characterized by the solvability of a system of coupled symmetric Riccati differential equations. Sometimes, open-loop Nash equilibria admit a closed-loop representation, via the solution to a system of non-symmetric Riccati equations, which could be different from the outcome of the closed-loop Nash equilibria in general. However, it is found that for the case of zero-sum differential games, the Riccati equation system for the closed-loop representation of an open-loop saddle point coincides with that for the closed-loop saddle point, which leads to the conclusion that the closed-loop representation of an open-loop saddle point is the outcome of the corresponding closed-loop saddle point as long as both exist. In particular, for linear–quadratic optimal control problem, the closed-loop representation of an open-loop optimal control coincides with the outcome of the corresponding closed-loop optimal strategy, provided both exist.     

非紧集上不连续函数的Ky Fan不等式及其等价形式和应用

证明了非紧集上不具有任何连续性的函数弱Ky Fan点的存在性,给出了在函数只具非常弱的连续性和凸性条件下非紧集上Ky Fan不等式解的存在性,并给出它的两种等价形式.作为应用:(1)得到Ky Fan截口定理和Fan-Browder不动点定理的推广;(2)应用于博弈理论,得到几个新的Nash平衡存在性定理.     

Approximate fixed point theorems in Banach spaces with applications in game theory

In this paper some new approximate fixed point theorems for multifunctions in Banach spaces are presented and a method is developed indicating how to use approximate fixed point theorems in proving the existence of approximate Nash equilibria for non-cooperative games.     

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

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.     

Fixed point theorems and their applications to theory of Nash equilibria

In this paper we prove fixed point theorems for set-valued mappings in products of posets. Applications to the theory of Nash equilibria are presented.     

On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.     

Equilibria in a competitive model arising from linear production situations with a common-pool resource

In this paper we deal with linear production situations in which there is a limited common-pool resource, managed by an external agent. The profit that a producer can attain depends on the amount of common-pool resource obtained through a certain procedure. We contemplate a competitive process among the producers and study the corresponding non-cooperative games, describing their (strict) Nash equilibria in pure strategies. It is shown that strict Nash equilibria form a subset of strong Nash equilibria, which in turn form a proper subset of Nash equilibria.     

Evolution by Non-Convex Functionals

We establish a semi-group solution concept for flows that are generated by generalized minimizers of non-convex energy functionals. We use relaxation and convexification to define these generalized minimizers. The main part of this work consists in exemplary validation of the solution concept for a non-convex energy functional. For rotationally invariant initial data it is compared with the solution of the mean curvature flow equation. The basic example relates the mean curvature flow equation with a sequence of iterative minimizers of a family of non-convex energy functionals. Together with the numerical evidence this corroborates the claim that the non-convex semi-group solution concept defines, in general, a solution of the mean curvature equation.     

Paths leading to the Nash set for nonsmooth games

Maschler, Owen and Peleg (1988) constructed a dynamic system for modelling a possible negotiation process for players facing a smooth n-person pure bargaining game, and showed that all paths of this system lead to the Nash point. They also considered the non-convex case, and found in this case that the limiting points of solutions of the dynamic system belong to the Nash set. Here we extend the model to i) general convex pure bargaining games, and to ii) games generated by “divide the cake” problems. In each of these cases we construct a dynamic system consisting of a differential inclusion (generalizing the Maschler-Owen-Peleg system of differential equations), prove existence of solutions, and show that the solutions converge to the Nash point (or Nash set). The main technical point is proving existence, as the system is neither convex valued nor continuous. The intuition underlying the dynamics is the same as (in the convex case) or analogous to (in the division game) that of Maschler, Owen, and Peleg. Received August 1997/Final version May 1998     

Reconstruction of noisy signals by minimization of non-convex functionals

Non-convex functionals have shown sharper results in signal reconstruction as compared to convex ones, although the existence of a minimum has not been established in general. This paper addresses the study of a general class of either convex or non-convex functionals for denoising signals which combines two general terms for fitting and smoothing purposes, respectively. The first one measures how close a signal is to the original noisy signal. The second term aims at removing noise while preserving some expected characteristics in the true signal such as edges and fine details. A theoretical proof of the existence of a minimum for functionals of this class is presented. The main merit of this result is to show the existence of minimizer for a large family of non-convex functionals.     

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.     

Constructions of Nash Equilibria in Stochastic Games of Resource Extraction with Additive Transition Structure

A class of N-person stochastic games of resource extraction with discounted payoffs in discrete time is considered. It is assumed that transition probabilities have special additive structure. It is shown that the Nash equilibria and corresponding payoffs in finite horizon games converge as horizon goes to infinity. This implies existence of stationary Nash equilibria in the infinite horizon case. In addition the algorithm for finding Nash equilibria in infinite horizon games is discussed     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

Equi-well-posed games

In this paper, the notion of equi-well-posed optimization problem as studied by Dontchev and Zolezzi, (Ref. 1) is extended to noncooperative games. Some existence theorems for Berge and Nash equilibria are obtained. Under some invariance properties, the existence of Berge equilibria which are also Nash equilibria points is studied.     

How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

On existence of undominated pure strategy Nash equilibria in anonymous nonatomic games: a generalization

In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact. Received August 2001     

Approximations of Nash equilibria

Inspired by previous works on approximations of optimization problems and recent papers on the approximation of Walrasian and Nash equilibria and on stochastic variational inequalities, the present paper investigates the approximation of Nash equilibria and clarifies the conditions required for the convergence of the approximate equilibria via a direct approach, a variational approach, and an optimization approach. Besides directly addressing the issue of convergence of Nash equilibria via approximation, our investigation leads to a deeper understanding of various notions of functional convergence and their interconnections; more importantly, the investigation yields improved conditions for convergence of the approximate Nash equilibria via the variational approach. An illustrative application of our results to the approximation of a Nash equilibrium in a competitive capacity expansion model under uncertainty is presented.     

A more refined convexity idea for Nash equilibria

In this paper, we relax the classical quasi-concavity assumption for the existence of pure Nash equilibria in the setting of constrained and unconstrained games in normal form. Multiconnected convexity (H. Ben-El-Mechaiekh et al., 1998) in spaces without any linear structure is a keen point. We present two games in which we show how the generalized continuity and quasi-concavity hypotheses are unrelated to each other as sufficient conditions for existence of Nash equilibria for games in normal form. Then our results are applied to two non-zero-sum games lacking the classical quasi-concavity assumption (Nash, 1950) and the more recent improvements (Ziad, 1999) and (Abalo and Kostreva, 2004). As minor results, we introduce new concept of convexity, named a-convexity, and some counterexamples of the relationships between some continuity conditions on players’ payoffs imposed by Lignola (1997), Reny (1999) and Simon (1987).