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.     

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.     

Structure of extreme correlated equilibria: a zero-sum example and its implications

We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments.     

A tractable multi-leader multi-follower peak-load-pricing model with strategic interaction

While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.

     

On participation games with complete information

We analyze a class of two-candidate voter participation games under complete information that encompasses as special cases certain public good provision games. We characterize the Nash equilibria of these games as stationary points of a non-linear programming problem, the objective function of which is a Morse function (onethat does not admit degenerate critical points) for almost all costs of participation. We use this fact to establish that, outside a closed set of measure zero of participation costs, all equilibria of these games are regular (an alternative to the result of De Sinopoli and Iannantuoni in Econ Theory 25(2):477–486, 2005). One consequence of regularity is that the equilibria of these games are robust to the introduction of (mild) incomplete information. Finally, we establish the existence of monotone Nash equilibria, such that players with higher participation cost abstain with (weakly) higher probability.      

多目标对策的弱Pareto-Nash平衡点集的稳定性研究

通过定义多目标对策的加权Nash平衡点集,得出它和对应对策的弱Pareto-Nash平衡点集之间的关系,证明了在一定条件下的多目标对策的弱Pareto-Nash平衡点集的稳定性.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

正则对策的N-M稳定集及其唯一存在定理

研究了有非对称性和负传递性偏好的无限策略对策,提出了N-M稳定集和正则对策的概念,其中N-M稳定集是将合作对策中由Von Neumann 和Morgenstern给出的相应概念引入到策略对策中的.所谓正则对策是指其Nash均衡集中每条链关于一致偏好总有上界的无限策略对策.证明了每个正则对策都有唯一N-M稳定集. 此结果及其应用例子说明正则对策N-M稳定集的概念对于策略对策的纯Nash均衡的精炼起着重要作用.     

On a class of nonzero-sum,linear-quadratic differential games

A class of two-player, nonzero-sum, linear-quadratic differential games is investigated for Nash equilibrium solutions when both players use closed-loop control and when one or both of the players are required to use open-loop control. For three formulations of the game, necessary and sufficient conditions are obtained for a particular strategy set to be a Nash equilibrium strategy set. For a fourth formulation of the game, where both players use open-loop control, necessary and sufficient conditions for the existence of a Nash equilibrium strategy set are developed. Several examples are presented in order to illustrate the differences between this class of differential games and its zero-sum analog.This research was supported by the National Science Foundation under Grant No. GK-3341.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Performance versus informativeness in linear-quadratic Gaussian noncooperative games

In this paper, we study the impact of informativeness on the performance of linear quadratic Gaussian Nash and Stackelberg games. We first show that, in two-person static Nash games, if one of the players acquires more information, then this extra information is beneficial to him, provided that it is orthogonal to both players' information. A special case is that when one of the players is informationally stronger than the other, then any new information is beneficial to him. We then show that a similar result holds for dynamic Nash games. In the dynamic games, the players use strategies that are linear functions of the current estimates of the state, generated by two Kalman filters. The same properties are proved to hold in static and feedback Stackelberg games as well.This work was partially supported by the US Air Force Office of Scientific Research under Grant No. AFOSR-82-0174.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

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.     

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     

A note on polymatrix games

This work is concerned with the class ofn-person games called polymatrix games (Yanovskaya (1968)). The structure of the set of Nash equilibrium points in a polymatrix game is studied and characterizations of these games are given.     

Generic stability of Nash equilibria for noncooperative differential games

The stability of Nash equilibria against the perturbation of the right-hand side functions of state equations for noncooperative differential games is investigated. By employing the set-valued analysis theory, we show that the differential games whose equilibria are all stable form a dense residual set, and every differential game can be approximated arbitrarily by a sequence of stable differential games, that is, in the sense of Baire’s category most of the differential games are stable.     

利他扰动与Nash均衡点集的利他稳定性

引入了一个新的利他扰动.定义了KyFan点集的利他本质集,进一步证明在此扰动下,KyFan点集的利他本质连通区的存在性.证明了满足一定条件的n人非合作博弈中,Nash均衡点集至少存在一个利他本质连通区,而且Nash均衡点集的每一个本质集必是利他稳定集,Nash均衡点集的本质连通区也是利他本质集连通区.     

Farsighted stable sets in Hotelling’s location games

We apply the farsighted stable set to two versions of Hotelling’s location games: one with a linear market and another with a circular market. It is shown that there always exists a farsighted stable set in both games, which consists of location profiles that yield equal payoff to all players. This stable set contains location profiles that reflect minimum differentiation as well as those profiles that reflect local monopoly. These results are in contrast to those obtained in the literature that use some variant of Nash equilibrium. While this stable set is unique when the number of players is two, uniqueness no longer holds for both models when the number of players is at least three.     

When “Better” is better than “Best”

We consider two-player normal form games where each player has the same finite strategy set. The payoffs of each player are assumed to be i.i.d. random variables with a continuous distribution. We show that, with high probability, the better-response dynamics converges to pure Nash equilibrium whenever there is one, whereas best-response dynamics fails to converge, as it is trapped.     

A survey of static and dynamic potential games

Potential games are noncooperative games for which there exist auxiliary functions, called potentials, such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.